Medium Include/Exclude Dynamic Programming
In plain English: Pack a bag with items of different weights and values to maximize total value without going over the weight limit.
For each item, decide include or exclude. dp[w] = max value achievable with capacity w. Process items in reverse to avoid reuse.
Prompt
Given n items with weights and values and a capacity W, find the maximum value you can carry without exceeding W. Each item can be used at most once.
Try to write it from scratch before scrolling down.
Solution
def knapsack(weights, values, W):
dp = [0] * (W + 1)
for i in range(len(weights)):
# reverse to ensure each item used at most once
for w in range(W, weights[i] - 1, -1):
dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
return dp[W]
# Test: knapsack([1,3,4,5], [1,4,5,7], 7) == 9 (items 1,2: weight 3+4=7, value 4+5=9)
# Test: knapsack([2,3,4,5], [3,4,5,6], 5) == 7