0/1 Knapsack (Dynamic Programming)

🎒 0/1 Knapsack - Maximize Value (Capacity = 4)

Items Available:

Item 1

W:1

V:1

Item 2

W:3

V:4

Item 3

W:4

V:5

DP Table [item][capacity]:

Items\Cap	0	1	2	3	4
0	0	0	0	0	0

Decision:

INIT

Base case: 0 items, all capacities = 0 value

Maximum Value So Far:

Progress: 1 / 5

Speed:

Recurrence:

dp[i][w] = max(dp[i-1][w], value[i] + dp[i-1][w-weight[i]])

Choose: exclude item OR include item (if it fits)

🎯 Explain Like I'm 5...

Imagine you're going to a birthday party 🎉 and your mom says you can only carry 5 toys in your backpack! Each toy has a weight and how much FUN it is!

🧸 Your Toys:

• Teddy Bear: weight=2, fun=6 🧸
• Race Car: weight=3, fun=10 🏎️
• Robot: weight=4, fun=12 🤖

🎒 Backpack limit: 5 (can't carry more!)

🤔 Your choices: For EACH toy, you decide: Take it (1) or Leave it (0)?

• Take Teddy (2) + Robot (4) = weight 6 → TOO HEAVY! ❌
• Take Car (3) + Teddy (2) = weight 5, fun 16 → PERFECT! ✅

🚀 The Smart Way: Don't try EVERY combination! Build a table that remembers "what's the best fun I can have with X weight?" Then use those answers to figure out bigger answers. It's like building with LEGO - use small pieces to build bigger things! 🧱

When Should You Use This Pattern?

✓Problems with capacity constraints
✓Optimization problems (maximize/minimize)
✓Items can be included or excluded (binary choice)
✓Need to find subset with maximum/minimum value

📝 Example 1: Classic 0/1 Knapsack

Given weights and values of items, find maximum value that can fit in a knapsack of capacity W.

Step-by-Step Thinking:

Create 2D DP table: dp[i][w] = max value using first i items with capacity w
For each item, decide: include it or exclude it
Include: dp[i][w] = value[i] + dp[i-1][w-weight[i]]
Exclude: dp[i][w] = dp[i-1][w]
Take maximum of both choices!

Knapsack.java

java

public class Knapsack {
    // Bottom-up DP approach
    public static int knapsack(int[] weights, int[] values, int capacity) {
        int n = weights.length;
        // dp[i][w] = max value using first i items with capacity w
        int[][] dp = new int[n + 1][capacity + 1];
        // Build table bottom-up
        for (int i = 1; i <= n; i++) {
            for (int w = 1; w <= capacity; w++) {
                // Option 1: Exclude current item
                int exclude = dp[i - 1][w];
                // Option 2: Include current item (if it fits)
                int include = 0;
                if (weights[i - 1] <= w) {
                    include = values[i - 1] + dp[i - 1][w - weights[i - 1]];
                }
                // Take maximum
                dp[i][w] = Math.max(exclude, include);
            }
        }
        return dp[n][capacity];
    }
    // Space-optimized: Use 1D array
    public static int knapsackOptimized(int[] weights, int[] values, int capacity) {
        int[] dp = new int[capacity + 1];
        // Process each item
        for (int i = 0; i < weights.length; i++) {
            // Traverse backwards to avoid using same item multiple times
            for (int w = capacity; w >= weights[i]; w--) {
                dp[w] = Math.max(dp[w], values[i] + dp[w - weights[i]]);
            }
        }
        return dp[capacity];
    }
    public static void main(String[] args) {
        int[] weights = {2, 3, 1, 4};
        int[] values = {4, 5, 3, 7};
        int capacity = 5;
        System.out.println("Max value (2D DP): " + knapsack(weights, values, capacity));
        System.out.println("Max value (1D DP): " + knapsackOptimized(weights, values, capacity));
        // Output: 10 (take items with weights 1 and 4)
    }
}

📝 Example 2: Equal Subset Sum Partition

Determine if an array can be partitioned into two subsets with equal sum.

EqualPartition.java

java

public class EqualPartition {
    public static boolean canPartition(int[] nums) {
        // Calculate total sum
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        // If odd sum, can't partition equally
        if (sum % 2 != 0) {
            return false;
        }
        int target = sum / 2;
        // Knapsack: can we make sum = target?
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;  // Empty subset has sum 0
        for (int num : nums) {
            // Traverse backwards
            for (int s = target; s >= num; s--) {
                dp[s] = dp[s] || dp[s - num];
            }
        }
        return dp[target];
    }
    public static void main(String[] args) {
        int[] nums1 = {1, 5, 11, 5};
        System.out.println("Can partition [1,5,11,5]: " + canPartition(nums1));
        // Output: true ([1,5,5] and [11])
        int[] nums2 = {1, 2, 3, 5};
        System.out.println("Can partition [1,2,3,5]: " + canPartition(nums2));
        // Output: false
    }
}

📝 Example 3: Subset Sum

Given a set of positive numbers, find if there exists a subset with sum equal to a target.

SubsetSum.java

java

public class SubsetSum {
    public static boolean canPartition(int[] nums, int target) {
        // dp[s] = true if we can make sum s
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;  // Base case: empty subset
        // Process each number
        for (int num : nums) {
            // Check all possible sums (backwards)
            for (int s = target; s >= num; s--) {
                // Can we make sum s by including current number?
                dp[s] = dp[s] || dp[s - num];
            }
        }
        return dp[target];
    }
    // With backtracking to find the actual subset
    public static boolean findSubset(int[] nums, int target) {
        int n = nums.length;
        boolean[][] dp = new boolean[n + 1][target + 1];
        // Base case
        for (int i = 0; i <= n; i++) {
            dp[i][0] = true;
        }
        // Fill table
        for (int i = 1; i <= n; i++) {
            for (int s = 1; s <= target; s++) {
                // Exclude current number
                dp[i][s] = dp[i - 1][s];
                // Include current number (if possible)
                if (s >= nums[i - 1]) {
                    dp[i][s] = dp[i][s] || dp[i - 1][s - nums[i - 1]];
                }
            }
        }
        // Print the subset
        if (dp[n][target]) {
            System.out.print("Subset: [");
            int s = target;
            for (int i = n; i > 0 && s > 0; i--) {
                // Was this item included?
                if (dp[i][s] && !dp[i - 1][s]) {
                    System.out.print(nums[i - 1]);
                    if (s - nums[i - 1] > 0) System.out.print(", ");
                    s -= nums[i - 1];
                }
            }
            System.out.println("]");
        }
        return dp[n][target];
    }
    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 7};
        int target = 6;
        System.out.println("Can make sum " + target + ": " + canPartition(nums, target));
        findSubset(nums, target);
        // Output: true
        // Subset: [3, 2, 1]
    }
}

🔑 Key Points to Remember

1️⃣Each item: include or exclude (0/1 choice)
2️⃣2D DP: O(n × capacity) time and space, 1D: O(capacity) space
3️⃣For 1D DP, traverse backwards to avoid using item multiple times
4️⃣Recurrence: dp[i][w] = max(dp[i-1][w], value[i] + dp[i-1][w-weight[i]])

💪 Practice Problems

• Minimum Subset Sum Difference
• Count of Subset Sum
• Target Sum
• Partition Equal Subset Sum