Chapter 63 of 65

Knapsack Problems

Imagine you're going on a trek. Your bag can carry at most 7 kg. In front of you are several items: a water bottle, a jacket, a camera, some food. Each item has a weight and a value (how useful it is to you).

You can't take everything. Which items should you pack to get the maximum total value without going over the weight limit?

This is the famous Knapsack Problem (a knapsack is just another word for a backpack). It's probably the single most important DP pattern for interviews, because a huge number of problems are knapsack problems in disguise.

The Knapsack Problem: given items with weights and values and a bag with a weight limit, choose items so that the total weight stays within the limit and the total value is as large as possible.

In this chapter, we'll cover:

Knapsack Family
├── 0/1 Knapsack          → each item can be taken at most once
├── Subset Sum            → can we hit an exact total?
├── Partition Equal Sum   → can we split into two equal halves?
├── Unbounded Knapsack    → each item can be taken any number of times
└── Coin Change II        → count the ways to make an amount

We'll use the 2D DP table idea from the previous chapter, where the two dimensions are items and capacity.


Variants at a Glance

Variant

Rule

Solved By

Fractional Knapsack

You can take a fraction of an item (like 0.5 kg of rice)

Greedy (sort by value/weight)

0/1 Knapsack

Each item is taken whole or not at all, at most once

Dynamic Programming

Unbounded Knapsack

Each item can be taken unlimited times

Dynamic Programming

The fractional version was solved in the Greedy Algorithms chapter: keep taking the item with the highest value per kg, and take a fraction of the last one to fill the bag exactly. This chapter is about the two versions that need DP.


0/1 Knapsack: The Problem

We'll use this example throughout:

Item   Weight   Value
 0       1        1
 1       3        4
 2       4        5
 3       5        7

Bag capacity W = 7

The best choice is items 1 and 2:

Weight = 3 + 4 = 7  (fits exactly)
Value  = 4 + 5 = 9

The answer is 9.


Why Greedy Fails for 0/1 Knapsack

The greedy idea is: "take items with the best value-per-kg first."

Item   Value/Weight
 3     7/5 = 1.40   ← best ratio
 1     4/3 = 1.33
 2     5/4 = 1.25
 0     1/1 = 1.00

Greedy takes item 3 (weight 5, value 7). Now only 2 kg is left. Items 1 and 2 don't fit, so it takes item 0 (weight 1, value 1).

Greedy total = 7 + 1 = 8
Best total   = 9

Greedy works for the fractional version because you can always fill the leftover space with a piece of the next item. In 0/1 knapsack, leftover space can be wasted, so an early "good-looking" choice can block a better combination.


The Brute-Force Idea

Every item has two choices: take it or skip it. That's exactly the decision tree you saw in the Backtracking chapter when generating subsets.

                     item 0
                  /          \
             take             skip
             /                    \
         item 1                  item 1
        /     \                 /     \
     take    skip            take    skip
     ...      ...             ...     ...

With n items, there are 2ⁿ subsets to check. For 40 items, that's over a trillion. Too slow.

But notice: the only things that matter for future decisions are which item we're on and how much capacity is left. Many different paths in the tree reach the same (item, capacity) pair. Those are overlapping subproblems, and that means DP.


0/1 Knapsack: The DP Formulation

State      : dp[i][w] = maximum value using only the first i items
                        with a bag of capacity w

Recurrence : For item i (its weight is wt[i-1], value is val[i-1]):

             Skip it : dp[i-1][w]
             Take it : val[i-1] + dp[i-1][w - wt[i-1]]   (only if wt[i-1] ≤ w)

             dp[i][w] = max(skip, take)

Base cases : dp[0][w] = 0   (no items → no value)
             dp[i][0] = 0   (no capacity → no value)

Answer     : dp[n][W]

Why dp[i-1][...] in the "take" case and not dp[i][...]? Because after taking item i, the rest of the bag must be filled using only the earlier items. Item i can't be used again. That one detail is what makes it "0/1".

We use i for "the first i items", so item i is stored at array index i - 1. This shift lets row 0 mean "no items", which is a free base case.


Filling the Table

Rows are items considered so far, columns are capacities 0 to 7:

                        capacity w →
                     0   1   2   3   4   5   6   7
no items       i=0   0   0   0   0   0   0   0   0
+ item 0 (1,1) i=1   0   1   1   1   1   1   1   1
+ item 1 (3,4) i=2   0   1   1   4   5   5   5   5
+ item 2 (4,5) i=3   0   1   1   4   5   6   6   9
+ item 3 (5,7) i=4   0   1   1   4   5   7   8   9  ← answer dp[4][7] = 9

