Algorithms and Data Structures · Senior · Question 24 of 75
What does it mean that the 0/1 knapsack DP is pseudo-polynomial?
- ✓Correct answer: O(n × W) depends on the value W, which is exponential in its bit length
- 2It's polynomial only when all item weights are equal
- 3It always finds an approximate answer, never the exact one
Explanation
The table has W columns, and each extra bit in W doubles it, so the work is exponential in the input size. Knapsack is NP-hard; the DP is fast only when capacities are small integers.