Knapsack problem

The knapsack problem asks for the most valuable set of items that fits in a backpack: each item has a weight and a value, the backpack holds a limited total weight, and each item is taken (1) or left (0), so it is also called the 0/1 knapsack. It is solved with a table over the items and the capacities. If each item can be taken any number of times, it is solved like coin change, where one array holds the answer for each amount; if items can be cut into pieces, taking the most value per kilogram first is enough.

Explanation

You pack a backpack for a hike, and it holds 6 kg. There are four items: item 1 weighs 3 kg and is worth 6, item 2 is 2 kg worth 3, item 3 is 4 kg worth 7, and item 4 is 5 kg worth 9.

Fig. 1. Four items and a 6 kg backpack. A box is as wide as the item is heavy.

Each item is in or out, so there are 2 · 2 · 2 · 2 = 16 sets to check. Each new item doubles that number, and thirty items give over a billion sets, far more than a program checks in a second.

The natural rule is to pack the items with the most value per kilogram first. Item 1 gives the most, 6 / 3 = 2 per kilogram, so it goes in; of the rest, only item 2 fits the 3 kg left. Items 1 and 2 are worth 6 + 3 = 9, and 1 kg stays empty. Items 2 and 3 fill the backpack exactly and are worth 3 + 7 = 10.

Fig. 2. The rule leaves 1 kg empty; items 2 and 3 fill the backpack.

Whether an item is a good choice depends on what fits in the capacity it leaves, and we can't know that in advance. So try both, starting from the last item: take item 4, and the first 3 items get the 1 kg left; leave it, and the first 3 items get all 6 kg. Either way, what remains is the same question with one item fewer. It depends on two numbers: how many first items are still allowed, and the capacity left.

Fig. 3. Two different sets of choices end at the same question: no items allowed and 1 kg left.

Different choices can end at the same question: taking item 4 alone and taking items 1 and 2 both leave 1 kg with no items allowed. There are only as many questions as pairs of the two numbers. On four items that is 5 · 7 = 35, more than the 16 sets, so here nothing is saved. The saving comes with size: thirty items give over a billion sets but only 31 · 7 = 217 questions, so most questions are reached by many different choices. So each question is answered once and stored, as in dynamic programming.

Keep a table with one cell per question: one row for each number of first items allowed, from none to all four, and one column for each capacity from 0 to 6 kg. A cell holds the best value the first items of its row can pack into its capacity; with no items, it is 0. Each new row adds one item. Leaving it gives the cell above. Taking it gives the cell in the row above, as many columns to the left as the item weighs, plus the item's value. The cell gets the larger.

One number per capacity, as in coin change, isn't enough. It would fill 6 kg with item 1 plus the best for 3 kg, which is item 1 again: 6 + 6 = 12. The row says which items are still allowed.

No items yet: nothing can be packed, so every capacity gets 0.

Item 1 weighs 3 kg and is worth 6. Capacities of 0, 1 and 2 kg are too small for it, so they copy 0 from the row above.

3 kg with item 1: leaving it gives 0; taking it leaves 0 kg, worth 0, so 0 + 6 = 6. The cell gets 6.

4 kg: leaving item 1 gives 0; taking it leaves 1 kg, worth 0, so 6. The cell gets 6.

5 kg: leaving gives 0; taking leaves 2 kg, worth 0, so 6. The cell gets 6.

6 kg: leaving gives 0; taking leaves 3 kg, worth 0 with no items, so 6. The cell gets 6.

Item 2 weighs 2 kg and is worth 3. Capacities of 0 and 1 kg copy 0 from the row above.

2 kg with items 1–2: leaving item 2 gives 0; taking it leaves 0 kg, so 0 + 3 = 3. The cell gets 3.

3 kg: leaving item 2 gives 6; taking it leaves 1 kg, worth 0, so 3. The cell gets 6.

4 kg: leaving gives 6; taking leaves 2 kg, worth 0 with item 1, so 3. The cell gets 6.

5 kg: leaving gives 6; taking leaves 3 kg, worth 6 with item 1, so 6 + 3 = 9. The cell gets 9: items 1 and 2.