Let's check a few cells by hand.

dp[2][4] (items 0–1, capacity 4):

Skip item 1 : dp[1][4]              = 1
Take item 1 : 4 + dp[1][4 - 3] = 4 + 1 = 5
dp[2][4] = max(1, 5) = 5

dp[3][7] (items 0–2, capacity 7):

Skip item 2 : dp[2][7]              = 5
Take item 2 : 5 + dp[2][7 - 4] = 5 + 4 = 9
dp[3][7] = max(5, 9) = 9

dp[4][7] (all items, capacity 7):

Skip item 3 : dp[3][7]              = 9
Take item 3 : 7 + dp[3][7 - 5] = 7 + 1 = 8
dp[4][7] = max(9, 8) = 9

Each row depends only on the row directly above it, so we fill row by row.


Finding Which Items Were Taken

The table tells us the best value, but which items give that value? We use path reconstruction, just like in the Minimum Path Sum problem.

Start at dp[n][W] and go up one row at a time:

  • If dp[i][w] == dp[i-1][w], item i was not needed. Move up.

  • Otherwise, item i was taken. Record it, subtract its weight from w, and move up.

i=4, w=7 : dp[4][7]=9, dp[3][7]=9 → same, skip item 3
i=3, w=7 : dp[3][7]=9, dp[2][7]=5 → different, TAKE item 2, w = 7 - 4 = 3
i=2, w=3 : dp[2][3]=4, dp[1][3]=1 → different, TAKE item 1, w = 3 - 3 = 0
i=1, w=0 : dp[1][0]=0, dp[0][0]=0 → same, skip item 0

Items taken: 1, 2

0/1 Knapsack in Java

static int knapsack01(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 w = 0; w <= W; w++) {
            dp[i][w] = dp[i - 1][w];                       // skip item i
            if (wt[i - 1] <= w) {
                dp[i][w] = Math.max(dp[i][w],
                    val[i - 1] + dp[i - 1][w - wt[i - 1]]); // take item i
            }
        }
    }

    // Which items were taken?
    List<Integer> taken = new ArrayList<>();
    int w = W;
    for (int i = n; i >= 1; i--) {
        if (dp[i][w] != dp[i - 1][w]) {
            taken.add(i - 1);
            w -= wt[i - 1];
        }
    }
    Collections.reverse(taken);
    System.out.println("Items taken (indexes) : " + taken);

    return dp[n][W];
}

Complexity: There are (n + 1) × (W + 1) states with O(1) work each:

Time  → O(n × W)
Space → O(n × W)

This is called pseudo-polynomial time. It's fast when W is reasonable (like a few thousand), but if W were a billion, the table would be far too large. The running time depends on the value of W, not just the number of items.


Space Optimization: One Array, Loop Backwards

Each row only reads the row above it. So, like in 2D DP, we can use a single 1D array dp[w].

static int knapsack01Optimized(int[] wt, int[] val, int W) {

    int[] dp = new int[W + 1];

    for (int i = 0; i < wt.length; i++) {
        for (int w = W; w >= wt[i]; w--) {       // BACKWARDS!
            dp[w] = Math.max(dp[w], val[i] + dp[w - wt[i]]);
        }
    }

    return dp[W];
}

The inner loop goes from right to left. This is the most important detail in this whole chapter, so let's see why.

Why Backwards?

dp[w - wt[i]] must still hold the value from the previous row (before item i was considered). Going right to left, we update the big capacities first, and the smaller index w - wt[i] hasn't been touched yet in this pass.

If we go left to right, dp[w - wt[i]] might already include item i, and we'd add item i a second time.

A tiny example: one item with weight 2 and value 3, capacity 4.

Forward  (w = 2, 3, 4):
dp[2] = 3 + dp[0] = 3
dp[3] = 3 + dp[1] = 3
dp[4] = 3 + dp[2] = 6   ← used the same item TWICE (wrong for 0/1)
Result: [0, 0, 3, 3, 6]

Backward (w = 4, 3, 2):
dp[4] = 3 + dp[2] = 3   (dp[2] is still 0 here)
dp[3] = 3 + dp[1] = 3
dp[2] = 3 + dp[0] = 3
Result: [0, 0, 3, 3, 3]  ← correct, item used once

Space drops from O(n × W) to O(W). As with any compressed table, you can no longer reconstruct which items were taken.


Subset Sum

Given a set of positive numbers, is there a subset whose sum is exactly target?

nums = {3, 34, 4, 12, 5, 2}

