arraysdsadynamic-programming
Why does 0/1 knapsack loop backward?
Anonymous
With a one-dimensional dp array, process capacities from high to low for each item. Then dp[c - weight] still represents the state before that item, so it cannot be reused in the same pass. For unbounded knapsack, an ascending loop allows reuse. Both versions take O(nC) time and O(C) space for n items and capacity C.
0