Knapsack

You sell at a weekend market and carry your goods on a bike trailer that holds 5 kg. You have three things you could bring: a box of honey (2 kg, profit 4), a wheel of cheese (3 kg, profit 7) and a crate of jam (4 kg, profit 10). Each one comes whole or not at all. What should you load?

Jam earns the most per kilo, 2.5, so a common rule takes it first. Then 1 kg is left and nothing fits: profit 10. Honey and cheese together weigh exactly 5 kg and earn 11. With 3 items you could check all 8 combinations. With 40 items there are over a trillion. This is the 0/1 knapsack problem: every item is either in (1) or out (0).

#Why one index is not enough

In 1D Dynamic Programming the state was "the best answer for the first i days". Try that here: "the best profit from the first i items". To decide whether to add item i, you need to know how much space the earlier items used, and that number is not in the state. Two packings with equal profit can leave different room.

So put the space into the state too. That gives a table with one row per item and one column per amount of space, the same kind of table you filled in DP on Grids.

#The five steps

1. State. best[i][w] is the most profit you can make using only the first i items, with at most w kg of space.
2. Recurrence. Item i is either left out or packed. Leave it out and you get best[i − 1][w]. Pack it, if it fits, and you get its value plus the best you can do with the earlier items in the space that remains: value[i] + best[i − 1][w − weight[i]]. Take the larger.
3. Base cases. best[0][w] = 0 for every w: with no items you earn nothing.
4. Order. Each cell reads only the row above. Fill row by row.
5. Answer. best[n][W]: all items allowed, full capacity.

The "take" arrow always comes from the row above. That is what stops an item being used twice: once you pack the cheese, the rest of the space can only hold items from earlier rows.

best[0][w] = 0 for every wfor i from 1 to n:  for w from 0 to W:    best[i][w] = best[i-1][w]            # skip item i    if weight[i] <= w:      take = value[i] + best[i-1][w - weight[i]]      best[i][w] = max(best[i][w], take)return best[n][W]

#The code

function bestProfit(weights, values, capacity) {
  const n = weights.length;
  const best = Array.from({ length: n + 1 }, () => new Array(capacity + 1).fill(0));
  for (let i = 1; i <= n; i++) {
    const weight = weights[i - 1]; // row i is item i - 1 in the arrays
    const value = values[i - 1];
    for (let w = 0; w <= capacity; w++) {
      best[i][w] = best[i - 1][w]; // skip the item
      if (weight <= w) {
        best[i][w] = Math.max(best[i][w], value + best[i - 1][w - weight]); // take it
      }
    }
  }
  return best[n][capacity];
}
 
bestProfit([2, 3, 4], [4, 7, 10], 5); // 11

def best_profit(weights, values, capacity):
    n = len(weights)
    best = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        weight, value = weights[i - 1], values[i - 1]  # row i is item i - 1
        for w in range(capacity + 1):
            best[i][w] = best[i - 1][w]  # skip the item
            if weight <= w:
                best[i][w] = max(best[i][w], value + best[i - 1][w - weight])  # take it
    return best[n][capacity]
 
best_profit([2, 3, 4], [4, 7, 10], 5)  # 11

#One row is enough, if you go backwards

Each row only reads the row above, so you can keep a single array and overwrite it item by item. There is one catch. The "take" option reads best[w − weight], a cell to the left. If you loop w upward, that cell has already been overwritten for the current item, and you end up packing the item twice. Loop w downward and every cell you read on the left still holds the old row.

function bestProfitOneRow(weights, values, capacity) {
  const best = new Array(capacity + 1).fill(0);
  for (let i = 0; i < weights.length; i++) {
    // High to low, so best[w - weights[i]] is still from the previous item.
    for (let w = capacity; w >= weights[i]; w--) {
      best[w] = Math.max(best[w], values[i] + best[w - weights[i]]);
    }
  }
  return best[capacity];
}

def best_profit_one_row(weights, values, capacity):
    best = [0] * (capacity + 1)
    for weight, value in zip(weights, values):
        # High to low, so best[w - weight] is still from the previous item.
        for w in range(capacity, weight - 1, -1):
            best[w] = max(best[w], value + best[w - weight])
    return best[capacity]

The cost depends on the capacity W as well as on the number of items. Three items and a 5 kg limit is 4 × 6 = 24 cells. Write the same weights in grams and the limit becomes 5,000 g: 4 × 5,001 cells for the same answer. With 20 items and a capacity in the billions the table is hopeless, while trying all 2²⁰ (about a million) subsets is quick.

#Common mistakes

#Check yourself

#What to practise next

The table here had items down the side and space across the top. DP on Strings uses a table with one word down the side and another across the top, and fills it with the same "look at the cells you came from" habit. To practise this lesson, try Busking Set List (each item once) and Vending Machine Coin Mixes (unlimited copies, counting).