0/1 knapsack: table to one row

The 0/1 knapsack problem hands you a bag that holds a fixed weight and a list of items, each with a weight and a value, and asks for the most valuable set of items that fits, with each item packed once or not at all: 0 or 1 copies of it, hence the name. No simple rule of thumb finds that set. Dynamic programming does, with one question per item: leave it out, or pack it and give up its weight. A table with one row per item and one column per capacity from 0 to W answers that question for every smaller bag on the way, in O(n·W) time for n items. Each row reads only the row above it, so a single row is enough, as long as the loop runs the capacity from high to low.

This lesson packs one bag every way there is: with greedy rules that fail, by trying every subset, and with the table, which it then walks back to find the items. It squeezes the table into one row, shows how turning one loop round solves a different problem instead, measures how the cost grows with the capacity, and ends with the code in five languages and five bugs, each with the smallest input that exposes it.

The problem: packing a trekking bag

The bag in the examples holds 10 kg, and five items are on the list:

Together they weigh 21 kg, so about half of the list stays at home, and the question is which half.

Greedy rules miss the best bag

The quick ideas all sort the list and pack every item that still fits: the most valuable first, the lightest first, or the most points per kilogram first. Here are all three, and then every one of the 32 possible subsets:

"""Three greedy rules for the trekking bag, then every subset of the five items."""
from itertools import combinations

ITEMS = [  # (name, weight in kg, value in points)
    ("stove", 3, 30),
    ("tent", 5, 55),
    ("rain gear", 2, 40),
    ("camera", 4, 35),
    ("food", 7, 80),
]
CAPACITY = 10


def pack_greedily(order):
    """Goes through the items in this order and takes each one that still fits."""
    taken, weight = [], 0
    for name, w, v in order:
        if weight + w <= CAPACITY:
            taken.append((name, w, v))
            weight += w
    return taken


def show(label, chosen):
    weight = sum(w for _, w, _ in chosen)
    value = sum(v for _, _, v in chosen)
    names = ", ".join(name for name, _, _ in chosen)
    print(f"{label:25} {value:3} points, {weight:2} kg: {names}")


show("highest value first", pack_greedily(sorted(ITEMS, key=lambda it: -it[2])))
show("lightest first", pack_greedily(sorted(ITEMS, key=lambda it: it[1])))
show("most points per kg first", pack_greedily(sorted(ITEMS, key=lambda it: -it[2] / it[1])))

# The brute force: every subset, the empty one included, kept if it fits and beats the best so far.
best, checked = (), 0
for k in range(len(ITEMS) + 1):
    for subset in combinations(ITEMS, k):
        checked += 1
        if sum(w for _, w, _ in subset) <= CAPACITY and sum(v for _, _, v in subset) > sum(v for _, _, v in best):
            best = subset
show(f"every subset ({checked})", best)

highest value first       120 points,  9 kg: food, rain gear
lightest first            105 points,  9 kg: rain gear, stove, camera
most points per kg first  120 points,  9 kg: rain gear, food
every subset (32)         125 points, 10 kg: stove, tent, rain gear

Each rule leaves points behind. Points per kilogram starts with the rain gear and the food, 9 kg and 120 points, and then nothing fits in the last kilogram. The best bag holds the stove, the tent and the rain gear, 125 points in exactly 10 kg, and it leaves out the food, the most valuable item on the list. Packing an item changes what the rest of the bag can hold, so whether an item belongs depends on everything else in the bag, which a rule that looks at one item at a time cannot see. The lesson on greedy proofs runs the same three rules on 10,000 random bags and counts how often each one fails. Points per kilogram is the right rule only when items can be cut, as in the fractional knapsack of NIST’s dictionary, where a part of an item is allowed.

The brute force: every subset

Each item is in or out, so n items give 2ⁿ subsets: 32 for the five above, and the program tried them all. That is the reference every faster version is checked against, and it is hopeless at the stated limits. A list of 100 items has 2¹⁰⁰, about 1.27 × 10³⁰, subsets. At a billion subsets a second, trying them would take about 4 × 10¹³ years.

The table: items by capacities

The way out is to ask a smaller question many times. Let best[i][c] be the most points that the first i items of the list can give in a bag of c kilograms. Item i (the i-th item, at position i − 1 of the list) is either left out or packed:

• Left out: the bag of c kilograms holds the best of the first i − 1 items, best[i − 1][c].
• Packed, if w[i] ≤ c: it takes w[i] kilograms and adds v[i] points, and the other c − w[i] kilograms hold the best of the first i − 1 items, best[i − 1][c − w[i]].

The second choice exists only when the item fits. Row 0, with no items, is 0 at every capacity, and the answer is best[n][W]. Why is that enough information? Once you have decided about the first i items, the rest of the problem depends on two numbers only: how many items are left to decide, and how many kilograms are still free. It does not matter which items took the space. Those two numbers are the state, and the lesson on recursion and dynamic programming prices such a table: (n + 1) × (W + 1) states with two choices each, so O(n·W) time.

The table for the trekking bag

The program fills the table one row at a time, then prints it with one row per item added:

"""The 0/1 knapsack table of the trekking bag, filled row by row, then walked back to the items it took."""
ITEMS = [  # (name, weight in kg, value in points)
    ("stove", 3, 30),
    ("tent", 5, 55),
    ("rain gear", 2, 40),
    ("camera", 4, 35),
    ("food", 7, 80),
]
CAPACITY = 10
n = len(ITEMS)

# best[i][c]: the most points from the first i items in a bag that holds c kg.
best = [[0] * (CAPACITY + 1) for _ in range(n + 1)]  # row 0: no items, 0 points at every capacity
for i in range(1, n + 1):
    name, w, v = ITEMS[i - 1]
    for c in range(CAPACITY + 1):
        best[i][c] = best[i - 1][c]  # skip item i: the best of the row above
        if w <= c and best[i - 1][c - w] + v > best[i][c]:
            best[i][c] = best[i - 1][c - w] + v  # take item i: w kg fewer for the first i - 1 items

