Implementation

This chapter implements 0/1 knapsack in Python (full table with reconstruction, then a single row), adds an LCS function that returns the subsequence, and ports the one-row knapsack to C++, Java and TypeScript.

The 0/1 knapsack problem

You have n items, each with a weight and a value, and a bag that holds at most capacity weight. Each item is either taken once or left behind ("0/1"). Maximize the total value.

• State: best[i][c] = the highest value using only the first i items with capacity c.
• Recurrence: skip item i (best[i-1][c]), or take it if it fits (best[i-1][c - w] + v); keep the larger.
• Base case: best[0][c] = 0, since no items means no value.

Python: full table with reconstruction

def knapsack(weights: list[int], values: list[int], capacity: int) -> tuple[int, list[int]]:
    n = len(weights)
    best = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        w, v = weights[i - 1], values[i - 1]
        for c in range(capacity + 1):
            best[i][c] = best[i - 1][c]
            if w <= c and best[i - 1][c - w] + v > best[i][c]:
                best[i][c] = best[i - 1][c - w] + v
    chosen, c = [], capacity
    for i in range(n, 0, -1):
        if best[i][c] != best[i - 1][c]:
            chosen.append(i - 1)
            c -= weights[i - 1]
    return best[n][capacity], chosen[::-1]


print(knapsack([1, 3, 4, 5], [1, 4, 5, 7], 7))  # (9, [1, 2])

Line by line:

• best has n + 1 rows and capacity + 1 columns; row 0 stays all zeros as the base case.
• Row i describes item i - 1, because Python lists are zero-based.
• best[i][c] = best[i - 1][c] is the "skip" choice, which is always allowed.
• The if tries the "take" choice: only when the item fits, and only kept when it is strictly better.
• Reconstruction walks rows from bottom to top. If the value changed between row i - 1 and row i at the current capacity, item i - 1 must have been taken, so we record it and subtract its weight.

In the example the best choice is items 1 and 2 (weight 3 + 4, value 4 + 5 = 9).

Python: one row is enough

Row i only reads row i - 1, so a single list can hold both if we update it carefully. Iterating capacities from high to low guarantees that best[c - w] still holds the previous row's value when it is read; that is what keeps each item to at most one use.

def knapsack_value(weights: list[int], values: list[int], capacity: int) -> int:
    best = [0] * (capacity + 1)
    for w, v in zip(weights, values):
        for c in range(capacity, w - 1, -1):  # high to low: each item at most once
            best[c] = max(best[c], best[c - w] + v)
    return best[capacity]


print(knapsack_value([1, 3, 4, 5], [1, 4, 5, 7], 7))  # 9

Iterating from low to high instead lets an item be reused within the row, which solves the unbounded knapsack. One loop direction is the whole difference.

Python: LCS with the subsequence itself

def lcs(a: str, b: str) -> str:
    n, m = len(a), len(b)
    L = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(n - 1, -1, -1):
        for j in range(m - 1, -1, -1):
            if a[i] == b[j]:
                L[i][j] = L[i + 1][j + 1] + 1
            else:
                L[i][j] = max(L[i + 1][j], L[i][j + 1])
    out, i, j = [], 0, 0
    while i < n and j < m:
        if a[i] == b[j]:
            out.append(a[i])
            i, j = i + 1, j + 1
        elif L[i + 1][j] >= L[i][j + 1]:
            i += 1
        else:
            j += 1
    return "".join(out)


print(lcs("ABCBDAB", "BDCABA"))  # BDAB

Here L[i][j] describes the suffixes a[i:] and b[j:], so the table is filled backwards and reconstruction walks forwards from (0, 0) with no final reversal.

C++

#include <algorithm>
#include <iostream>
#include <vector>

long long knapsack(const std::vector<int>& weights, const std::vector<long long>& 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) {
            best[c] = std::max(best[c], best[c - weights[i]] + values[i]);
        }
    }
    return best[capacity];
}

int main() {
    std::cout << knapsack({1, 3, 4, 5}, {1, 4, 5, 7}, 7) << '\n';  // 9
}

Values use long long because sums of many large values can overflow a 32-bit int.

Java

public final class Knapsack {
    static long knapsack(int[] weights, long[] 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--) {
                best[c] = Math.max(best[c], best[c - weights[i]] + values[i]);
            }
        }
        return best[capacity];
    }

    public static void main(String[] args) {
        System.out.println(knapsack(new int[] {1, 3, 4, 5}, new long[] {1, 4, 5, 7}, 7)); // 9
    }
}

TypeScript

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

console.log(knapsack([1, 3, 4, 5], [1, 4, 5, 7], 7)); // 9

All four versions have the same shape: one array of size capacity + 1, an outer loop over items and an inner loop over capacities from high to low.

Summary

• Build the full table when you need to reconstruct the choices; drop to one row when you only need the value.
• In the one-row 0/1 knapsack, the inner loop must run from high capacity to low.
• Defining LCS on suffixes lets reconstruction run forwards.
• The core routine is the same few lines in every language; watch for integer overflow in C++ and Java.