The 0/1 Knapsack Problem: 2D and 1D Dynamic Programming

The 0/1 knapsack problem is the archetype of “choose a subset under a constraint” DP. You have n items, each with a weight and a value, and a bag that holds at most W total weight. Each item is taken once or not at all (hence 0/1). Maximize the total value that fits. This page builds the 2D table first, then space-optimizes it to a single 1D array.

Defining the DP

At each item you face one binary decision: take it or skip it. The subproblem is “given the first i items and a remaining capacity c, what’s the best value?”

State: dp[i][c] = max value using the first i items with capacity c.
Transition: for item i (1-indexed) with weight w and value v:
- skip it: dp[i-1][c]
- take it (only if w <= c): v + dp[i-1][c-w]
- dp[i][c] = max(skip, take)
Base cases: dp[0][c] = 0 — zero items means zero value for any capacity.

The answer is dp[n][W].

2D tabulation: O(nW) time, O(nW) space

int knapsack(const std::vector<int>& wt, const std::vector<int>& val, int W) {
    int n = wt.size();
    std::vector<std::vector<int>> dp(n + 1, std::vector<int>(W + 1, 0));
    for (int i = 1; i <= n; i++) {
        for (int c = 0; c <= W; c++) {
            dp[i][c] = dp[i - 1][c];                       // skip
            if (wt[i - 1] <= c)
                dp[i][c] = std::max(dp[i][c],
                                    val[i - 1] + dp[i - 1][c - wt[i - 1]]); // take
        }
    }
    return dp[n][W];
}

int knapsack(int[] wt, int[] val, int W) {
    int n = wt.length;
    int[][] dp = new int[n + 1][W + 1];
    for (int i = 1; i <= n; i++) {
        for (int c = 0; c <= W; c++) {
            dp[i][c] = dp[i - 1][c];                       // skip
            if (wt[i - 1] <= c)
                dp[i][c] = Math.max(dp[i][c],
                                    val[i - 1] + dp[i - 1][c - wt[i - 1]]); // take
        }
    }
    return dp[n][W];
}

function knapsack(wt, val, W) {
  const n = wt.length;
  const dp = Array.from({ length: n + 1 }, () => new Array(W + 1).fill(0));
  for (let i = 1; i <= n; i++) {
    for (let c = 0; c <= W; c++) {
      dp[i][c] = dp[i - 1][c];                             // skip
      if (wt[i - 1] <= c)
        dp[i][c] = Math.max(dp[i][c],
                            val[i - 1] + dp[i - 1][c - wt[i - 1]]); // take
    }
  }
  return dp[n][W];
}

def knapsack(wt, val, W):
    n = len(wt)
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for c in range(W + 1):
            dp[i][c] = dp[i - 1][c]                        # skip
            if wt[i - 1] <= c:
                dp[i][c] = max(dp[i][c],
                               val[i - 1] + dp[i - 1][c - wt[i - 1]])  # take
    return dp[n][W]

1D space optimization: O(nW) time, O(W) space

Row i depends only on row i-1, so a single array suffices — as long as you iterate capacity in reverse. Going right-to-left ensures dp[c - w] still holds the previous item’s value (not the current item’s), preserving the “each item used at most once” rule.

int knapsack(const std::vector<int>& wt, const std::vector<int>& val, int W) {
    int n = wt.size();
    std::vector<int> dp(W + 1, 0);
    for (int i = 0; i < n; i++)
        for (int c = W; c >= wt[i]; c--)                   // iterate capacity DOWN
            dp[c] = std::max(dp[c], val[i] + dp[c - wt[i]]);
    return dp[W];
}

int knapsack(int[] wt, int[] val, int W) {
    int n = wt.length;
    int[] dp = new int[W + 1];
    for (int i = 0; i < n; i++)
        for (int c = W; c >= wt[i]; c--)                   // iterate capacity DOWN
            dp[c] = Math.max(dp[c], val[i] + dp[c - wt[i]]);
    return dp[W];
}

function knapsack(wt, val, W) {
  const n = wt.length;
  const dp = new Array(W + 1).fill(0);
  for (let i = 0; i < n; i++)
    for (let c = W; c >= wt[i]; c--)                       // iterate capacity DOWN
      dp[c] = Math.max(dp[c], val[i] + dp[c - wt[i]]);
  return dp[W];
}

def knapsack(wt, val, W):
    dp = [0] * (W + 1)
    for i in range(len(wt)):
        for c in range(W, wt[i] - 1, -1):                 # iterate capacity DOWN
            dp[c] = max(dp[c], val[i] + dp[c - wt[i]])
    return dp[W]

Pitfall: If you iterate capacity forward in the 1D version, dp[c - w] may already include the current item — that silently turns it into the unbounded knapsack (items reusable). The reverse loop is what enforces 0/1. This direction rule is the most-tested detail of the problem.

Complexity and pseudo-polynomial caveat

Approach	Time	Space
Brute force (all subsets)	O(2ⁿ)	O(n)
2D DP	O(nW)	O(nW)
1D DP	O(nW)	O(W)

Going deeper: O(nW) is pseudo-polynomial — it’s polynomial in W’s value, not its number of bits. If W is astronomically large, this table becomes infeasible; the 0/1 knapsack is NP-hard in general. For most interview constraints, the 1D DP is exactly what you want.

The take-or-skip pattern here recurs in coin change and subset-sum problems. Next, see how DP handles two sequences at once in Longest Common Subsequence.