Dynamic Programming21 sections · 916 units
Open in Course

Unbounded Knapsack - State Design

One dimension

Here's the simplification: you don't need to track which items you've processed. Since items can repeat, the order doesn't matter.

Define dp[w]dp[w] as the maximum value achievable with capacity ww. That's it. One dimension instead of two. For each capacity, you consider all items and decide whether to add one more copy of each. Base case: dp[0]=0dp[0] = 0 (zero capacity means zero value).