Subhra Jyoti Baroieditorial
Chat with me
← Daily Logs
Algorithms

0/1 Knapsack — Tabulation

MediumAug 12, 2026dynamic-programmingknapsacktabulationbottom-up

Same table as the memoized version, filled in the opposite direction. Instead of asking for `memo[n][capacity]` and letting recursion discover which subproblems it needs, this fills every cell in order from `(1, 1)` upward, so the two values each cell depends on are already sitting in the row below it. The recursion, the stack and the null checks all disappear — what's left is two loops and one line of recurrence.

The problem

Same 0/1 knapsack: `knapsackTopDown(weights, values, capacity)` returns the maximum value obtainable by choosing a subset of items whose total weight fits the capacity, each item usable at most once. The goal here is to compute it iteratively, without recursion.

`weights = [1, 3, 4, 5], values = [1, 4, 5, 7], capacity = 7` still returns `9`, and the answer lands in `memo[4][7]` — the bottom-right corner of a table where every other cell is also a real answer to a smaller version of the problem.

The approach

A naming note before anything else: this function is called `knapsackTopDown`, but what it does is bottom-up tabulation. Top-down is the recursive-plus-memo version from the previous entry — it starts at the answer and recurses down toward the base cases. This starts at the base cases and builds up to the answer. The code is right; the label is the wrong way round, and the two names get swapped often enough that it's worth pinning down which is which.

The two initialisation loops are the recursive base cases written out as data instead of an `if`. Row `0` is 'no items available' and column `0` is 'no capacity left' — both worth `0` value — and every cell from `(1, 1)` onward is computed from cells that already exist. Nothing is ever read before it's written, which is the whole reason recursion isn't needed.

The recurrence is line-for-line the recursive body with the calls replaced by lookups: `memo[i-1][j - weights[i-1]]` is the include branch (one fewer item, less room), `memo[i-1][j]` is the exclude branch (one fewer item, same room), and the `weights[i-1] <= j` guard picks between taking the max and being forced to skip. Every recursive call became an array read, which is why the constant factor here beats memoization even though the big-O is identical.

The loop order is what makes the dependencies work: `i` outer, `j` inner means row `i-1` is complete before row `i` starts, and both lookups are in row `i-1`. That also exposes the standard optimisation — since only the previous row is ever read, the whole table can collapse to two rows (or one row iterated right-to-left) for `O(capacity)` space. The full grid is kept here because it's what you walk backwards through if you need the chosen items, not just the total.

The solution

js
export function knapsackTopDown(weights, values, capacity) {
    const memo = Array.from({ length: weights.length + 1 }, () => Array(capacity + 1).fill(null))

    // initialize the first row with 0
    for (let i = 0; i <= weights.length; i++) {
        memo[i][0] = 0
    }
    // initialize the first column with 0
    for (let j = 0; j <= capacity; j++) {
        memo[0][j] = 0
    }

    // fill the memo table
    for (let i = 1; i <= weights.length; i++) {
        for (let j = 1; j <= capacity; j++) {
            if (weights[i-1] <= j) {
                memo[i][j] = Math.max(values[i-1] + memo[i-1][j-weights[i-1]], memo[i-1][j])
            } else {
                memo[i][j] = memo[i-1][j]
            }
        }
    }

    // return the maximum value
    return memo[weights.length][capacity]
}

Time O(n * capacity)Space O(n * capacity)

All entries