print("capacity (kg)  " + "".join(f"{c:4}" for c in range(CAPACITY + 1)))
print("0 no items     " + "".join(f"{x:4}" for x in best[0]))
for i in range(1, n + 1):
    print(f"{i} + {ITEMS[i - 1][0]:11}" + "".join(f"{x:4}" for x in best[i]))

print(f"\nbest[{n}][{CAPACITY}] = {best[n][CAPACITY]} points. Walking back from it:")
c = CAPACITY
for i in range(n, 0, -1):
    name, w, v = ITEMS[i - 1]
    if best[i][c] == best[i - 1][c]:
        print(f"  row {i}, {c:2} kg: {best[i][c]:3} = the {best[i - 1][c]} above it, so the {name} was left out")
    else:
        print(f"  row {i}, {c:2} kg: {best[i][c]:3} > the {best[i - 1][c]} above it, so the {name} was packed: {c} - {w} = {c - w} kg left")
        c -= w

capacity (kg)     0   1   2   3   4   5   6   7   8   9  10
0 no items        0   0   0   0   0   0   0   0   0   0   0
1 + stove         0   0   0  30  30  30  30  30  30  30  30
2 + tent          0   0   0  30  30  55  55  55  85  85  85
3 + rain gear     0   0  40  40  40  70  70  95  95  95 125
4 + camera        0   0  40  40  40  70  75  95  95 105 125
5 + food          0   0  40  40  40  70  75  95  95 120 125

best[5][10] = 125 points. Walking back from it:
  row 5, 10 kg: 125 = the 125 above it, so the food was left out
  row 4, 10 kg: 125 = the 125 above it, so the camera was left out
  row 3, 10 kg: 125 > the 85 above it, so the rain gear was packed: 10 - 2 = 8 kg left
  row 2,  8 kg:  85 > the 30 above it, so the tent was packed: 8 - 5 = 3 kg left
  row 1,  3 kg:  30 > the 0 above it, so the stove was packed: 3 - 3 = 0 kg left

Read a few entries to see the two choices at work. In row 2 the bag of 8 kg holds 85 points, the stove and the tent together. In row 3, at 10 kg, packing the rain gear gives 85 + 40 = 125, because 8 kg are left for the first two items, against 85 without it. In row 4 the camera would give best[3][6] + 35, which is 70 + 35 = 105 at 10 kg, less than the 125 above it, so the entry stays 125. In row 5 the food is worth packing in a 9 kg bag, where 80 points plus the 40 that the remaining 2 kg give beat the 105 above, but not in the full 10 kg bag.

Walking back to the items

The table holds values, not items, but the items can be read back from it. Start at best[n][W] and look at the entry above it. If the two are equal, there is a best bag without item n, so leave it out and move up a row. If they differ, the entry could only have come from packing the item: record it, take its weight off c, and move up a row. The walk printed above leaves out the food and the camera, packs the rain gear and moves to 8 kg, packs the tent and moves to 3 kg, and ends with the stove at 0 kg. The walk makes n steps, one per row.

When both choices give the same value, the walk prefers leaving the item out. Any fixed rule would do, but fixing one makes the answer the same on every run and in every language, which is what lets a test compare it.

One row: the capacity runs downwards

Row i reads only row i − 1, so the rows before it can be thrown away. Better still, the table fits in one row, dp[c], updated in place for each item: dp[c] = max(dp[c], dp[c − w] + v). The catch is the second term. When dp[c] is updated, dp[c − w] must still hold its value from before this item, “without the item”, or the item can end up in the bag twice. Updating the capacities from high to low guarantees it: c − w is smaller than c, so its entry has not been touched yet in this item’s pass. The loop can stop at c = w, since smaller bags cannot hold the item.

"""The table squeezed into one row: capacities from high to low, then the same loop run from low to high by mistake."""
ITEMS = [  # (name, weight in kg, value in points)
    ("stove", 3, 30),
    ("tent", 5, 55),
    ("rain gear", 2, 40),
    ("camera", 4, 35),
    ("food", 7, 80),
]
CAPACITY = 10


def one_row(items, capacity, downwards):
    """Prints the row after each item; returns the last entry, the best for the whole bag."""
    dp = [0] * (capacity + 1)  # dp[c]: the most points in a bag of c kg from the items seen so far
    for name, w, v in items:
        # Downwards, dp[c - w] still holds the previous item's row when dp[c] reads it.
        capacities = range(capacity, w - 1, -1) if downwards else range(w, capacity + 1)
        for c in capacities:
            dp[c] = max(dp[c], dp[c - w] + v)
        print(f"  + {name:10}" + "".join(f"{x:4}" for x in dp))
    return dp[capacity]


print("capacity (kg)" + "".join(f"{c:4}" for c in range(CAPACITY + 1)))
print("from 10 kg down to w:")
print(f"  best = {one_row(ITEMS, CAPACITY, downwards=True)}")
print("from w up to 10 kg, by mistake:")
print(f"  best = {one_row(ITEMS, CAPACITY, downwards=False)}")

capacity (kg)   0   1   2   3   4   5   6   7   8   9  10
from 10 kg down to w:
  + stove        0   0   0  30  30  30  30  30  30  30  30
  + tent         0   0   0  30  30  55  55  55  85  85  85
  + rain gear    0   0  40  40  40  70  70  95  95  95 125
  + camera       0   0  40  40  40  70  75  95  95 105 125
  + food         0   0  40  40  40  70  75  95  95 120 125
  best = 125
from w up to 10 kg, by mistake:
  + stove        0   0   0  30  30  30  60  60  60  90  90
  + tent         0   0   0  30  30  55  60  60  85  90 110
  + rain gear    0   0  40  40  80  80 120 120 160 160 200
  + camera       0   0  40  40  80  80 120 120 160 160 200
  + food         0   0  40  40  80  80 120 120 160 160 200
  best = 200

