Knapsack in Python, Java and TypeScript

The two-dimensional table, then the same answer from one array filled from the top capacity down.

A 0/1 knapsack can be written with the full table of items by capacities or with a single array of capacities, and the listings below give both in each language. Each solves the three parcels from Fill the Knapsack Table One Item at a Time and fifteen generated items with a capacity of 30, whose weights and values come from (i × 7) mod 9 + 1 and (i × 11) mod 13 + 1 so the run repeats exactly.

0/1 knapsack with a table and with one array, in each language

knapsack_code.pypy

def best_with_table(items: list[tuple[int, int]], capacity: int) -> int:
    best = [[0] * (capacity + 1) for _ in range(len(items) + 1)]
    for i, (weight, value) in enumerate(items, start=1):
        for c in range(capacity + 1):
            best[i][c] = best[i - 1][c]
            if weight <= c:
                best[i][c] = max(best[i][c], best[i - 1][c - weight] + value)
    return best[len(items)][capacity]


def best_with_one_array(items: list[tuple[int, int]], capacity: int) -> int:
    best = [0] * (capacity + 1)
    for weight, value in items:
        for c in range(capacity, weight - 1, -1):
            best[c] = max(best[c], best[c - weight] + value)
    return best[capacity]


small = [(2, 3), (3, 5), (4, 6)]
larger = [((i * 7) % 9 + 1, (i * 11) % 13 + 1) for i in range(15)]
for name, items, capacity in (("3 items, capacity 6", small, 6), ("15 items, capacity 30", larger, 30)):
    print(f"{name}: table {best_with_table(items, capacity)}, one array {best_with_one_array(items, capacity)}")

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

3 items, capacity 6: table 9, one array 9
15 items, capacity 30: table 70, one array 70

KnapsackCode.javajava

import java.util.stream.IntStream;

public class KnapsackCode {
    static int bestWithTable(int[][] items, int capacity) {
        int[][] best = new int[items.length + 1][capacity + 1];
        for (int i = 1; i <= items.length; i++) {
            int weight = items[i - 1][0];
            int value = items[i - 1][1];
            for (int c = 0; c <= capacity; c++) {
                best[i][c] = best[i - 1][c];
                if (weight <= c) {
                    best[i][c] = Math.max(best[i][c], best[i - 1][c - weight] + value);
                }
            }
        }
        return best[items.length][capacity];
    }

    static int bestWithOneArray(int[][] items, int capacity) {
        int[] best = new int[capacity + 1];
        for (int[] item : items) {
            for (int c = capacity; c >= item[0]; c--) {
                best[c] = Math.max(best[c], best[c - item[0]] + item[1]);
            }
        }
        return best[capacity];
    }

    public static void main(String[] args) {
        int[][] small = {{2, 3}, {3, 5}, {4, 6}};
        int[][] larger = IntStream.range(0, 15).mapToObj(i -> new int[] {(i * 7) % 9 + 1, (i * 11) % 13 + 1}).toArray(int[][]::new);
        System.out.println("3 items, capacity 6: table " + bestWithTable(small, 6) + ", one array " + bestWithOneArray(small, 6));
        System.out.println("15 items, capacity 30: table " + bestWithTable(larger, 30) + ", one array " + bestWithOneArray(larger, 30));
    }
}

OutputRan with eclipse-temurin:25.0.4.1_1-jdk-noble (Java 25.0.4.1)

3 items, capacity 6: table 9, one array 9
15 items, capacity 30: table 70, one array 70

knapsack_code.tsts

type Item = readonly [weight: number, value: number];

function bestWithTable(items: readonly Item[], capacity: number): number {
  const best = Array.from({ length: items.length + 1 }, () => new Array<number>(capacity + 1).fill(0));
  items.forEach(([weight, value], index) => {
    const i = index + 1;
    for (let c = 0; c <= capacity; c++) {
      best[i][c] = best[i - 1][c];
      if (weight <= c) {
        best[i][c] = Math.max(best[i][c], best[i - 1][c - weight] + value);
      }
    }
  });
  return best[items.length][capacity];
}

function bestWithOneArray(items: readonly Item[], capacity: number): number {
  const best = new Array<number>(capacity + 1).fill(0);
  for (const [weight, value] of items) {
    for (let c = capacity; c >= weight; c--) {
      best[c] = Math.max(best[c], best[c - weight] + value);
    }
  }
  return best[capacity];
}

const small: Item[] = [[2, 3], [3, 5], [4, 6]];
const larger: Item[] = Array.from({ length: 15 }, (_, i) => [((i * 7) % 9) + 1, ((i * 11) % 13) + 1] as const);
const cases: [string, Item[], number][] = [["3 items, capacity 6", small, 6], ["15 items, capacity 30", larger, 30]];
for (const [name, items, capacity] of cases) {
  console.log(`${name}: table ${bestWithTable(items, capacity)}, one array ${bestWithOneArray(items, capacity)}`);
}

OutputRan with node:24.22.0-trixie-slim (Node 24.22.0), TypeScript 5.9.3

3 items, capacity 6: table 9, one array 9
15 items, capacity 30: table 70, one array 70

All three printed the same lines, and a separate check that tried all 32,768 subsets of the fifteen items printed them too.

The first highlighted line is the take choice in the table version: the row above, at the capacity left after the item, plus its value. The skip choice is the line before it, which copies the row above. The table has n + 1 rows of W + 1 cells, so it costs O(n × W) space as well as time.

The one-array version keeps a single row and overwrites it in place, item by item. The other two highlighted lines are its loop and its update, and the loop runs from the full capacity down to the item's weight. Going downwards, each cell reads best[c − w] before that cell has been updated for the current item, so it still holds the previous row's value, exactly what the table version reads from row i − 1. The space falls to O(W), and the time stays O(n × W).

The one array gives only the value. To list the items packed, keep the table and walk back through it, or keep a separate record of which cells took each item.

← → move through sections and cards