---
title: "knapsack"
type: concept
source: https://www.jemoka.com/posts/kbhknapsack/
confidence: high
status: active
---

unbounded knapsack Suppose I have infinite copies of all items, what&rsquo;s the most valuable way to fill the knapsack?
DP, with subproblems containing smaller knapsack. K[x] = max_i { K[x-wi] + vi }
def solve(): dp[0] = 0 sol[0] = [] for x in 1 ... knapsack_size: dp[x] = 0 for i in 1 ... num_items: if weight(i) &lt;= x: # why max base case instead of incrementally adding stuff? # a bigger knapsack that fits 2 things can be find a sa dp[x] = max(dp[x], dp[x-weight(i)]+value(i)) if dp[x] changed: sol[x] = sol[x-weight(i)] + [i] 0/1 knapsack Suppose I have one copy of each item; what&rsquo;s the most valuable way to fill the knapsack? We have to keep track of a 2D DP table. Casework:
optimal solution for j items doesn&rsquo;t use item j: K[x,j] = K[x,j-1] optimal solution for j items does use item j: K[x,j] = K[x-weight(j),j-1]+value(j) So we have: K[x,j] = max(K[x,j-1], K[x-weight(j),j-1]+value(j), for each j). We can thus solve 0/1 knapsack in \(O\qty(nW)\).
