Leonid Karlinsky, Joseph Shtok, et al.
CVPR 2019
Paper
A Polynomial-Time Algorithm for the Knapsack Problem with Two Variables
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. © 1976, ACM. All rights reserved.
Related
Conference paper
Hybrid reinforcement learning with expert state sequences
Xiaoxiao Guo, Shiyu Chang, et al.
AAAI 2019
Michael Hersche, Mustafa Zeqiri, et al.
NeSy 2023
John R. Kender, Rick Kjeldsen
IEEE Transactions on Pattern Analysis and Machine Intelligence