☕ DSA Java Articles

Topics › Dynamic Programming › DP on Subsequences

0 and 1 Knapsack

Hard TUF ID 315 SDE

Java source ↗ Edit this article ↗

Problem

There are n items; item i has weight wt[i] and value val[i]. A knapsack can carry a total weight of at most W. Choose a set of items, each used at most once and never split, so that the total weight is at most W and the total value is as large as possible. Return that value. The “0/1” in the name means every item is either left out (0) or taken whole (1).

Constraints in the usual version (GFG, “0 - 1 Knapsack Problem”): n and W up to about 1000, positive weights, non-negative values.

Example 1

W = 4, wt = [4, 5, 1], val = [1, 2, 3]
answer = 3          // take only item 2 (weight 1, value 3); items 0 and 2 together weigh 5 > 4

Example 2

W = 10, wt = [6, 5, 5], val = [30, 20, 20]
answer = 40         // the two weight-5 items

Example 2 shows why a greedy rule fails. Item 0 has the best value per unit of weight (30 / 6 = 5), but taking it leaves room for nothing else and gives only 30. The decisions interact, so we have to explore both choices for every item.

Approach 1: Recursion

Intuition. Look at the last item i. There are two options:

So solve(i, cap) = max(skip, take), with solve(-1, cap) = 0 because no items means no value. The “take” option is set to Integer.MIN_VALUE when the item does not fit, so max always picks “skip” in that case.

Algorithm.

  1. If i < 0, return 0.
  2. skip = solve(i - 1, cap).
  3. take = val[i] + solve(i - 1, cap - wt[i]) if the item fits, else MIN_VALUE.
  4. Return max(skip, take).
static int recursion(int W, int[] wt, int[] val) {
    return solve(wt.length - 1, W, wt, val);
}

static int solve(int i, int cap, int[] wt, int[] val) {
    if (i < 0) return 0;                                   // no items left
    int skip = solve(i - 1, cap, wt, val);
    int take = wt[i] <= cap ? val[i] + solve(i - 1, cap - wt[i], wt, val) : Integer.MIN_VALUE;
    return Math.max(skip, take);
}

Complexity. Time O(2^n): every item branches into two calls. Space O(n) for the recursion stack.

Approach 2: Memoization

Intuition. The value of solve(i, cap) depends only on the pair (i, cap), and there are only n · (W + 1) such pairs. The recursion tree reaches the same pair many times: for example, taking item 3 and skipping item 2, or the other way round, leads to the same subproblem whenever wt[3] == wt[2]. Caching every result in memo[i][cap] makes each pair cost O(1) after its first computation. Since values are non-negative, -1 safely means “not computed yet”.

static int memoization(int W, int[] wt, int[] val) {
    int n = wt.length;
    int[][] memo = new int[n][W + 1];
    for (int[] row : memo) Arrays.fill(row, -1);
    return solveMemo(n - 1, W, wt, val, memo);
}

static int solveMemo(int i, int cap, int[] wt, int[] val, int[][] memo) {
    if (i < 0) return 0;
    if (memo[i][cap] != -1) return memo[i][cap];
    int skip = solveMemo(i - 1, cap, wt, val, memo);
    int take = wt[i] <= cap ? val[i] + solveMemo(i - 1, cap - wt[i], wt, val, memo) : Integer.MIN_VALUE;
    return memo[i][cap] = Math.max(skip, take);
}

Complexity. Time O(n · W): each state is computed once with O(1) work. Space O(n · W) for the table plus O(n) stack.

Approach 3: Tabulation

Intuition. Fill the same table bottom-up, without recursion. Let dp[i][c] be the best value using the first i items (indices 0..i-1) with capacity c. This is solve(i - 1, c) shifted by one row, so that row 0 can stand for “no items” and is all zeros. Row i depends only on row i - 1:

dp[i][c] = max(dp[i-1][c], val[i-1] + dp[i-1][c - wt[i-1]]), where the second option exists only if wt[i-1] ≤ c.

Algorithm.

  1. Create dp[n + 1][W + 1], all zeros.
  2. For i = 1 .. n, for c = 0 .. W: copy the “skip” value from the row above, then try “take”.
  3. Return dp[n][W].
static int tabulation(int W, int[] wt, int[] val) {
    int n = wt.length;
    int[][] dp = new int[n + 1][W + 1];                    // row 0: no items, value 0
    for (int i = 1; i <= n; i++) {
        for (int c = 0; c <= W; c++) {
            dp[i][c] = dp[i - 1][c];                       // skip item i - 1
            if (wt[i - 1] <= c) dp[i][c] = Math.max(dp[i][c], val[i - 1] + dp[i - 1][c - wt[i - 1]]);
        }
    }
    return dp[n][W];
}

Dry run on Example 1 (W = 4):

row (items allowed) c = 0 c = 1 c = 2 c = 3 c = 4
0 (none) 0 0 0 0 0
1 (+ w4 v1) 0 0 0 0 1
2 (+ w5 v2) 0 0 0 0 1
3 (+ w1 v3) 0 3 3 3 3

In the last row, c = 4 compares skipping (1) with taking item 2 (3 + dp[2][3] = 3). The answer is dp[3][4] = 3.

Complexity. Time O(n · W), space O(n · W).

Approach 4: Space optimised, one array

Intuition. Row i reads only row i - 1, so two rows of length W + 1 would be enough. We can go further and use a single array if we fill it from right to left. When computing dp[c], the “take” option reads dp[c - wt[i]], an index to the left that has not been updated yet in this pass. It still holds the previous row’s value, which is exactly what the recurrence needs, so each item is counted at most once.

Scanning left to right instead would read a value already updated for the current item, which lets the same item be taken again and again. That is the unbounded knapsack, a different problem.

static int spaceOptimised(int W, int[] wt, int[] val) {
    int[] dp = new int[W + 1];
    for (int i = 0; i < wt.length; i++) {
        for (int c = W; c >= wt[i]; c--) {                 // right to left: dp[c - wt[i]] is still the old value
            dp[c] = Math.max(dp[c], val[i] + dp[c - wt[i]]);
        }
    }
    return dp[W];
}

Complexity. Time O(n · W), space O(W). The loop also stops at c = wt[i], since smaller capacities cannot take item i and keep their old value.

A note on scale: O(n · W) is pseudo-polynomial, because it grows with the numeric value of W. If W were around 10^9 but the values were small, you would swap the roles and compute “minimum weight needed to reach each total value” instead.

Edge cases and pitfalls