The 0/1 knapsack problem models packing: you have items, each with a weight and a value, and a bag with a weight capacity. Each item may be taken once or left behind. Maximize total value without exceeding the capacity.
Implement knapsack(weights, values, capacity). The lists weights and values line up by index: item i has weight weights[i] and value values[i].
Build a table dp where dp[i][cap] is the best value using only the first i items with capacity cap. For each item you choose between skipping it (dp[i-1][cap]) and taking it when it fits (dp[i-1][cap - weight] + value). Take the larger.
Example: weights [1, 3, 4, 5], values [1, 4, 5, 7], capacity 7. Taking the items of weight 3 and weight 4 uses all 7 units of capacity for value 4 + 5 = 9, which is optimal.
Examples:
def climb_stairs(n):
"""Number of ways to climb n stairs taking 1 or 2 steps, using memoization."""
memo = {}
def ways(k):
if k < 0:
return 0
if k == 0:
return 1
if k in memo:
return memo[k]
memo[k] = ways(k - 1) + ways(k - 2)
return memo[k]
return ways(n)
def coin_change(coins, amount):
"""Minimum number of coins to make amount, or -1 if impossible (tabulation)."""
INF = amount + 1
dp = [0] + [INF] * amount
for a in range(1, amount + 1):
for c in coins:
if c <= a and dp[a - c] + 1 < dp[a]:
dp[a] = dp[a - c] + 1
return dp[amount] if dp[amount] != INF else -1
def knapsack(weights, values, capacity):
"""Max total value with total weight <= capacity (0/1 knapsack, tabulation)."""
# TODO: build a 2D dp table of size (n + 1) by (capacity + 1), all zeros.
# For item i (1-based) with weight w and value v, for every cap:
# skip: dp[i][cap] = dp[i - 1][cap]
# take: if w <= cap, consider dp[i - 1][cap - w] + v and keep the larger.
# Return dp[n][capacity].
pass
The editor and the test runner need a wide screen. Open this page on a desktop browser and your progress will be waiting.
The 0/1 knapsack problem models packing: you have items, each with a weight and a value, and a bag with a weight capacity. Each item may be taken once or left behind. Maximize total value without exceeding the capacity.
Implement knapsack(weights, values, capacity). The lists weights and values line up by index: item i has weight weights[i] and value values[i].
Build a table dp where dp[i][cap] is the best value using only the first i items with capacity cap. For each item you choose between skipping it (dp[i-1][cap]) and taking it when it fits (dp[i-1][cap - weight] + value). Take the larger.
Example: weights [1, 3, 4, 5], values [1, 4, 5, 7], capacity 7. Taking the items of weight 3 and weight 4 uses all 7 units of capacity for value 4 + 5 = 9, which is optimal.
Examples:
Press Run Tests or ⌘↩ to check your solution.