Dynamic Programming21 sections · 915 units
Open in Course

Unbounded Knapsack - Transition

Reuse allowed

For each capacity ww and each item ii: dp[w]=max⁡(dp[w],dp[w−wi]+vi)dp[w] = \max(dp[w], dp[w-w_i] + v_i) if wi≤ww_i \le w Notice the difference from 0/1: you use dp[w−wi]dp[w-w_i], not dpprev[w−wi]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[w−wi]dp[w-w_i] to already include items from this round. This formula captures the relationship between smaller problems.