### A Polynomial-Time Algorithm for the Knapsack Problem with Two VariablesA Polynomial-Time Algorithm for the Knapsack Problem with Two Variables

Access Restriction
Subscribed

 Author Hirschberg, D. S. ♦ Wong, C. K. Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1976 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science 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 $\textit{n}$ > 2, the knapsack problem with $\textit{n}$ variables can be solved in polynomial time. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1976-01-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 23 Issue Number 1 Page Count 8 Starting Page 147 Ending Page 154

#### Open content in new tab

Source: ACM Digital Library