knapsack DP
Work in Progress
Summary
Top-down
Solve(i, b):
if (i, b) is a base state:
return BASE(i, b)
if Memo[i, b] != UNSEEN:
return Memo[i, b]
// Option 1: skip item i
answer = Solve(i + 1, b)
// Option 2: take item i
if weight[i] <= b:
candidate = TAKE(i, Solve(i + 1, b - weight[i]))
answer = COMBINE(answer, candidate)
Memo[i, b] = answer
return answer
return Solve(1, B)
Bottom-up
for b = 0 to B:
DP[n + 1, b] = BASE(n + 1, b)
for i = n down to 1:
for b = 0 to B:
DP[i, b] = DP[i + 1, b] // skip
if weight[i] <= b: // take
candidate = TAKE(i, DP[i + 1, b - weight[i]])
DP[i, b] = COMBINE(DP[i, b], candidate)
return DP[1, B]
Concept
Subset Sum
- pseudopolynomial time,
is polynomial as long as is small relative to - knapsack DP
Problem
- input:
positive integers and a target - output: “Yes” if there is a subset of numbers that sum to
, “No” otherwise
| State | Means | Need | Decision | Combination |
|---|---|---|---|---|
| Feasibility without | Skip or take |
Recursive
SubsetSum(i, l):
if l == 0:
return Yes
if l < 0 or i > n:
return No
return SubsetSum(i + 1, l - a) or SubsetSum(i + 1, l)
SubsetSum(0, k)
Top-down
- 2d dp array
Bottom-up
- can be more space efficient
Knapsack
- knapsack DP
Problem
- input:
items with weight and value and a weight threshold - output: maximum value
, the sum of the values of a subset, where the sum of all weights <=
| State | Means | Need | Decision | Combination |
|---|---|---|---|---|
| Skip item |
Top-down
Knapsack(i, c):
if i == 0:
return 0
if Memo[i, c] has been computed:
return Memo[i, c]
answer = Knapsack(i - 1, c)
if w[i] <= c:
answer = max(answer, v[i] + Knapsack(i - 1, c - w[i]))
Memo[i, c] = answer
return answer
return Knapsack(n, W)
Bottom-up
Application
Leetcode: Coin Change
- knapsack DP
cpp
int dp[amount + 1];
dp[0] = 0;
sort(begin(coins), end(coins)); // sort first
for (int i = 1; i <= amount; i++) {
dp[i] = INT_MAX;
for (int c: coins) {
if (c > i) break; // terminate if coin is larger than the current amount, possible since we sort first
if (dp[i - c] != INT_MAX) dp[i] = min(dp[i], 1 + dp[i - c]); // check if the sub-problem has a solution and use it
// this will result in the minimum coins to reach this current amount
}
}
return dp[amount] == INT_MAX ? -1 : dp[amount];