Knapsack Dynamic Programming

1. Introduction: The Thief's Dilemma

Imagine you are a thief who has broken into a museum. You have a backpack (knapsack) that can hold a maximum weight of 15 kg. You see 4 items:

• A Painting: 12 kg, $4000
• A Vase: 4 kg, $2500
• A Statue: 6 kg, $3000
• A Gem: 5 kg, $3500

You cannot take them all because their combined weight exceeds 15 kg. You cannot split an item in half (you either take it or leave it). How do you maximize your profit?

This is the 0/1 Knapsack Problem. It is the archetypal problem for teaching 2D Dynamic Programming where decisions are constrained by a limited capacity. Mastering Knapsack DP is critical because dozens of popular interview questions (Subset Sum, Partition Equal Subset Sum, Target Sum) are just Knapsack in disguise.

2. Core Concept: The Include/Exclude State

For any Knapsack problem, you are iterating through a list of items, and for each item, you make a binary choice: Include it in the bag, or Exclude it from the bag.

Our state requires two variables:

1. i: The current index of the item we are considering.
2. w: The current available weight capacity in the knapsack.

The DP table is dp[N+1][W+1], where dp[i][w] represents the maximum profit using the first i items, with a knapsack capacity of w.

The Transition Equation: For item i (which has weight wt[i-1] and value val[i-1]):

• If wt[i-1] > w: The item is too heavy. We cannot include it. dp[i][w] = dp[i-1][w] (Value is the same as if we didn't have this item).
• If wt[i-1] <= w: We can choose to Include or Exclude. We want the maximum of both choices!
  • Exclude: dp[i-1][w]
  • Include: val[i-1] + dp[i-1][w - wt[i-1]] (We add its value, and subtract its weight from our capacity, looking up the best profit for the remaining capacity). dp[i][w] = max(Exclude, Include)

3. Beginner Code Example: 0/1 Knapsack (Bottom-Up)

Problem Statement: Given weights wt[] and values val[] of n items, put these items in a knapsack of capacity W to get the maximum total value. You cannot break an item, either pick it or don't (0-1 property).

public class ZeroOneKnapsack {
    public static int knapsack(int W, int[] wt, int[] val, int n) {
        // dp[i][w] matrix
        int[][] dp = new int[n + 1][W + 1];
        
        // Build table in bottom-up manner
        for (int i = 0; i <= n; i++) {
            for (int w = 0; w <= W; w++) {
                
                // Base Case: 0 capacity or 0 items yields 0 profit
                if (i == 0 || w == 0) {
                    dp[i][w] = 0;
                } 
                // Transition: If the item can fit in the current capacity 'w'
                else if (wt[i - 1] <= w) {
                    int exclude = dp[i - 1][w];
                    int include = val[i - 1] + dp[i - 1][w - wt[i - 1]];
                    dp[i][w] = Math.max(exclude, include);
                } 
                // Transition: Item is too heavy
                else {
                    dp[i][w] = dp[i - 1][w];
                }
            }
        }
        
        return dp[n][W]; // Max profit using all n items with capacity W
    }
}

Complexity Analysis:

• Time Complexity: $O(N \times W)$, where $N$ is number of items and $W$ is capacity. (Note: This is "Pseudo-Polynomial", because runtime depends on the numeric value of $W$, not just the size of the array).
• Space Complexity: $O(N \times W)$ for the DP matrix.

4. Intermediate Code Example: Subset Sum (Knapsack Disguise)

Problem Statement: (LeetCode 416 - Partition Equal Subset Sum) Given an integer array nums, return true if you can partition the array into two subsets such that the sum of the elements in both subsets is equal.

The Insight: If we partition the array into two equal subsets, the sum of each subset must be exactly Total_Sum / 2. Therefore, this is just a 0/1 Knapsack problem!

• Items: nums[]
• Knapsack Capacity: Total_Sum / 2
• Goal: Find if we can perfectly fill the knapsack capacity.

public class PartitionSubsetSum {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int num : nums) sum += num;
        
        // If the total sum is odd, we can't possibly divide it by 2 evenly.
        if (sum % 2 != 0) return false;
        
        int target = sum / 2;
        int n = nums.length;
        
        // dp[i][j] = true if subset of first i items can sum to j
        boolean[][] dp = new boolean[n + 1][target + 1];
        
        // Base case: A sum of 0 is always possible (pick no items)
        for (int i = 0; i <= n; i++) dp[i][0] = true;
        
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= target; j++) {
                if (nums[i - 1] <= j) {
                    // Include OR Exclude
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
                } else {
                    // Too big, must Exclude
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        
        return dp[n][target];
    }
}

5. Advanced Code Example: Unbounded Knapsack (Space Optimized)