6 kg: leaving gives 6; taking leaves 4 kg, worth 6, so 9. The cell gets 9.

Item 3 weighs 4 kg and is worth 7. Capacities of 0 to 3 kg copy 0, 0, 3 and 6 from the row above.

4 kg with items 1–3: leaving item 3 gives 6; taking it leaves 0 kg, so 7. The cell gets 7.

5 kg: leaving gives 9; taking leaves 1 kg, worth 0, so 7. The cell gets 9.

6 kg: leaving gives 9; taking leaves 2 kg, worth 3 with items 1–2, so 3 + 7 = 10. The cell gets 10.

Item 4 weighs 5 kg and is worth 9. Capacities of 0 to 4 kg copy 0, 0, 3, 6 and 7 from the row above.

5 kg with items 1–4: leaving item 4 gives 9; taking it leaves 0 kg, so 0 + 9 = 9. Both choices give 9.

6 kg: leaving item 4 gives 10; taking it leaves 1 kg, worth 0, so 9 < 10. The cell gets 10, and item 4 is left.

1/19

Fig. 4. Step through the table with the buttons or the arrow keys. Watch 6 kg in row 1–3: taking item 3 reads 2 kg in the row above, and that is where 10 comes from.

The answer, 10, is the last cell. The last row also holds the best value for every capacity from 0 to 6 kg.

Implementation

Item i, from 1 to n, weighs w[i] and is worth v[i]. The backpack, called a knapsack in problem statements, holds W, and c is a capacity from 0 to W. The table is a vector of vectors dp. In the stage names of dynamic programming:

1. State: dp[i][c] is the best value of a set of the first i items with total weight at most c.

2. Base case: dp[0][c] = 0 for every c: no items, nothing to pack.

3. Order: items i from 1 to n outside, capacities c from 0 to W inside.

4. Transition: leave item i, dp[i][c] = dp[i - 1][c]; if w[i] <= c, take it, dp[i][c] = max(dp[i][c], dp[i - 1][c - w[i]] + v[i]).

5. Answer: dp[n][W].

For item 3 and capacity 6, the transition gives dp[3][6] = max(dp[2][6], dp[2][2] + 7) = max(9, 10) = 10.

The input holds n and W, then one line per item with its weight and value. The program prints the best value and the items taken. For the 6 kg backpack the input is:

4 6
3 6
2 3
4 7
5 9

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n, W;
    cin >> n >> W;
    vector<int> w(n + 1), v(n + 1);
    for (int i = 1; i <= n; i++) cin >> w[i] >> v[i];

    // state: dp[i][c] = the best value from the first i items with capacity c
    // base case: dp[0][c] = 0, no items
    vector<vector<long long>> dp(n + 1, vector<long long>(W + 1, 0));

    // order: items one by one, every capacity
    for (int i = 1; i <= n; i++) {
        for (int c = 0; c <= W; c++) {
            // transition: leave item i
            dp[i][c] = dp[i - 1][c];
            // or take it, if it fits
            if (w[i] <= c) dp[i][c] = max(dp[i][c], dp[i - 1][c - w[i]] + v[i]);
        }
    }

    // answer
    cout << dp[n][W] << "\n";

    // restore the items; remove this block if you only need the value
    vector<int> taken;
    for (int i = n, c = W; i >= 1; i--) {
        if (dp[i][c] != dp[i - 1][c]) {   // item i was taken
            taken.push_back(i);
            c -= w[i];
        }
    }
    reverse(taken.begin(), taken.end());
    for (int i : taken) cout << i << " ";
    cout << "\n";
}

The time and the memory are both O(n \cdot W) (see time complexity). They grow with W: with 100 items and W up to 10^9, the table would have 10^{11} cells. The weights must be whole numbers, because they index columns; items of 1.5 kg and 2.5 kg need their weights doubled first.

Restoring the items

The restore block walks up from dp[n][W], one row per step, $O(n)$ in all. If dp[i][c] equals dp[i - 1][c], a best set exists without item i, so the walk leaves it. If they differ, the best value needed item i: the walk takes it and moves to c - w[i].

Fig. 5. The walk takes items 3 and 2, the blue set of Fig. 2.