Downwards, the row after each item is exactly the matching row of the full table, and the answer is 125. Upwards, the row goes wrong after the very first item: dp[6] becomes 60, two stoves, and dp[9] becomes 90, three of them. By the rain gear it reaches 200 at 10 kg, five rain gears in one bag. The upward loop is not a broken version of anything: it solves the unbounded knapsack, in which every item may be packed as many times as you like (NIST’s dictionary defines both problems). The difference between the two problems is only the direction of one loop, which is why mixing them up is a common and silent bug. A later lesson of this module uses the upward loop on purpose, for counting coins.

Getting the items back from one row

The single row keeps only the last row of the table, and the walk back needs every row. The usual fix keeps one mark per item and capacity: when item i raises dp[c] during its pass, mark took[i][c]. That is the same test as best[i][c] ≠ best[i − 1][c] in the full table, so the walk back reads the marks instead of the rows. The marks are one byte each in a Python bytearray: 100 items and capacities up to 10,000 come to about 1 MB, against about 8 MB for a table of Python integers, where each list entry is an 8-byte reference. The value row itself stays at W + 1 entries.

Why the one row is right

The loop over items keeps an invariant: after the pass of item i, dp[c] is the most value that a subset of the first i items can give within c kilograms, for every c from 0 to W.

1. Before any item, every entry is 0, and the empty subset gives exactly that.
2. The pass of item i. A best subset of the first i items within c kilograms either leaves item i out, and is then worth the old dp[c], or contains it, and then its other items form a subset of the first i − 1 items within c − w kilograms, worth at most the old dp[c − w]. Both values can be reached, so the larger of the two is the best. The downward order makes the pass read exactly those two old values.
3. After the last item, dp[W] is the answer for the whole list.

The lesson on dry runs and invariants argues other loops the same way. The invariant also says what an upward loop breaks: step 2 needs the old dp[c − w], and the upward loop reads the new one.

The cost, and why it is called pseudo-polynomial

The table has (n + 1) × (W + 1) entries and each costs a comparison and an addition, so the time is O(n·W). The one row needs O(W) memory, plus n·(W + 1) marks if the items are wanted. The program below times the value loop for the same 100 items as the capacity grows tenfold. It measures processor time, so other programs running at the same time matter less, but expect other numbers on your computer:

"""The one-row loop timed (processor time) for 100 items as the capacity grows tenfold, and what 10^9 would need."""
from time import process_time


def make_items(n):
    """n (weight, value) pairs from the Park-Miller generator, weights 1 to 400 and values 1 to 1,000."""
    x, items = 2026, []
    for _ in range(n):
        x = x * 48271 % 2147483647
        w = 1 + x % 400
        x = x * 48271 % 2147483647
        items.append((w, 1 + x % 1000))
    return items


def best_value(items, capacity):
    dp = [0] * (capacity + 1)
    updates = 0
    for w, v in items:
        for c in range(capacity, w - 1, -1):
            if dp[c - w] + v > dp[c]:
                dp[c] = dp[c - w] + v
        updates += max(0, capacity - w + 1)
    return dp[capacity], updates


items = make_items(100)
for capacity in (1_000, 10_000, 100_000):
    start = process_time()
    value, updates = best_value(items, capacity)
    ms = (process_time() - start) * 1000
    print(f"capacity {capacity:>7,}: {updates:>10,} entries visited, {ms:8.1f} ms")
print(f"capacity 10^9 would visit about {100 * 10**9:,} entries, and its row alone would hold {10**9 + 1:,}")

capacity   1,000:     79,672 entries visited,      6.0 ms
capacity  10,000:    979,672 entries visited,    101.8 ms
capacity 100,000:  9,979,672 entries visited,   1173.2 ms
capacity 10^9 would visit about 100,000,000,000 entries, and its row alone would hold 1,000,000,001

The work grows with the capacity, not with the size of the input. In the recorded run, CPython took a few milliseconds at 1,000 kg, about a tenth of a second at 10,000 and over a second at 100,000, roughly a tenth of a microsecond per entry. A capacity of 10⁹ would need 10¹¹ entries: hours in CPython and minutes even in compiled code, with a row of a billion entries to hold.

That is the sense of pseudo-polynomial. Writing W down takes only about log₂ W bits, so each extra decimal digit in W makes the input one character longer and the work ten times larger: the running time is a polynomial in the value of W, not in the length of the input. Garey and Johnson named such algorithms pseudo-polynomial, with knapsack among their examples. The decision version of knapsack, whether some subset reaches a given value, is NP-complete (it is among Karp’s problems, and NIST’s dictionary says so too), so no algorithm whose time is polynomial in the length of the input is known. In a coding round, multiply n by W and hold the product against the step budgets of the constraints lesson: roughly ten million simple steps per second for Python, a hundred million for compiled languages.

When the capacity is huge and the values are small

Sometimes the weights are enormous and the values are not: files of a few gigabytes each on a backup disk, scored by a priority from 1 to 40. The capacity row would need billions of entries, but the values add up to a few hundred. Swap the roles: let lightest[p] be the fewest bytes that reach exactly p points, start it at 0 for p = 0 and infinity elsewhere, and update it for each file with the same downward loop over p. The answer is the largest p whose lightest[p] fits on the disk.

"""Huge weights, small values: index the row by value and keep the lightest way to reach each value."""
from itertools import combinations

FILES = [  # (name, size in bytes, priority points)
    ("photos-2019", 1_850_000_000, 34),
    ("thesis", 420_000_000, 40),
    ("music", 2_300_000_000, 18),
    ("videos-trip", 3_100_000_000, 29),
    ("mail-archive", 960_000_000, 21),
    ("code", 150_000_000, 25),
    ("scans", 1_200_000_000, 12),
    ("games", 2_700_000_000, 6),
]
FREE = 4_700_000_000  # bytes free on the backup disk

