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
StateMeansNeedDecisionCombination
says whether some subset of sums to exactly .Feasibility without : ; if , feasibility after taking it: .Skip or take .. Base: .

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 <=
StateMeansNeedDecisionCombination
is the maximum value obtainable from items with capacity at most .; if , also .Skip item , or take it once if it fits., excluding take if it does not fit. Base: .

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];