On a tie the walk leaves the item. With a 5 kg backpack, row 1–4 ties at 9 (step 18 of Fig. 4): the walk leaves item 4, then item 3, and finds items 1 and 2, also worth 9.

One array

With 1000 items and W = 10^5, the table has 10^8 cells, 400 MB even as int, over a usual 128–256 MB limit. Each row reads only the row above, so one row best, updated in place, is enough. The time stays O(n \cdot W), and the memory drops to $O(W)$:

    vector<long long> best(W + 1, 0);      // base case: no items
    for (int i = 1; i <= n; i++)
        for (int c = W; c >= w[i]; c--)     // capacity downward
            best[c] = max(best[c], best[c - w[i]] + v[i]);
    cout << best[W] << "\n";                // answer

The loop runs downward because best[c - w[i]] lies to the left of best[c]. Going down, it isn't updated for item i yet, so it still holds the row above. Going up, it may already contain item i, and the line adds it again.

Going down, capacity 6 reads capacity 3, still 0: 0 + 6 = 6.

Capacity 5 reads capacity 2, still 0: 6.

Capacity 4 reads capacity 1, still 0: 6.

Capacity 3 reads capacity 0: 6. Every cell holds item 1 at most once.

Going up, capacity 3 reads capacity 0: 6.

Capacity 4 reads capacity 1, still 0: 6.

Capacity 5 reads capacity 2, still 0: 6.

Capacity 6 reads capacity 3, which already holds item 1: 6 + 6 = 12, item 1 twice.

1/8

Fig. 6. Step through both directions. The outlined cell is the one being read, with its value at that moment.

One array can't restore the items, so keep the table when they are needed.

Exact weight

When the items must weigh exactly W, starting every cell at 0 is wrong: with items of 3 kg worth 6 and 2 kg worth 3, the downward loop sets best[4] to best[1] + 6 = 6, though no set of them weighs 4 kg. The 0 in best[1] meant "nothing packed in 1 kg", not "exactly 1 kg".

So start best[0] at 0, the empty set, and every other cell at a mark NEG that means no set weighs exactly c. Never add to a cell that holds NEG: NEG + v[i] is no longer NEG, and the check for "impossible" at the end would miss it.

    const long long NEG = -1e18;           // no set weighs exactly c
    vector<long long> best(W + 1, NEG);
    best[0] = 0;                            // base case: the empty set
    for (int i = 1; i <= n; i++)
        for (int c = W; c >= w[i]; c--)
            if (best[c - w[i]] != NEG)
                best[c] = max(best[c], best[c - w[i]] + v[i]);
    if (best[W] == NEG) cout << "impossible\n";
    else cout << best[W] << "\n";

With the two items above, best[4] reads best[1] for item 1 and best[2] for item 2, and both are still NEG when read. So best[4] stays NEG: no set weighs exactly 4 kg.

Correctness proof

The table keeps an invariant: d_{i,c}, the number in dp[i][c], is the largest value of a set of the first $i$ items with total weight at most $c$.

For i = 0 only the empty set exists, worth 0. Let row i - 1 be correct, and take a best set for $i$ items and capacity $c$. Without item $i$, it is a set of the first i - 1 items within $c$, worth at most d_{i-1,c}. With item $i$, the rest fits in c - w_i, so the set is worth at most d_{i-1,c-w_i} + v_i. The transition takes the larger of the two, and both are values of real sets that fit, so d_{i,c} is the best. Taking reads row i - 1, so no item is counted twice.

Common mistakes

• Packing the most value per kilogram first. On the 6 kg backpack it packs 9, not 10 (Fig. 2); that rule works only when items can be cut.

• Swapping the loops in the one-array version, capacities outside. Then best[6] is finished before any smaller cell is filled, so it holds at most one item: the 6 kg backpack gets 9, item 4 alone. Keep the items outside.

Similar algorithms

Greedy algorithms solve the fractional knapsack, where items can be cut: the last item is cut to fit.

When W is up to 10^9, the table is too big. With at most about 20 items, try all 2^{20} sets with bitmasks or backtracking; with up to about 40, use meet in the middle.

Practice