The 0/1 knapsack

Lesson · 13 min read · Dynamic programming · 0/1 knapsack

Each item is taken once or not at all. The state is (items considered, capacity left), and each item is a take-or-skip decision.

The problem

Items have weights and values; a bag holds at most a given weight. Choose a set of items, each at most once, with the largest total value that fits. With items of weight 1, 3, 4, 5 kg worth 1, 4, 5 and 7 points and a 7 kg bag, the best is the 3 kg and 4 kg items, 9 points. Budget allocation, choosing projects under a headcount limit, and loading cargo are all knapsacks.

Greedy by value per kilogram fails: it takes the 5 kg item (1.4 points per kg) first and is left with 2 kg, worth 1 point at most, 8 in all.

State and recurrence

Decide the items one at a time. After deciding the first i items, what matters for the rest is only how much capacity is left. So the state is (i, c): the best value using items 1..i with capacity c.

Recurrence

best(i, c)

skip item i: best(i − 1, c);
take it, if it fits: value[i] + best(i − 1, c − weight[i]);
take the larger.

base cases

best(0, c) = 0: no items, no value.

Taking item i moves to row i − 1: that is what "at most once" means in the recurrence.

Bottom-up

Rows add one item at a time; columns are capacities 0 to 7. Each cell reads the row above: straight up (skip) or up and to the left by the item's weight (take).

Step 1 / 5

Base cases filled first.
Step 2 / 5

Row 1kg·1 filled.
Step 3 / 5

Row 3kg·4 filled.
Step 4 / 5

Row 4kg·5 filled.
Step 5 / 5

Row 5kg·7 filled. best(4, 7) = 9: the 3 kg and 4 kg items.

One row is enough

Row i reads only row i − 1, at the same capacity or a smaller one. So keep a single array and update it in place with capacities going downwards: when best[c] is updated, best[c − w] still holds the previous row's value, because smaller capacities have not been touched yet in this pass.

def knapsack(weights, values, cap):
    best = [0] * (cap + 1)
    for w, v in zip(weights, values):
        for c in range(cap, w - 1, -1):        # downwards: each item used at most once
            best[c] = max(best[c], v + best[c - w])
    return best[cap]

int knapsack(const std::vector<int>& weights, const std::vector<int>& values, int cap) {
    std::vector<int> best(cap + 1, 0);
    for (size_t k = 0; k < weights.size(); ++k)
        for (int c = cap; c >= weights[k]; --c)        // downwards: each item used at most once
            best[c] = std::max(best[c], values[k] + best[c - weights[k]]);
    return best[cap];
}

static int knapsack(int[] weights, int[] values, int cap) {
    int[] best = new int[cap + 1];
    for (int k = 0; k < weights.length; k++)
        for (int c = cap; c >= weights[k]; c--)       // downwards: each item used at most once
            best[c] = Math.max(best[c], values[k] + best[c - weights[k]]);
    return best[cap];
}

function knapsack(weights, values, cap) {
    const best = new Array(cap + 1).fill(0);
    weights.forEach((w, k) => {
        for (let c = cap; c >= w; c--)                // downwards: each item used at most once
            best[c] = Math.max(best[c], values[k] + best[c - w]);
    });
    return best[cap];
}

fn knapsack(weights: &[usize], values: &[i64], cap: usize) -> i64 {
    let mut best = vec![0i64; cap + 1];
    for (&w, &v) in weights.iter().zip(values) {
        for c in (w..=cap).rev() {                    // downwards: each item used at most once
            best[c] = best[c].max(v + best[c - w]);
        }
    }
    best[cap]
}

knapsack :: [Int] -> [Int] -> Int -> Int
knapsack weights values cap = last (foldl add (replicate (cap + 1) 0) (zip weights values))
  where
    -- the new row reads only the previous one, so each item is used at most once
    add best (w, v) = [ if c >= w then max (row ! c) (v + row ! (c - w)) else row ! c | c <- [0 .. cap] ]
      where row = listArray (0, cap) best :: Array Int Int

Going upwards instead would let best[c − w] already include item i, so the item could be taken again and again. That bug is the unbounded knapsack, and the next-but-one module uses it on purpose.

Implementation

In six languages:

def knapsack_01(weights, values, capacity):
    best = [0] * (capacity + 1)                # best[c]: most value within capacity c
    for w, v in zip(weights, values):
        for c in range(capacity, w - 1, -1):   # downwards: each item at most once
            best[c] = max(best[c], v + best[c - w])
    return best[capacity]

#include <algorithm>
#include <vector>

long long solve(const std::vector<int>& weights, const std::vector<int>& values, int capacity) {
    std::vector<long long> best(capacity + 1, 0);
    for (size_t i = 0; i < weights.size(); ++i)
        for (int c = capacity; c >= weights[i]; --c)   // downwards: each item once
            best[c] = std::max(best[c], values[i] + best[c - weights[i]]);
    return best[capacity];
}

class Solution {
    public long knapsack01(int[] weights, int[] values, int capacity) {
        long[] best = new long[capacity + 1];
        for (int i = 0; i < weights.length; i++)
            for (int c = capacity; c >= weights[i]; c--)   // downwards: each item once
                best[c] = Math.max(best[c], values[i] + best[c - weights[i]]);
        return best[capacity];
    }
}

function knapsack01(weights, values, capacity) {
  const best = new Array(capacity + 1).fill(0);
  for (let i = 0; i < weights.length; i++)
    for (let c = capacity; c >= weights[i]; c--)       // downwards: each item once
      best[c] = Math.max(best[c], values[i] + best[c - weights[i]]);
  return best[capacity];
}

fn solve(weights: &[i64], values: &[i64], capacity: i64) -> i64 {
    let cap = capacity as usize;
    let mut best = vec![0i64; cap + 1];
    for (&w, &v) in weights.iter().zip(values) {
        let w = w as usize;
        for c in (w..=cap).rev() {                      // downwards: each item once
            best[c] = best[c].max(v + best[c - w]);
        }
    }
    best[cap]
}

solve :: [Int] -> [Int] -> Int -> Int
solve weights values capacity = last (foldl addItem (replicate (capacity + 1) 0) (zip weights values))
  where
    -- the new row from the previous one: skip the item, or take it from capacity c - w of the previous row
    addItem best (w, v) = [if c >= w then max b (v + best !! (c - w)) else b | (c, b) <- zip [0 ..] best]

The same code is the reference solution to The 0/1 knapsack, where it is compiled and run against the tests in all six languages.

TimeO(n · capacity)

SpaceO(capacity)

Pseudo-polynomial: the running time grows with the numerical size of the capacity, not just the number of items. With capacities in the billions, use a different state, such as the minimum weight for each total value.