Knapsack problems

In the 0/1 knapsack problem you have n items, each with a weight and a value, and a bag of capacity W. Choose a subset with total weight at most W and maximum total value. Each item is either taken once or not at all.

The DP state is dp[i][c] = best value using the first i items with capacity c. For item i you either skip it (dp[i-1][c]) or take it if it fits (dp[i-1][c - w] + v). The table has n x W states, so the time is O(n x W). This is pseudo-polynomial: fast when W is small, but W can be exponentially large in the number of bits used to write it, and 0/1 knapsack is NP-hard in general.

In the unbounded knapsack each item can be used any number of times. Coin change (fewest coins to make an amount) and coin change II (number of ways) are unbounded knapsacks. Subset sum, partition equal subset sum and target sum are 0/1 knapsacks with booleans or counts instead of values.

1. 1State: dp[c] = best value achievable with capacity c using the items processed so far. Start with dp = [0] * (W + 1).
2. 20/1: for each item (w, v), for c from W down to w: dp[c] = max(dp[c], dp[c - w] + v). Going down means dp[c - w] still refers to the state before this item, so it is not used twice.
3. 3Unbounded: for each item, for c from w up to W: same update. Going up means dp[c - w] may already include this item, which is exactly what allows reuse.
4. 4Counting ways (coin change II): dp[0] = 1 and dp[a] += dp[a - coin], with coins in the outer loop so each combination is counted once regardless of order. Putting amounts in the outer loop counts ordered sequences (permutations) instead.
5. 5Minimum count (coin change): dp[0] = 0, others infinity, dp[a] = min(dp[a], dp[a - coin] + 1).

def knapsack_01(weights, values, cap):
    """Each item at most once."""
    dp = [0] * (cap + 1)               # dp[c] = best value with capacity c
    for w, v in zip(weights, values):
        for c in range(cap, w - 1, -1):    # backwards: item used once
            dp[c] = max(dp[c], dp[c - w] + v)
    return dp[cap]


def coin_change(coins, amount):
    """Unbounded: fewest coins to make amount, or -1."""
    INF = float("inf")
    dp = [0] + [INF] * amount
    for coin in coins:
        for a in range(coin, amount + 1):  # forwards: coin reusable
            dp[a] = min(dp[a], dp[a - coin] + 1)
    return dp[amount] if dp[amount] != INF else -1

# knapsack_01([1, 3, 4], [15, 20, 30], 4) -> 35
# coin_change([1, 3, 4], 6) -> 2

The only difference between the two is the loop direction over capacity: backwards keeps each item single-use, forwards allows reuse. Both run in O(n x W) time with O(W) space.

Cost: O(n x W) time, O(W) space with the 1D array (O(n x W) if you need to reconstruct the chosen items). Pseudo-polynomial; the general problem is NP-hard.