Knapsack dynamic programming

When to use it

Use it when each item is taken or left against a budget or an exact total, so the cells are numbered by the amount used, not by position.

It belongs to the optimization group: Find the best answer without trying every possibility: reuse smaller answers, or take the safe choice first.

Watch it work

A hiker's bag carries a limited weight. The lists give the weight and the value of a tent, a stove and a lamp, in that order. Each goes in once or stays at home. Return the largest total value the bag can carry.

Input
weights = [4, 3, 1]
values = [6, 3, 4]
limit = 4

Output
7

The method

1. Keep the best value for each bag size, all 0 at first
2. For each item, visit the sizes from large to small
3. Keep the larger: leave the item out, or pack it
4. Return the best value for the full bag

The run, one moment at a time

1. Step 1. best[size] will hold the largest value that fits in a bag of that size, using the items seen so far. No item has been seen, so every cell is 0.

   item: tent stove lamp
   weights: 4 3 1
   values: 6 3 4
   best: 0 0 0 0 0
   

2. Step 2. The tent weighs 4 and is worth 6. Bags of size 0 to 3 cannot hold it, so those cells stay. Only size 4 is visited.

   item: tent stove lamp
   weights: 4 3 1
   values: 6 3 4
   best: 0 0 0 0 0
   

3. Step 3. Size 4 without the tent: 0. With it: 6 plus cell 0, which holds 0, makes 6. Write 6, the larger.

   item: tent stove lamp
   weights: 4 3 1
   values: 6 3 4
   best: 0 0 0 0 6
   

4. Step 2. The stove weighs 3 and is worth 3. Bags of size 0 to 2 cannot hold it, so those cells stay. Sizes 4 down to 3 are visited, largest first.

   item: tent stove lamp
   weights: 4 3 1
   values: 6 3 4
   best: 0 0 0 0 6
   

5. Step 3. Size 4 without the stove: 6. With it: 3 plus cell 1, which holds 0, makes 3. Keep 6.

   item: tent stove lamp
   weights: 4 3 1
   values: 6 3 4
   best: 0 0 0 0 6
   

6. Step 3. Size 3 without the stove: 0. With it: 3 plus cell 0, which holds 0, makes 3. Write 3, the larger.

   item: tent stove lamp
   weights: 4 3 1
   values: 6 3 4
   best: 0 0 0 3 6
   

7. Step 2. The lamp weighs 1 and is worth 4. A bag of size 0 cannot hold it, so that cell stays. Sizes 4 down to 1 are visited, largest first.

   item: tent stove lamp
   weights: 4 3 1
   values: 6 3 4
   best: 0 0 0 3 6
   

8. Step 3. Size 4 without the lamp: 6. With it: 4 plus cell 3, which holds 3, makes 7. Write 7, the larger. Cell 3 has not met the lamp yet, so the lamp is packed once.

   item: tent stove lamp
   weights: 4 3 1
   values: 6 3 4
   best: 0 0 0 3 7
   

9. Step 3. Size 3 without the lamp: 3. With it: 4 plus cell 2, which holds 0, makes 4. Write 4, the larger.

   item: tent stove lamp
   weights: 4 3 1
   values: 6 3 4
   best: 0 0 0 4 7
   

10. Step 3. Size 2 without the lamp: 0. With it: 4 plus cell 1, which holds 0, makes 4. Write 4, the larger.

    item: tent stove lamp
    weights: 4 3 1
    values: 6 3 4
    best: 0 0 4 4 7
    

11. Step 3. Size 1 without the lamp: 0. With it: 4 plus cell 0, which holds 0, makes 4. Write 4, the larger.

    item: tent stove lamp
    weights: 4 3 1
    values: 6 3 4
    best: 0 4 4 4 7
    

12. Step 4. The cell for size 4 is the answer: 7, from the stove and the lamp. Packing the most valuable item first, the tent, would give only 6.

    item: tent stove lamp
    weights: 4 3 1
    values: 6 3 4
    best: 0 4 4 4 7
    

The code

The numbered comments are the steps of the method.

function solve(weights, values, limit) {
  // 1. Keep the best value for each bag size, all 0 at first
  const best = Array(limit + 1).fill(0);
  // 2. For each item, visit the sizes from large to small
  for (let i = 0; i < weights.length; i++) {
    // A bag smaller than the item cannot hold it, so stop there.
    for (let size = limit; size >= weights[i]; size--) {
      // 3. Keep the larger: leave the item out, or pack it
      const packed = best[size - weights[i]] + values[i];
      best[size] = Math.max(best[size], packed);
    }
  }
  // 4. Return the best value for the full bag
  return best[limit];
}

def solve(weights, values, limit):
    # 1. Keep the best value for each bag size, all 0 at first
    best = [0] * (limit + 1)
    # 2. For each item, visit the sizes from large to small
    for i in range(len(weights)):
        # A bag smaller than the item cannot hold it, so stop there.
        for size in range(limit, weights[i] - 1, -1):
            # 3. Keep the larger: leave the item out, or pack it
            packed = best[size - weights[i]] + values[i]
            best[size] = max(best[size], packed)
    # 4. Return the best value for the full bag
    return best[limit]

How to spot it

Given: Each item has a size, and the total may not pass a limit

Many different choices use the same amount, and only the best of them matters. So one cell for each amount is enough.

Asked: Can some of the numbers add up to exactly this total?

Which numbers made a sum does not matter, only that it can be reached. Mark each reachable sum in its cell, number by number.

Asked: The fewest items, or the number of ways, to make an exact amount

Take one item off the amount and a smaller amount is left. Its cell is already filled, so the answer is read, not worked out again.

Limits: The limit or the target total is at most a few thousand

The row has one cell for each amount from 0 to the limit, so the limit must be small enough to walk through.

Looks like it, but is not

• No budget and no total: the answer at a position depends on a few earlier positions. Use One-dimensional dynamic programming. There the cells are numbered by position in the list. Here they are numbered by the amount used, and every item updates the whole row.
• Every combination that reaches the total must be listed, and there are about 20 items. Use Backtracking. The row can say whether, how many, or how good. It does not hold the combinations themselves, so each one has to be built.
• Fill a bag up to a weight limit, and any item may be cut and taken in part. Use Greedy choice. Then taking what is worth most for its weight first is never regretted. With whole items it can be, so every amount needs a cell.

Cost and mistakes

Time is the number of items times the limit, written O(n * limit), because each item visits each amount once. Extra space is one cell for each amount from 0 to the limit.

Watch out

• When an item can be packed once, visit the sizes from large to small. Going up, a cell you read may already hold the item, and it is packed again. Here the answer would be 16: the lamp four times.
• When an item may be used as many times as you like, go from small to large on purpose. Then a cell may build on a cell that already used the same item.

In the 150

4 problems of the 150 use it. Naming them gives their method away, so the list is folded.