Problem Statement: (LeetCode 322 - Coin Change) You are given an integer array coins representing coins of different denominations and an integer amount. Return the fewest number of coins that you need to make up that amount. You may use an infinite number of each kind of coin.

This is the Unbounded Knapsack. We can pick the same item over and over again!

The Space Optimization: In 0/1 Knapsack, dp[i] depends strictly on the row above it dp[i-1]. So if we use a 1D array, we must loop backwards to avoid overwriting values we still need. In Unbounded Knapsack, because we can reuse items, dp[w] actually depends on the current row we are building! Therefore, we can just use a 1D array and loop forwards!

import java.util.Arrays;

public class CoinChange {
    public static int coinChange(int[] coins, int amount) {
        // dp[i] represents minimum coins needed to make amount i
        int[] dp = new int[amount + 1];
        
        // Initialize with 'Infinity' (amount + 1 is impossible to reach)
        Arrays.fill(dp, amount + 1);
        dp[0] = 0; // 0 coins needed to make amount 0
        
        // Loop through every coin (Item)
        for (int coin : coins) {
            // Loop forwards through capacities (Unbounded Knapsack!)
            for (int w = coin; w <= amount; w++) {
                // dp[w - coin] represents reusing the SAME coin multiple times
                dp[w] = Math.max(dp[w], dp[w - coin] + 1);
                
                // Oops, the problem asks for MINIMUM coins, so Math.min!
                dp[w] = Math.min(dp[w], dp[w - coin] + 1);
            }
        }
        
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

Complexity Analysis:

• Time Complexity: $O(N \times \text{amount})$.
• Space Complexity: $O(\text{amount})$ for the 1D DP array. We successfully dropped the 2D matrix!

6. Common Mistakes Beginners Make

1. Forgetting the difference between 0/1 and Unbounded loops

   • The Mistake: Using a 1D array for 0/1 Knapsack but iterating the capacity loop forwards.
   • Why it's wrong: If you iterate forwards, you use the newly updated value of dp[w - wt] to calculate dp[w]. This means you just used the item twice! For 0/1 Knapsack with a 1D array, you MUST iterate the inner capacity loop backwards from W down to 0 to ensure you only use values from the previous row.

2. Using standard sorting/Greedy approaches

   • The Mistake: Sorting items by Value/Weight ratio and picking the highest ratios first (Fractional Knapsack approach).
   • Why it's wrong: Fractional Knapsack allows you to cut items in half. 0/1 Knapsack does not. A greedy approach on 0/1 will fail to find optimal combinations that pack the space perfectly. You MUST use DP.

7. Interview Q&A

Q1: How do you know a problem is a Knapsack problem? Answer: You are given an array of items. You have a target limit (weight, sum, target value). For each item, you must make a binary choice (Include/Exclude, +/-, True/False) to reach that target optimally.

Q2: What is the Time Complexity of 0/1 Knapsack? Is it polynomial? Answer: It is $O(N \times W)$. This is called Pseudo-Polynomial. If $W$ is 10, it's fast. But if $W$ is 10 billion (which fits easily in a 64-bit integer), the algorithm will take forever, even if there are only 5 items! A true polynomial algorithm depends ONLY on the number of inputs $N$, not the numeric magnitude of the inputs.

Q3: (LeetCode 494) Target Sum: How does this relate to Knapsack? Answer: You are placing + or - in front of array numbers to reach a target. Mathematically, let $P$ be the set of positive numbers and $N$ be the set of negative numbers. Sum(P) - Sum(N) = Target. We also know Sum(P) + Sum(N) = TotalSum. Adding these equations gives 2 * Sum(P) = Target + TotalSum. So, we just need to find a subset $P$ that equals (Target + TotalSum) / 2. It instantly reduces to the standard Subset Sum 0/1 Knapsack!

8. Practice Problems

1. Partition Equal Subset Sum (LeetCode 416)
   • Goal: Master the standard 0/1 Knapsack logic adapted to booleans.
2. Coin Change (LeetCode 322)
   • Goal: Master the 1D Unbounded Knapsack forward-looping logic.
3. Target Sum (LeetCode 494)
   • Hint: Apply the math trick in Q3 to turn it into a standard subset count problem.

9. Summary

• 0/1 Knapsack: Items can be used exactly once. Choice is Include vs Exclude.
• Unbounded Knapsack: Items can be used infinitely. (e.g., Coin Change).
• Space Optimization: You can always drop the 2D dp[N][W] matrix to a 1D dp[W] array.
• Looping Rule: For 1D space optimization: 0/1 Knapsack requires the inner loop to run Backwards. Unbounded Knapsack requires the inner loop to run Forwards.