total = sum(p for _, _, p in FILES)
INF = float("inf")
lightest = [0] + [INF] * total  # lightest[p]: the fewest bytes that reach exactly p points
for _, size, p in FILES:
    for q in range(total, p - 1, -1):  # downwards, as in the capacity row: each file at most once
        if lightest[q - p] + size < lightest[q]:
            lightest[q] = lightest[q - p] + size
best = max(p for p in range(total + 1) if lightest[p] <= FREE)
print(f"a row indexed by bytes would need {FREE + 1:,} entries; indexed by points it needs {total + 1}")
print(f"best: {best} points in {lightest[best]:,} bytes")

brute = max(sum(p for _, _, p in s) for k in range(len(FILES) + 1) for s in combinations(FILES, k) if sum(b for _, b, _ in s) <= FREE)
print(f"every subset of the {len(FILES)} files agrees: {brute == best}")

a row indexed by bytes would need 4,700,000,001 entries; indexed by points it needs 186
best: 132 points in 4,580,000,000 bytes
every subset of the 8 files agrees: True

The value row has 186 entries where the capacity row would have 4,700,000,001, and it finds 132 points in 4,580,000,000 bytes, which every subset of the eight files confirms. The cost is O(n·V) for a total value V. When the weights and the values are both large and the list is short, about 40 items, splitting the list into two halves, listing the subsets of each half and combining them is the usual way out.

The code in five languages

Here is best_bag(items, capacity), the one row with its marks, returning the best value and the indices of one best set. The Python and JavaScript tabs can be run right here; for the three compiled languages, the recorded session after them shows each build and its output.

"""0/1 knapsack in one row of values, with one row of "took it" marks per item to recover the chosen items."""


def best_bag(items, capacity):
    """items: (weight, value) pairs. Returns the best total value and the indices of one best set, in order."""
    dp = [0] * (capacity + 1)  # dp[c]: the best value in a bag of c from the items seen so far
    took = []  # took[i][c] == 1: item i improved dp[c], so the best set for (i, c) contains it
    for w, v in items:
        mark = bytearray(capacity + 1)
        for c in range(capacity, w - 1, -1):  # downwards: dp[c - w] is still the previous item's value
            if dp[c - w] + v > dp[c]:
                dp[c] = dp[c - w] + v
                mark[c] = 1
        took.append(mark)
    chosen, c = [], capacity
    for i in range(len(items) - 1, -1, -1):  # walk back from the last item and the full bag
        if took[i][c]:
            chosen.append(i)
            c -= items[i][0]
    return dp[capacity], chosen[::-1]


def make_items(n):
    """n (weight, value) pairs from the Park-Miller generator, the same in every language."""
    x, items = 2026, []
    for _ in range(n):
        x = x * 48271 % 2147483647
        w = 1 + x % 400
        x = x * 48271 % 2147483647
        items.append((w, 1 + x % 1000))
    return items


trek = [(3, 30), (5, 55), (2, 40), (4, 35), (7, 80)]  # stove, tent, rain gear, camera, food
print("trek, 10 kg:", best_bag(trek, 10))
print("trek, 0 kg:", best_bag(trek, 0))
print("one item heavier than the bag:", best_bag([(12, 100)], 10))
big = make_items(100)
value, chosen = best_bag(big, 10_000)
print(f"100 items, capacity 10000: value {value}, {len(chosen)} items, weight {sum(big[i][0] for i in chosen)}")

trek, 10 kg: (125, [0, 1, 2])
trek, 0 kg: (0, [])
one item heavier than the bag: (0, [])
100 items, capacity 10000: value 39537, 62 items, weight 9983

// 0/1 knapsack in one row of values, with one row of "took it" marks per item to recover the chosen items.

// items: [weight, value] pairs. Returns the best total value and the indices of one best set, in order.
function bestBag(items, capacity) {
  const dp = new Array(capacity + 1).fill(0); // dp[c]: the best value in a bag of c from the items seen so far
  const took = []; // took[i][c] === 1: item i improved dp[c], so the best set for (i, c) contains it
  for (const [w, v] of items) {
    const mark = new Uint8Array(capacity + 1);
    for (let c = capacity; c >= w; c--) {
      // downwards: dp[c - w] is still the previous item's value
      if (dp[c - w] + v > dp[c]) {
        dp[c] = dp[c - w] + v;
        mark[c] = 1;
      }
    }
    took.push(mark);
  }
  const chosen = [];
  let c = capacity;
  for (let i = items.length - 1; i >= 0; i--) {
    // walk back from the last item and the full bag
    if (took[i][c]) {
      chosen.push(i);
      c -= items[i][0];
    }
  }
  return [dp[capacity], chosen.reverse()];
}

// n [weight, value] pairs from the Park-Miller generator, the same in every language.
function makeItems(n) {
  let x = 2026;
  const items = [];
  for (let k = 0; k < n; k++) {
    x = (x * 48271) % 2147483647; // below 2 ** 47, so the product is exact in a JavaScript number
    const w = 1 + (x % 400);
    x = (x * 48271) % 2147483647;
    items.push([w, 1 + (x % 1000)]);
  }
  return items;
}

const show = ([value, chosen]) => `(${value}, [${chosen.join(', ')}])`;
const trek = [[3, 30], [5, 55], [2, 40], [4, 35], [7, 80]]; // stove, tent, rain gear, camera, food
console.log('trek, 10 kg:', show(bestBag(trek, 10)));
console.log('trek, 0 kg:', show(bestBag(trek, 0)));
console.log('one item heavier than the bag:', show(bestBag([[12, 100]], 10)));
const big = makeItems(100);
const [value, chosen] = bestBag(big, 10_000);
const weight = chosen.reduce((sum, i) => sum + big[i][0], 0);
console.log(`100 items, capacity 10000: value ${value}, ${chosen.length} items, weight ${weight}`);