target = 9  → true   (4 + 5, or 3 + 4 + 2)
target = 30 → false

This is 0/1 knapsack where each number is an item whose "weight" is the number itself. Instead of maximizing value, we only ask "is this sum reachable?", so the table holds boolean values.

State      : dp[s] = true if some subset of the numbers seen so far sums to s
Recurrence : dp[s] = dp[s] OR dp[s - num]
             (either s was already reachable, or we reach it by adding num)
Base case  : dp[0] = true   (the empty subset sums to 0)
Answer     : dp[target]
static boolean subsetSum(int[] nums, int target) {

    boolean[] dp = new boolean[target + 1];
    dp[0] = true;

    for (int num : nums) {
        for (int s = target; s >= num; s--) {    // backwards: each number once
            dp[s] = dp[s] || dp[s - num];
        }
    }

    return dp[target];
}

For target 30: the number 34 is too big, and all the other numbers together add up to only 3 + 4 + 12 + 5 + 2 = 26. So 30 is impossible.

Complexity: Time O(n × target), Space O(target).


Partition Equal Subset Sum

Can the array be split into two groups with equal sums?

[1, 5, 11, 5] → true    ({11} and {1, 5, 5}, both sum to 11)
[1, 2, 3, 5]  → false   (total is 11, which is odd)

The trick: if the total is S, each group must sum to S / 2. And if one group sums to S / 2, the remaining numbers automatically sum to S / 2 too. So the question becomes:

Is there a subset with sum = total / 2?

That's just Subset Sum. If the total is odd, the answer is immediately false.

static boolean canPartition(int[] nums) {

    int total = 0;
    for (int num : nums) {
        total += num;
    }

    if (total % 2 != 0) {
        return false;
    }

    return subsetSum(nums, total / 2);
}

Recognizing that a new problem reduces to a problem you already know is one of the most valuable interview skills in DP.


Unbounded Knapsack

Now suppose each item is available in unlimited quantity. You can take the same item as many times as you like.

Item   Weight   Value
 0       2        3
 1       3        5
 2       4        7

Capacity W = 10

Best answer: 17, for example items 1 + 1 + 2 (weights 3 + 3 + 4 = 10, values 5 + 5 + 7 = 17). If each item could be used only once, the best we could do would be all three items: weight 9, value 15.

The One-Line Difference

