The 0/1 Knapsack — Solution & Editorial
1-D DP over capacities, iterating capacity DOWNWARD per item so each item is used at most once.
Complexity: O(N·W)
Watch out: Iterating capacity upward turns it into the unbounded knapsack — items get reused.
1-D DP over capacities, iterating capacity DOWNWARD per item so each item is used at most once.
Complexity: O(N·W)
Watch out: Iterating capacity upward turns it into the unbounded knapsack — items get reused.