Dynamic Programming21 sections · 916 units
Open in Course

Unbounded Knapsack - Transition

Reuse allowed

For each capacity ww and each item ii: dp[w]=max(dp[w],dp[wwi]+vi)dp[w] = \max(dp[w], dp[w-w_i] + v_i) if wiww_i \le w Notice the difference from 0/1: you use dp[wwi]dp[w-w_i], not dpprev[wwi]dp_{prev}[w-w_i].

This allows taking the same item multiple times. Process weights from 00 to WW (not reversed like 0/1). When computing dp[w]dp[w], you want dp[wwi]dp[w-w_i] to already include items from this round. This formula captures the relationship between smaller problems.