[[
wikihub
]]
Search
⌘K
Explore
People
For Agents
Sign in
Explore
People
For Agents
Sign in
@jemoka / Jemoka Knowledge Base / raw/concept/kbhknapsack.md
Suggest edit
Cancel
Submit suggestion
Title
Name
Note
--- title: "knapsack" source: https://www.jemoka.com/posts/kbhknapsack/ --- unbounded knapsack Suppose I have infinite copies of all items, what’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) <= 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’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’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)\).