trek, 10 kg: (125, [0, 1, 2])
trek, 0 kg: (0, [])
one item heavier than the bag: (0, [])
100 items, capacity 10000: value 39537, 62 items, weight 9983

// 0/1 knapsack in one row of values, with one row of "took it" marks per item to recover the chosen items.
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class BestBag {
    record Result(int value, List<Integer> chosen) {
        @Override
        public String toString() {
            return "(" + value + ", " + chosen + ")";
        }
    }

    // items[i] = {weight, value}. Returns the best total value and the indices of one best set, in order.
    static Result bestBag(int[][] items, int capacity) {
        int[] dp = new int[capacity + 1]; // dp[c]: the best value in a bag of c from the items seen so far
        boolean[][] took = new boolean[items.length][capacity + 1];
        for (int i = 0; i < items.length; i++) {
            int w = items[i][0], v = items[i][1];
            for (int c = capacity; c >= w; c--) { // downwards: dp[c - w] is still the previous item's value
                if (dp[c - w] + v > dp[c]) {
                    dp[c] = dp[c - w] + v;
                    took[i][c] = true;
                }
            }
        }
        List<Integer> chosen = new ArrayList<>();
        int c = capacity;
        for (int i = items.length - 1; i >= 0; i--) { // walk back from the last item and the full bag
            if (took[i][c]) {
                chosen.add(i);
                c -= items[i][0];
            }
        }
        Collections.reverse(chosen);
        return new Result(dp[capacity], chosen);
    }

    // n {weight, value} pairs from the Park-Miller generator, the same in every language.
    static int[][] makeItems(int n) {
        long x = 2026;
        int[][] items = new int[n][];
        for (int k = 0; k < n; k++) {
            x = x * 48271 % 2147483647; // the product needs a long: it can reach about 2^47
            int w = (int) (1 + x % 400);
            x = x * 48271 % 2147483647;
            items[k] = new int[] {w, (int) (1 + x % 1000)};
        }
        return items;
    }

    public static void main(String[] args) {
        int[][] trek = {{3, 30}, {5, 55}, {2, 40}, {4, 35}, {7, 80}}; // stove, tent, rain gear, camera, food
        System.out.println("trek, 10 kg: " + bestBag(trek, 10));
        System.out.println("trek, 0 kg: " + bestBag(trek, 0));
        System.out.println("one item heavier than the bag: " + bestBag(new int[][] {{12, 100}}, 10));
        int[][] big = makeItems(100);
        Result r = bestBag(big, 10_000);
        int weight = 0;
        for (int i : r.chosen()) weight += big[i][0];
        System.out.println("100 items, capacity 10000: value " + r.value() + ", " + r.chosen().size() + " items, weight " + weight);
    }
}

// 0/1 knapsack in one row of values, with one row of "took it" marks per item to recover the chosen items.
#include <algorithm>
#include <cstdint>
#include <print>
#include <string>
#include <utility>
#include <vector>

struct Item {
    int weight, value;
};

// Returns the best total value and the indices of one best set, in order.
std::pair<int, std::vector<int>> best_bag(const std::vector<Item>& items, int capacity) {
    std::vector<int> dp(capacity + 1, 0);  // dp[c]: the best value in a bag of c from the items seen so far
    std::vector<std::vector<char>> took(items.size(), std::vector<char>(capacity + 1, 0));
    for (std::size_t i = 0; i < items.size(); i++) {
        auto [w, v] = items[i];
        for (int c = capacity; c >= w; c--) {  // downwards: dp[c - w] is still the previous item's value
            if (dp[c - w] + v > dp[c]) {
                dp[c] = dp[c - w] + v;
                took[i][c] = 1;
            }
        }
    }
    std::vector<int> chosen;
    int c = capacity;
    for (int i = static_cast<int>(items.size()) - 1; i >= 0; i--) {  // walk back from the last item and the full bag
        if (took[i][c]) {
            chosen.push_back(i);
            c -= items[i].weight;
        }
    }
    std::ranges::reverse(chosen);
    return {dp[capacity], chosen};
}

// n {weight, value} pairs from the Park-Miller generator, the same in every language.
std::vector<Item> make_items(int n) {
    std::int64_t x = 2026;  // the product can reach about 2^47, so it needs 64 bits
    std::vector<Item> items;
    for (int k = 0; k < n; k++) {
        x = x * 48271 % 2147483647;
        int w = static_cast<int>(1 + x % 400);
        x = x * 48271 % 2147483647;
        items.push_back({w, static_cast<int>(1 + x % 1000)});
    }
    return items;
}

std::string show(const std::pair<int, std::vector<int>>& r) {
    std::string out = "(" + std::to_string(r.first) + ", [";
    for (std::size_t k = 0; k < r.second.size(); k++) out += (k ? ", " : "") + std::to_string(r.second[k]);
    return out + "])";
}

