Knapsack problems

The problem

You are packing a trekking bag that can carry at most W kilograms. Each item has a weight and a value (how useful it is). Each item is either taken or left: you cannot take half a tent, and you have only one of each. Which items give the largest total value without going over W? This is the 0/1 knapsack problem ("knapsack" is an old word for a backpack; "0/1" means each item is taken 0 or 1 times).

Trying every subset of n items is O(2ⁿ). Greedy by value per kilogram fails too: with capacity 50 and items (weight 10, value 60), (20, 100), (30, 120), the best ratio picks the first two for 160, but the last two give 220.

The 2-D table

State: dp[i][c] = the best value using only the first i items with capacity c. For item i (weight w, value v) there are two choices. Skip it: dp[i − 1][c]. Take it, if w ≤ c: v + dp[i − 1][c − w], the best with the remaining capacity from the earlier items only. dp[i][c] is the larger. Base case: dp[0][c] = 0 (no items, no value). The answer is dp[n][W]. Time and space are O(n × W).

In the table, capacity 4 with the first two items gives 35 (both items, weight 4). The third item alone (value 30) cannot beat that, so the last row stays 35.

One row, looping capacity downwards

Row i only reads row i − 1, so one array dp[c] can hold "the previous row" and be updated in place. The catch is the order. dp[c] reads dp[c − w], a SMALLER capacity. If you loop c upwards, dp[c − w] has already been updated for this item, so the item gets counted again. If you loop c DOWNWARDS from W to w, dp[c − w] still holds the value from before this item, so each item is used at most once. Space drops to O(W).

def knapsack_01(weights, values, capacity):
    dp = [0] * (capacity + 1)
    for w, v in zip(weights, values):
        for c in range(capacity, w - 1, -1):     # downwards!
            dp[c] = max(dp[c], dp[c - w] + v)
    return dp[capacity]

print(knapsack_01([10, 20, 30], [60, 100, 120], 50))   # Output: 220

Unbounded knapsack: loop upwards

If you have unlimited copies of each item (like coins in coin change), you WANT the item to be reusable. Loop c upwards: dp[c − w] may already include this item, so dp[c] can add it again. With one item of weight 2 and value 3 and capacity 10, the 0/1 answer is 3 and the unbounded answer is 15. The loop direction is the whole difference.

Subset sum and equal partition

Subset sum asks: can some of the numbers add up exactly to a target T? It is a knapsack where weight equals value and we only care about yes or no. can[s] = True if some subset sums to s; can[0] = True; for each number x, loop s downwards from T to x and set can[s] = can[s] or can[s − x].

Partition equal subset sum asks whether a list can be split into two groups with equal sums. If the total is odd, the answer is no at once. Otherwise it is subset sum with T = total / 2: if one group reaches half, the rest is the other half.

Counting subsets, and target sum

Replace True/False with counts: ways[0] = 1, and ways[s] += ways[s − x] while looping s downwards. This counts subsets by position, so in [1, 1, 2] the two 1s are different items. A zero doubles the count, because each subset can include it or not.

The "target sum" puzzle puts a + or − in front of every number and asks how many sign choices reach a target. Let P be the sum of the plus numbers and N the sum of the minus numbers. P − N = target and P + N = total, so P = (total + target) / 2. If that is not a whole number, or is negative, the answer is 0. Otherwise count the subsets that sum to P.

Common mistakes

• Looping capacity upwards in 0/1 knapsack, so items are reused. Fix: downwards for 0/1, upwards for unbounded.
• Sorting by value per weight and taking greedily. Fix: greedy works only for the fractional knapsack (where you may take part of an item), not for 0/1.
• Forgetting the odd-total check in equal partition. Fix: if total % 2 == 1, return False before building the table.
• Starting the count array with ways[0] = 0. Fix: the empty subset makes sum 0, so ways[0] = 1.
• In target sum, not checking that (total + target) is even and non-negative. Fix: return 0 for those cases before counting.