In 0/1 knapsack, after taking item i, we look at the previous row (item i can't be reused). In unbounded knapsack, after taking item i, we look at the same row (item i is still available):

0/1       : take = val[i] + dp[i-1][w - wt[i]]
Unbounded : take = val[i] + dp[i][w - wt[i]]

In the 1D version, this simply means looping capacity forwards. The exact "bug" that broke 0/1 knapsack (reusing an item) is now exactly what we want.

static int unboundedKnapsack(int[] wt, int[] val, int W) {

    int[] dp = new int[W + 1];

    for (int i = 0; i < wt.length; i++) {
        for (int w = wt[i]; w <= W; w++) {       // FORWARDS
            dp[w] = Math.max(dp[w], val[i] + dp[w - wt[i]]);
        }
    }

    return dp[W];
}

Final dp array for capacities 0 to 10:

w     : 0  1  2  3  4  5   6   7   8   9  10
dp[w] : 0  0  3  5  7  8  10  12  14  15  17

The Coin Change (minimum coins) problem from the 1D DP chapter is also an unbounded knapsack: each coin can be used any number of times, and we minimize the count instead of maximizing value.

0/1 Knapsack

Unbounded Knapsack

Each item used

At most once

Any number of times

2D "take" reads

Previous row dp[i-1][...]

Same row dp[i][...]

1D capacity loop

Backwards (W down to wt)

Forwards (wt up to W)

Examples

Subset Sum, Partition, Target Sum

Coin Change, Rod Cutting


Coin Change II: Counting the Ways

Given coins {1, 2, 5} (unlimited supply), in how many ways can you make the amount 5?

5
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1

Answer: 4

Here 2 + 2 + 1 and 1 + 2 + 2 count as the same way. We're counting combinations, not ordered sequences.

State      : dp[a] = number of combinations that make amount a
Recurrence : dp[a] += dp[a - coin]
Base case  : dp[0] = 1   (one way to make 0: use no coins)
Answer     : dp[amount]
static long countCombinations(int[] coins, int amount) {

    long[] dp = new long[amount + 1];
    dp[0] = 1;

    for (int coin : coins) {                  // coins in the OUTER loop
        for (int a = coin; a <= amount; a++) {
            dp[a] += dp[a - coin];
        }
    }

    return dp[amount];
}

The table after processing each coin:

amount         : 0  1  2  3  4  5
after coin 1   : 1  1  1  1  1  1
after coin 2   : 1  1  2  2  3  3
after coin 5   : 1  1  2  2  3  4  ← answer

Loop Order Changes the Meaning

If you swap the loops (amount outside, coins inside), the same code counts ordered sequences (permutations), where 1 + 2 + 2, 2 + 1 + 2 and 2 + 2 + 1 are all different:

static long countPermutations(int[] coins, int amount) {

    long[] dp = new long[amount + 1];
    dp[0] = 1;

    for (int a = 1; a <= amount; a++) {        // amount in the OUTER loop
        for (int coin : coins) {
            if (coin <= a) {
                dp[a] += dp[a - coin];
            }
        }
    }

    return dp[amount];
}

For coins {1, 2, 5} and amount 5, this returns 9 instead of 4.

Why? With coins outside, we finish using all the 1s before we ever consider a 2, so coins always get added in one fixed order and each combination is counted once. With amount outside, any coin can be the "last" coin at every step, so every ordering gets counted separately.

Coins outer, amount inner → combinations  (Coin Change II, LeetCode 518)
Amount outer, coins inner → permutations  (Combination Sum IV, LeetCode 377)

This is a classic interview trap. Always ask yourself whether order matters.


Complete Java Program

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Main {

    // 1. 0/1 Knapsack: 2D table + reconstruction
    static int knapsack01(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 w = 0; w <= W; w++) {
                dp[i][w] = dp[i - 1][w];                       // skip item i
                if (wt[i - 1] <= w) {
                    dp[i][w] = Math.max(dp[i][w],
                        val[i - 1] + dp[i - 1][w - wt[i - 1]]); // take item i
                }
            }
        }

        // Which items were taken?
        List<Integer> taken = new ArrayList<>();
        int w = W;
        for (int i = n; i >= 1; i--) {
            if (dp[i][w] != dp[i - 1][w]) {
                taken.add(i - 1);
                w -= wt[i - 1];
            }
        }
        Collections.reverse(taken);
        System.out.println("Items taken (indexes) : " + taken);

        return dp[n][W];
    }

    // 2. 0/1 Knapsack: 1D array (loop capacity BACKWARDS)
    static int knapsack01Optimized(int[] wt, int[] val, int W) {
        int[] dp = new int[W + 1];
        for (int i = 0; i < wt.length; i++) {
            for (int w = W; w >= wt[i]; w--) {
                dp[w] = Math.max(dp[w], val[i] + dp[w - wt[i]]);
            }
        }
        return dp[W];
    }

    // 3. Unbounded Knapsack (loop capacity FORWARDS)
    static int unboundedKnapsack(int[] wt, int[] val, int W) {
        int[] dp = new int[W + 1];
        for (int i = 0; i < wt.length; i++) {
            for (int w = wt[i]; w <= W; w++) {
                dp[w] = Math.max(dp[w], val[i] + dp[w - wt[i]]);
            }
        }
        return dp[W];
    }

    // 4. Subset Sum
    static boolean subsetSum(int[] nums, int target) {
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;
        for (int num : nums) {
            for (int s = target; s >= num; s--) {
                dp[s] = dp[s] || dp[s - num];
            }
        }
        return dp[target];
    }

    // 5. Partition Equal Subset Sum
    static boolean canPartition(int[] nums) {
        int total = 0;
        for (int num : nums) {
            total += num;
        }
        if (total % 2 != 0) {
            return false;
        }
        return subsetSum(nums, total / 2);
    }

    // 6. Coin Change II: number of combinations
    static long countCombinations(int[] coins, int amount) {
        long[] dp = new long[amount + 1];
        dp[0] = 1;
        for (int coin : coins) {                  // coins OUTSIDE
            for (int a = coin; a <= amount; a++) {
                dp[a] += dp[a - coin];
            }
        }
        return dp[amount];
    }

    // 7. Number of ordered sequences (permutations)
    static long countPermutations(int[] coins, int amount) {
        long[] dp = new long[amount + 1];
        dp[0] = 1;
        for (int a = 1; a <= amount; a++) {        // amount OUTSIDE
            for (int coin : coins) {
                if (coin <= a) {
                    dp[a] += dp[a - coin];
                }
            }
        }
        return dp[amount];
    }

    public static void main(String[] args) {

        int[] wt  = {1, 3, 4, 5};
        int[] val = {1, 4, 5, 7};
        int W = 7;

        System.out.println("0/1 knapsack (2D)     : " + knapsack01(wt, val, W));
        System.out.println("0/1 knapsack (1D)     : " + knapsack01Optimized(wt, val, W));

        int[] uwt  = {2, 3, 4};
        int[] uval = {3, 5, 7};
        System.out.println("Unbounded knapsack    : " + unboundedKnapsack(uwt, uval, 10));
        System.out.println("Same items as 0/1     : " + knapsack01Optimized(uwt, uval, 10));

        int[] set = {3, 34, 4, 12, 5, 2};
        System.out.println("Subset sum = 9?       : " + subsetSum(set, 9));
        System.out.println("Subset sum = 30?      : " + subsetSum(set, 30));

        System.out.println("Partition [1,5,11,5]  : " + canPartition(new int[]{1, 5, 11, 5}));
        System.out.println("Partition [1,2,3,5]   : " + canPartition(new int[]{1, 2, 3, 5}));

        int[] coins = {1, 2, 5};
        System.out.println("Combinations for 5    : " + countCombinations(coins, 5));
        System.out.println("Permutations for 5    : " + countPermutations(coins, 5));
    }
}

