0/1 Knapsack Visualizer - Bottom-Up DP Tabulation

0/1 Knapsack (Bottom-Up DP): how it works

Tabulation (Bottom-Up DP) solves all sub-problems iteratively from smallest to largest, filling a 2D table. No recursion needed: a nested loop builds the answer from scratch.

1. The Problem

   Given N items with weights and values, and a knapsack of capacity W, pick items to maximize total value without exceeding W. Each item can only be picked once (0/1).

2. Building the Table

   dp[i][w] = maximum value achievable using the first i items with capacity w. The table is filled row by row. Row 0 (no items) = all zeros.

3. The Recurrence

   For each item i and capacity w: if item weight > w → dp[i][w] = dp[i-1][w] (can't take it). Otherwise → dp[i][w] = max(skip: dp[i-1][w], take: dp[i-1][w-weight] + value).

4. Backtracking for Items

   After filling the table, read backwards from dp[n][W]. If dp[i][w] ≠ dp[i-1][w], item i was taken, so subtract its weight and move up. Repeat until row 0.

Complexity

Best-case time

O(n·W)

Average time

O(n·W)

Worst-case time

O(n·W)

Space

O(n·W)

n = number of items, W = knapsack capacity. Unlike Fibonacci, knapsack cannot be solved in O(n), because the table has n×W cells. Space can be optimized to O(W) using a 1D rolling array.