Knapsack

The 0/1 Knapsack problem: Given items with weights and values, select items to maximize value without exceeding weight capacity. Each item can be chosen at most once.

Problem Statement

Given:
- n items, each with weight w[i] and value v[i]
- knapsack capacity W

Find: Maximum total value without exceeding capacity W

Recursive Solution

// Time: O(2^n), Space: O(n)
public int knapsackRecursive(int[] wt, int[] val, int W, int n) {
    if (n == 0 || W == 0) return 0;
    
    // If current item's weight > remaining capacity, skip it
    if (wt[n - 1] > W) {
        return knapsackRecursive(wt, val, W, n - 1);
    }
    
    // Max of: (include item) vs (exclude item)
    return Math.max(
        val[n - 1] + knapsackRecursive(wt, val, W - wt[n - 1], n - 1),
        knapsackRecursive(wt, val, W, n - 1)
    );
}

Memoization (Top-Down)

public int knapsackMemo(int[] wt, int[] val, int W, int n, int[][] memo) {
    if (n == 0 || W == 0) return 0;
    if (memo[n][W] != -1) return memo[n][W];
    
    if (wt[n - 1] > W) {
        memo[n][W] = knapsackMemo(wt, val, W, n - 1, memo);
    } else {
        memo[n][W] = Math.max(
            val[n - 1] + knapsackMemo(wt, val, W - wt[n - 1], n - 1, memo),
            knapsackMemo(wt, val, W, n - 1, memo)
        );
    }
    
    return memo[n][W];
}

// Usage:
int[][] memo = new int[n + 1][W + 1];
for (int[] row : memo) Arrays.fill(row, -1);
int result = knapsackMemo(wt, val, W, n, memo);

Tabulation (Bottom-Up)

public int knapsackTab(int[] wt, int[] val, int W, int n) {
    int[][] dp = new int[n + 1][W + 1];
    
    // Base case: 0 items or 0 capacity = 0 value
    for (int i = 0; i <= n; i++) dp[i][0] = 0;
    for (int j = 0; j <= W; j++) dp[0][j] = 0;
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= W; j++) {
            if (wt[i - 1] <= j) {
                // Can include item i: max(include, exclude)
                dp[i][j] = Math.max(
                    val[i - 1] + dp[i - 1][j - wt[i - 1]],
                    dp[i - 1][j]
                );
            } else {
                // Cannot include item i
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    
    return dp[n][W];
}

Space-Optimized (1D Array)

// O(n*W) time, O(W) space
public int knapsackOptimized(int[] wt, int[] val, int W, int n) {
    int[] dp = new int[W + 1];
    
    for (int i = 0; i < n; i++) {
        // Traverse backwards to avoid using same item twice
        for (int j = W; j >= wt[i]; j--) {
            dp[j] = Math.max(dp[j], dp[j - wt[i]] + val[i]);
        }
    }
    
    return dp[W];
}

// IMPORTANT: Traverse backwards for 0/1 Knapsack!
// Forward traversal = Unbounded Knapsack (can reuse items)

Trace Example

Items: wt=[1,3,4,5], val=[1,4,5,7], W=7

 dp[0..7] after each item:
Initial: [0,0,0,0,0,0,0,0]
Item 1 (w=1,v=1): [0,1,1,1,1,1,1,1]
Item 2 (w=3,v=4): [0,1,1,4,5,5,5,5]
Item 3 (w=4,v=5): [0,1,1,4,5,6,6,9]
Item 4 (w=5,v=7): [0,1,1,4,5,7,8,9]

Answer: dp[7] = 9 (items 2 and 4, or items 1,2,3)

Unbounded Knapsack

Items can be used unlimited times.

// Only difference: traverse capacity forward
public int unboundedKnapsack(int[] wt, int[] val, int W) {
    int[] dp = new int[W + 1];
    
    for (int i = 0; i < wt.length; i++) {
        for (int j = wt[i]; j <= W; j++) {  // FORWARD traversal!
            dp[j] = Math.max(dp[j], dp[j - wt[i]] + val[i]);
        }
    }
    
    return dp[W];
}

Subset Sum Problem

// Check if subset with given sum exists
public boolean subsetSum(int[] arr, int sum) {
    int n = arr.length;
    boolean[][] dp = new boolean[n + 1][sum + 1];
    
    // Base case: sum 0 is always possible (empty subset)
    for (int i = 0; i <= n; i++) dp[i][0] = true;
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= sum; j++) {
            if (arr[i - 1] > j) {
                dp[i][j] = dp[i - 1][j];  // Cannot include
            } else {
                dp[i][j] = dp[i - 1][j] || dp[i - 1][j - arr[i - 1]];
            }
        }
    }
    
    return dp[n][sum];
}

// Space-optimized
public boolean subsetSumOptimized(int[] arr, int sum) {
    boolean[] dp = new boolean[sum + 1];
    dp[0] = true;
    
    for (int num : arr) {
        for (int j = sum; j >= num; j--) {
            dp[j] = dp[j] || dp[j - num];
        }
    }
    
    return dp[sum];
}

Partition Equal Subset Sum

// Can array be partitioned into two subsets with equal sum?
public boolean canPartition(int[] nums) {
    int totalSum = 0;
    for (int num : nums) totalSum += num;
    
    // Odd sum cannot be partitioned equally
    if (totalSum % 2 != 0) return false;
    
    int target = totalSum / 2;
    boolean[] dp = new boolean[target + 1];
    dp[0] = true;
    
    for (int num : nums) {
        for (int j = target; j >= num; j--) {
            dp[j] = dp[j] || dp[j - num];
        }
    }
    
    return dp[target];
}

Coin Change (Minimum Coins)

// Find minimum coins to make amount
public int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, amount + 1);  // Initialize with impossible value
    dp[0] = 0;
    
    for (int i = 1; i <= amount; i++) {
        for (int coin : coins) {
            if (coin <= i) {
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
    }
    
    return dp[amount] > amount ? -1 : dp[amount];
}

Coin Change II (Number of Ways)

// Find number of combinations to make amount
public int change(int amount, int[] coins) {
    int[] dp = new int[amount + 1];
    dp[0] = 1;
    
    for (int coin : coins) {
        for (int i = coin; i <= amount; i++) {
            dp[i] += dp[i - coin];
        }
    }
    
    return dp[amount];
}

Knapsack Pattern Recognition

Problem	Type	Key Difference
0/1 Knapsack	Each item once	Traverse capacity backward
Unbounded Knapsack	Unlimited items	Traverse capacity forward
Subset Sum	Boolean (exists?)	Use boolean dp
Partition Equal	0/1 with sum/2 target	Check total sum first
Coin Change	Unbounded + min/count	Different initialization

Amazon Relevance

• Subset Sum / Partition: Resource allocation, load balancing
• Coin Change: Payment systems, making change
• Knapsack: Budget optimization, feature selection