A Polynomial-Time Algorithm for the Knapsack Problem with Two Variables
- 1 January 1976
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 23 (1), 147-154
- https://doi.org/10.1145/321921.321936
Abstract
The general knapsack problem is known to be NP-complete. In this paper a very special knapsack problem ia studied, namely, one with only two variables. A polynomial-time algorithm is presented and analyzed. However, it remains an open problem that for any fixed n > 2, the knapsack problem with n variables can be solved in polynomial time.Keywords
This publication has 3 references indexed in Scilit:
- Approximate Algorithms for the 0/1 Knapsack ProblemJournal of the ACM, 1975
- Computing Partitions with Applications to the Knapsack ProblemJournal of the ACM, 1974
- Reducibility among Combinatorial ProblemsPublished by Springer Nature ,1972