int main() {
    std::vector<Item> trek = {{3, 30}, {5, 55}, {2, 40}, {4, 35}, {7, 80}};  // stove, tent, rain gear, camera, food
    std::println("trek, 10 kg: {}", show(best_bag(trek, 10)));
    std::println("trek, 0 kg: {}", show(best_bag(trek, 0)));
    std::println("one item heavier than the bag: {}", show(best_bag({{12, 100}}, 10)));
    auto big = make_items(100);
    auto [value, chosen] = best_bag(big, 10'000);
    int weight = 0;
    for (int i : chosen) weight += big[i].weight;
    std::println("100 items, capacity 10000: value {}, {} items, weight {}", value, chosen.size(), weight);
}

// 0/1 knapsack in one row of values, with one row of "took it" marks per item to recover the chosen items.
package main

import (
	"fmt"
	"slices"
	"strconv"
	"strings"
)

type item struct{ weight, value int }

// bestBag returns the best total value and the indices of one best set, in order.
func bestBag(items []item, capacity int) (int, []int) {
	dp := make([]int, capacity+1) // dp[c]: the best value in a bag of c from the items seen so far
	took := make([][]bool, len(items))
	for i, it := range items {
		took[i] = make([]bool, capacity+1)
		for c := capacity; c >= it.weight; c-- { // downwards: dp[c - w] is still the previous item's value
			if dp[c-it.weight]+it.value > dp[c] {
				dp[c] = dp[c-it.weight] + it.value
				took[i][c] = true
			}
		}
	}
	chosen := []int{}
	c := capacity
	for i := len(items) - 1; i >= 0; i-- { // walk back from the last item and the full bag
		if took[i][c] {
			chosen = append(chosen, i)
			c -= items[i].weight
		}
	}
	slices.Reverse(chosen)
	return dp[capacity], chosen
}

// makeItems returns n {weight, value} pairs from the Park-Miller generator, the same in every language.
func makeItems(n int) []item {
	var x int64 = 2026 // the product can reach about 2^47, so it needs 64 bits on every platform
	items := []item{}
	for k := 0; k < n; k++ {
		x = x * 48271 % 2147483647
		w := int(1 + x%400)
		x = x * 48271 % 2147483647
		items = append(items, item{w, int(1 + x%1000)})
	}
	return items
}

func show(value int, chosen []int) string {
	parts := make([]string, len(chosen))
	for k, i := range chosen {
		parts[k] = strconv.Itoa(i)
	}
	return fmt.Sprintf("(%d, [%s])", value, strings.Join(parts, ", "))
}

func main() {
	trek := []item{{3, 30}, {5, 55}, {2, 40}, {4, 35}, {7, 80}} // stove, tent, rain gear, camera, food
	fmt.Println("trek, 10 kg:", show(bestBag(trek, 10)))
	fmt.Println("trek, 0 kg:", show(bestBag(trek, 0)))
	fmt.Println("one item heavier than the bag:", show(bestBag([]item{{12, 100}}, 10)))
	big := makeItems(100)
	value, chosen := bestBag(big, 10_000)
	weight := 0
	for _, i := range chosen {
		weight += big[i].weight
	}
	fmt.Printf("100 items, capacity 10000: value %d, %d items, weight %d\n", value, len(chosen), weight)
}

from session import run, versions

# best_bag in Java, C++ (built with the sanitizers on) and Go, each on the same four bags.
versions("java -version", "clang++ --version", "go version")
run("""
java BestBag.java
clang++ -std=c++23 -Wall -Wextra -fsanitize=address,undefined best_bag.cpp -o best_bag && ./best_bag
go run best_bag.go
""")

# openjdk version "25.0.4.1" LTS
# Apple clang version 21.0.0 (clang-2100.3.34.2)
# go version go1.27.1 darwin/arm64
$ java BestBag.java
trek, 10 kg: (125, [0, 1, 2])
trek, 0 kg: (0, [])
one item heavier than the bag: (0, [])
100 items, capacity 10000: value 39537, 62 items, weight 9983
$ clang++ -std=c++23 -Wall -Wextra -fsanitize=address,undefined best_bag.cpp -o best_bag && ./best_bag
trek, 10 kg: (125, [0, 1, 2])
trek, 0 kg: (0, [])
one item heavier than the bag: (0, [])
100 items, capacity 10000: value 39537, 62 items, weight 9983
$ go run best_bag.go
trek, 10 kg: (125, [0, 1, 2])
trek, 0 kg: (0, [])
one item heavier than the bag: (0, [])
100 items, capacity 10000: value 39537, 62 items, weight 9983

All five print the same four lines. The last one packs 62 of 100 generated items, 9,983 kg of a 10,000 kg capacity, for 39,537 points. The items come from the minimal standard generator of Park, Miller and Stockmeyer, x = x · 48,271 mod (2³¹ − 1), which C++ also provides as std::minstd_rand, so every language works on the same list. A few things differ between the languages:

• The values fit anywhere. At most 100 items of 1,000 points make 100,000, far below 2,147,483,647, the top of Java’s 32-bit int according to its language specification.
• The generator does not. x · 48,271 reaches about 2⁴⁷, so Java, C++ and Go keep x in 64 bits. JavaScript numbers hold every integer up to Number.MAX_SAFE_INTEGER, 2⁵³ − 1, exactly, so the product is exact there, and Go’s int64 is written out because a plain int has 32 bits on some platforms, by the Go specification.
• The marks are a bytearray per item in Python, a Uint8Array in JavaScript and booleans in Java and Go. C++ uses char, one byte per mark.
• The builds: Java is started straight from its source file, a launcher feature since JEP 330. The C++ binary is compiled with two Clang sanitizers, AddressSanitizer for memory errors and UndefinedBehaviorSanitizer for undefined operations; an index outside a row would have been reported, and nothing was.

Check it against every subset

"""best_bag against every subset on 2,000 random bags, and a check that each set it returns is a real answer."""
import random
from itertools import combinations


def best_bag(items, capacity):
    dp = [0] * (capacity + 1)
    took = []
    for w, v in items:
        mark = bytearray(capacity + 1)
        for c in range(capacity, w - 1, -1):
            if dp[c - w] + v > dp[c]:
                dp[c] = dp[c - w] + v
                mark[c] = 1
        took.append(mark)
    chosen, c = [], capacity
    for i in range(len(items) - 1, -1, -1):
        if took[i][c]:
            chosen.append(i)
            c -= items[i][0]
    return dp[capacity], chosen[::-1]


def every_subset(items, capacity):
    """The brute force: the best value over all 2^n subsets that fit."""
    best = 0
    for k in range(len(items) + 1):
        for subset in combinations(items, k):
            if sum(w for w, _ in subset) <= capacity:
                best = max(best, sum(v for _, v in subset))
    return best


rng = random.Random(7)
bags = []
for _ in range(2000):
    n = rng.randint(0, 10)
    items = [(rng.randint(1, 12), rng.randint(1, 30)) for _ in range(n)]
    bags.append((items, rng.randint(0, 40)))

wrong = 0
for items, capacity in bags:
    value, chosen = best_bag(items, capacity)
    real = (
        chosen == sorted(set(chosen))  # each item at most once, in order
        and sum(items[i][0] for i in chosen) <= capacity  # it fits
        and sum(items[i][1] for i in chosen) == value  # it is worth what is claimed
    )
    if value != every_subset(items, capacity) or not real:
        wrong += 1
print(f"{len(bags)} random bags of up to 10 items: {wrong} wrong")
print("bags with capacity 0:", sum(c == 0 for _, c in bags), "| bags where nothing fits:",
      sum(best_bag(i, c)[0] == 0 and len(i) > 0 for i, c in bags))
print("items heavier than the whole bag:", sum(w > c for i, c in bags for w, _ in i))

2000 random bags of up to 10 items: 0 wrong
bags with capacity 0: 38 | bags where nothing fits: 124
items heavier than the whole bag: 1645

The check compares the value with the brute force on 2,000 random bags of up to 10 items, including 38 bags with no capacity at all, 124 in which nothing fits and 1,645 items heavier than their whole bag. It also checks that the set returned is a real answer: each index once and in order, a total weight within the capacity, and a total value equal to the value claimed. A function can return the right number and the wrong items, and only a check of the set catches that. The lesson on stress testing builds such checks step by step.

Edge cases and common bugs

Each of these five changes looks reasonable, and each one is wrong. The drill runs them against the brute force on every bag of up to three small items, fewest items and smallest bag first, and prints the first bag that each one gets wrong:

"""Five plausible bugs, each run against the brute force on every bag of up to 3 items (weights and values 1 to 3,
capacities 0 to 4), fewest items and smallest capacity first, until it fails. The first failure is a smallest input
that shows the bug."""
from itertools import combinations, product


def every_subset(items, capacity):
    return max(sum(v for _, v in s) for k in range(len(items) + 1) for s in combinations(items, k) if sum(w for w, _ in s) <= capacity)


def upwards(items, capacity):  # one row, capacities from w up to the capacity
    dp = [0] * (capacity + 1)
    for w, v in items:
        for c in range(w, capacity + 1):
            dp[c] = max(dp[c], dp[c - w] + v)
    return dp[capacity]


def shared_rows(items, capacity):  # the table made with [[0] * (capacity + 1)] * (n + 1): one list, n + 1 times
    best = [[0] * (capacity + 1)] * (len(items) + 1)
    for i, (w, v) in enumerate(items, start=1):
        for c in range(capacity + 1):
            best[i][c] = best[i - 1][c]
            if w <= c:
                best[i][c] = max(best[i][c], best[i - 1][c - w] + v)
    return best[len(items)][capacity]


def no_guard(items, capacity):  # one row, downwards, but over every capacity, even those below w
    dp = [0] * (capacity + 1)
    for w, v in items:
        for c in range(capacity, -1, -1):
            dp[c] = max(dp[c], dp[c - w] + v)  # c - w < 0 reads dp[-1], dp[-2] … from the far end
    return dp[capacity]


def exact_start(items, capacity):  # starts every entry but dp[0] at minus infinity, as for "weighs exactly c"
    dp = [0] + [float("-inf")] * capacity
    for w, v in items:
        for c in range(capacity, w - 1, -1):
            dp[c] = max(dp[c], dp[c - w] + v)
    return dp[capacity]


def forward_walk(items, capacity):  # the right table, but the items are read back from the first row onwards
    n = len(items)
    best = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i, (w, v) in enumerate(items, start=1):
        for c in range(capacity + 1):
            best[i][c] = max(best[i - 1][c], best[i - 1][c - w] + v) if w <= c else best[i - 1][c]
    c, value = capacity, 0
    for i, (w, v) in enumerate(items, start=1):
        if best[i][c] != best[i - 1][c]:
            value += v  # the value of the set it returns
            c -= w
    return value


def bags():
    for n in range(4):
        for capacity in range(5):
            for flat in product(range(1, 4), repeat=2 * n):
                yield [(flat[2 * k], flat[2 * k + 1]) for k in range(n)], capacity


for bug in (upwards, shared_rows, no_guard, exact_start, forward_walk):
    for items, capacity in bags():
        got, right = bug(items, capacity), every_subset(items, capacity)
        if got != right:
            print(f"{bug.__name__:12} items {items}, capacity {capacity}: {got}, not {right}")
            break
    else:
        print(f"{bug.__name__:12} passed every bag")

upwards      items [(1, 1)], capacity 2: 2, not 1
shared_rows  items [(1, 1)], capacity 2: 2, not 1
no_guard     items [(1, 1)], capacity 0: 1, not 0
exact_start  items [], capacity 1: -inf, not 0
forward_walk items [(1, 1), (1, 2)], capacity 1: 1, not 2

• The capacity loop runs upwards. One item of 1 kg worth 1 point in a 2 kg bag gives 2: the item is packed twice.
• The rows of the table are one list. [[0] * (W + 1)] * (n + 1) builds a list that holds the same row n + 1 times, as the Python FAQ warns: * copies references, not lists. The “row above” is then the row being filled, and the table behaves like the upward loop.
• No w ≤ c guard. For c < w the index c − w is negative, and Python reads dp[-1], dp[-2] and so on from the far end of the list without any error, because a negative index counts from the end. A 1 kg item in a bag of 0 kg then scores a point. In Java the same bug throws an exception, and in C++ it reads outside the vector, which is undefined behaviour.
• The row starts at minus infinity. Starting every entry but dp[0] at −∞ answers a different question, the best value of a bag filled to exactly c kilograms. It is the right start when the bag must be full; for “at most W” it returns −∞ whenever no subset weighs exactly W, even for an empty list.
• The walk back starts at the first item. Reading the items from row 1 onwards judges each item against the full bag, before the later items have had their say. With items of 1 kg worth 1 and 1 kg worth 2 in a 1 kg bag, it packs the first and returns a set worth 1, not 2.

Three cases need no special code but deserve a test each: a capacity of 0, where the answer is 0 and no items; an item heavier than the whole bag, whose downward loop is empty, so it is never packed; and an empty list.

Exercise

best_bag([(3, 30), (5, 55), (2, 40), (4, 35), (7, 80)], 10)  # (125, [0, 1, 2])
best_bag([(3, 30)], 0)                                       # (0, [])
best_bag([(11, 50), (4, 7)], 10)                             # (7, [1]): the first item never fits

def best_bag(items, capacity):
    """The largest total value of items (each used at most once) within capacity, and the positions of one such set."""
    # Replace this line with your code.
    return 0, []

import random
from itertools import combinations

from bag import best_bag


def brute(items, capacity):
    """The best value over every subset (small lists only)."""
    best = 0
    for k in range(len(items) + 1):
        for subset in combinations(items, k):
            if sum(w for w, _ in subset) <= capacity:
                best = max(best, sum(v for _, v in subset))
    return best


def check(items, capacity, value):
    """best_bag's answer has the expected value, and its set is a real set of items that reaches it."""
    got = best_bag(items, capacity)
    assert isinstance(got, tuple) and len(got) == 2, "return a pair (value, chosen)"
    got_value, chosen = got
    assert got_value == value, f"value {got_value}, expected {value}"
    assert list(chosen) == sorted(set(chosen)), f"positions {chosen}: each item once, in increasing order"
    assert all(0 <= i < len(items) for i in chosen), f"positions {chosen} are not all positions of items"
    assert sum(items[i][0] for i in chosen) <= capacity, f"the set {chosen} weighs more than {capacity}"
    assert sum(items[i][1] for i in chosen) == value, f"the set {chosen} is not worth {value}"


def test_the_trekking_bag():
    """the five items of the lesson in a 10 kg bag: the stove, the tent and the rain gear"""
    assert best_bag([(3, 30), (5, 55), (2, 40), (4, 35), (7, 80)], 10) == (125, [0, 1, 2])


def test_an_empty_bag_and_an_empty_list():
    """capacity 0 packs nothing, and so does an empty list of items"""
    assert best_bag([(3, 30), (1, 9)], 0) == (0, [])
    assert best_bag([], 25) == (0, [])


def test_items_heavier_than_the_bag():
    """an item that never fits is never packed"""
    assert best_bag([(11, 50), (12, 70)], 10) == (0, [])
    assert best_bag([(11, 50), (4, 7)], 10) == (7, [1])


def test_each_item_at_most_once():
    """one light, valuable item in a large bag is packed once, not five times"""
    assert best_bag([(1, 10)], 5) == (10, [0])
    check([(2, 40), (3, 20)], 10, 60)


def test_random_bags_against_every_subset():
    """600 random bags of up to 9 items, checked against every subset"""
    rng = random.Random(41)
    for _ in range(600):
        items = [(rng.randint(1, 15), rng.randint(1, 50)) for _ in range(rng.randint(0, 9))]
        capacity = rng.randint(0, 45)
        check(items, capacity, brute(items, capacity))


def test_a_hundred_items_and_a_capacity_of_ten_thousand():
    """100 items from a fixed generator in a capacity of 10,000: too many subsets to try"""
    x, items = 2026, []
    for _ in range(100):
        x = x * 48271 % 2147483647
        w = 1 + x % 400
        x = x * 48271 % 2147483647
        items.append((w, 1 + x % 1000))
    check(items, 10_000, 39_537)

Interview questions

Fresher · Why does the one-row 0/1 knapsack loop run the capacity downwards?

Because the update dp[c] = max(dp[c], dp[c − w] + v) must read dp[c − w] as it was before the current item. In the full table that value is best[i − 1][c − w], the best bag without item i. Going from high to low, every capacity below c is still untouched when dp[c] is computed, so the item can be added at most once. Going from low to high, dp[c − w] may already include the item, so it can be packed again and again: that loop solves the unbounded knapsack, where every item may be used any number of times. On a 10 kg bag with a 2 kg item worth 40 points, the upward loop reports 200 points: five copies of one item.

Fresher · Is the O(n·W) knapsack algorithm polynomial?

Not in the length of the input, which is why it is called pseudo-polynomial. The capacity W is a number, and writing it down takes about log₂ W bits, so adding one decimal digit to W makes the input one character longer and the table ten times larger. The running time is a polynomial in n and in the value of W. That is fine when W is small, about 10⁴ or 10⁵, and hopeless when W is 10⁹. The decision version of knapsack is NP-complete, so no algorithm that is polynomial in the input length is known. When the capacity is huge but the values are small, index the table by value instead.

Key takeaways

• 0/1 knapsack chooses each item at most once; greedy rules fail on it, and trying every subset costs 2ⁿ.
• best[i][c] is the larger of best[i − 1][c] (leave item i out) and best[i − 1][c − w[i]] + v[i] (pack it, if it fits). The answer is best[n][W], in O(n·W) time.
• Walk back from best[n][W]: an entry that differs from the one above it means the item was packed.
• One row is enough if the capacity runs downwards. Upwards, the same loop solves the unbounded knapsack instead.
• To recover the items from one row, keep one mark per item and capacity.
• O(n·W) is pseudo-polynomial: fine for W up to about 10⁵, hopeless for 10⁹. With small values, index by value.