Recursion & DP Target: 15s
The inner loop goes BACKWARDS to prevent reusing item i. Forward loop = unbounded knapsack.
def knapsack(weights, values, W):
n = len(weights)
dp = [0] * (W + 1)
for i in range(n):
for w in range(W, weights[i] - 1, -1): # backwards!
dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
return dp[W]Type it from memory. Go.