3 ms·

Actually, the knapsack problem allows taking an item more than once. The problem described in the blog is the 0-1 knapsack problem which can be solved in polyno

Actually, the knapsack problem allows taking an item more than once. The problem described in the blog is the 0-1 knapsack problem which can be solved in polynomial time.

chaoxu 6y ago
0-1 knapsack is not known to be solvable in polynomial time.
- howling 6y ago
  Okay, to be pedantic, pseudo-polynomial time.