Output:

Items taken (indexes) : [1, 2]
0/1 knapsack (2D)     : 9
0/1 knapsack (1D)     : 9
Unbounded knapsack    : 17
Same items as 0/1     : 15
Subset sum = 9?       : true
Subset sum = 30?      : false
Partition [1,5,11,5]  : true
Partition [1,2,3,5]   : false
Combinations for 5    : 4
Permutations for 5    : 9

How to Spot a Knapsack Problem

A problem is probably a knapsack variant if:

  • You have a list of items (numbers, coins, weights, tasks)

  • For each item, you decide to take it or not (or how many times)

  • There is a limit or target (capacity, sum, amount)

  • You need a max/min value, a yes/no answer, or a count of ways

Then ask two questions:

1. Can an item be used more than once?
   No  → 0/1 knapsack       → capacity loop backwards
   Yes → unbounded knapsack → capacity loop forwards

2. What do we want?
   Max / min value → dp holds numbers, combine with max / min
   Possible?       → dp holds booleans, combine with OR
   Count of ways   → dp holds counts, combine with +

Common Mistakes

1. Looping the wrong direction in 1D

Forward loop in 0/1 knapsack silently allows reusing items. Backward loop in unbounded knapsack silently prevents reuse. The code still compiles and often passes small tests, which makes this bug dangerous.

2. Off-by-one between item number and array index

In the 2D table, row i means "first i items", so its weight is wt[i - 1]. Mixing these up gives wrong answers or ArrayIndexOutOfBoundsException.

3. Wrong base case for counting

For counting ways, dp[0] = 1. For max value, dp[0] = 0. For subset sum, dp[0] = true. Each one says "the empty choice is valid for target 0".

4. Swapping loops in Coin Change II

Coins outside counts combinations. Amount outside counts permutations. Read the problem carefully to see which one it wants.

5. Using greedy for 0/1 knapsack

Sorting by value/weight only works for the fractional version.

6. Ignoring the size of W

O(n × W) is only fast when W is small enough to fit in an array. If the capacity is huge (like 10⁹), you need a different approach.


Practice Problems

  • 0/1 Knapsack (GeeksforGeeks)

  • Partition Equal Subset Sum (LeetCode 416)

  • Target Sum (LeetCode 494)

  • Last Stone Weight II (LeetCode 1049)

  • Ones and Zeroes (LeetCode 474), a knapsack with two capacities

  • Coin Change (LeetCode 322)

  • Coin Change II (LeetCode 518)

  • Combination Sum IV (LeetCode 377)

  • Rod Cutting (GeeksforGeeks)


The Main Idea

In knapsack problems, every item gives you a choice: take it or skip it. DP stores the best result for every pair of (items considered, capacity) so no combination is checked twice.

0/1 Knapsack
dp[i][w] = max(dp[i-1][w], val + dp[i-1][w - wt])

Unbounded Knapsack
dp[i][w] = max(dp[i-1][w], val + dp[i][w - wt])

The complexity is:

Time  → O(n × W)
Space → O(n × W), or O(W) with a single array

And the most important implementation detail to remember:

1D array, 0/1 knapsack       → loop capacity BACKWARDS
1D array, unbounded knapsack → loop capacity FORWARDS

Whenever a problem asks you to pick some items under a limit, or to reach a target sum, think knapsack. Decide whether items can repeat, then choose max, OR, or + to combine the choices.

In the next chapter, we'll apply 2D DP to two strings at once, with the classic LCS and Edit Distance problems.