0-1 knapsack Theory

Introduction

Definition: Given n items with weights w[] and values v[], and a knapsack of capacity W, select items to maximize total value without exceeding capacity. Each item is either taken (1) or not taken (0) — binary choice.

0/1 vs. Fractional Knapsack:

0/1: Items are indivisible (binary choice)
Fractional: Items can be partially taken (greedy solution works)

Real-World Applications:

Resource allocation in manufacturing
Budget planning for project portfolios
Data compression optimization
Cryptocurrency arbitrage strategies

Problem Statement

Inputs:

int[] wt = {2, 3, 4, 5} // Item weights
int[] val = {3, 4, 5, 6} // Item values
int W = 8 // Knapsack capacity

Recursive Relation:

dp[i][w] = max( 
    dp[i-1][w],  // Skip item i
    val[i-1] + dp[i-1][w - wt[i-1]]  // Take item i (if w >= wt[i-1])
)

Approaches

1. Naive Recursion

public class KnapsackRecursive {
    public static int knapSack(int W, int[] wt, int[] val, int n) {
        if (n == 0 || W == 0) return 0;
        if (wt[n-1] > W) 
            return knapSack(W, wt, val, n-1);
        else 
            return Math.max(
                knapSack(W, wt, val, n-1),
                val[n-1] + knapSack(W - wt[n-1], wt, val, n-1)
            );
    }
}

Recursion Tree (n=3, W=4):

                         KS(3,4)
                      /          \
            wt[2]=5 <=4?        KS(2,4)
            (Skip)             /        \
                         KS(1,4)       KS(1,1)
                        /     \           /   \
                   KS(0,4) KS(0,1)   KS(0,1) KS(0,-2)

Redundant calls: KS(1,1) computed twice

Complexity:

Time: O(2ⁿ)
Space: O(n) (call stack depth)

2. Memoization (Top-Down DP)

import java.util.Arrays;

public class KnapsackMemoization {
    public static int knapSack(int W, int[] wt, int[] val, int n, int[][] dp) {
        if (n == 0 || W == 0) return 0;
        if (dp[n][W] != -1) return dp[n][W];  // Return cached result
        
        if (wt[n-1] > W) 
            dp[n][W] = knapSack(W, wt, val, n-1, dp);
        else 
            dp[n][W] = Math.max(
                knapSack(W, wt, val, n-1, dp),
                val[n-1] + knapSack(W - wt[n-1], wt, val, n-1, dp)
            );
        return dp[n][W];
    }

    public static void main(String[] args) {
        int[] val = {60, 100, 120};
        int[] wt = {10, 20, 30};
        int W = 50, n = 3;
        int[][] dp = new int[n+1][W+1];
        for (int[] row : dp) Arrays.fill(row, -1);
        System.out.println(knapSack(W, wt, val, n, dp)); // Output: 220
    }
}

Dry Run (n=3, W=50):

Call Stack	Action	dp[n][W] Result
KS(3,50)	max(KS(2,50), 120 + KS(2,20))	220
├─ KS(2,50)	max(KS(1,50), 100 + KS(1,30))	160
└─ KS(2,20)	max(KS(1,20), 100 + KS(1,0))	100

Complexity:

Time: O(n × W)
Space: O(n × W) + Recursion Stack

3. Tabulation (Bottom-Up DP)

public class KnapsackTabulation {
    public static int knapSack(int W, int[] wt, int[] val, int n) {
        int[][] dp = new int[n+1][W+1];
        
        for (int i = 1; i <= n; i++) {
            for (int w = 1; w <= W; w++) {
                if (wt[i-1] <= w) 
                    dp[i][w] = Math.max(
                        dp[i-1][w], 
                        val[i-1] + dp[i-1][w - wt[i-1]]
                    );
                else 
                    dp[i][w] = dp[i-1][w];
            }
        }
        return dp[n][W];
    }
}

DP Table (wt = [1,2,3], val = [10,15,40], W = 5):

`i \ w`	1	2	3	4	5
0	0	0	0	0	0
1	10	10	10	10	10
2	10	15	25	25	25
3	10	15	40	50	55

→ Max Value = 55

Cell [3][5] = max(25, 40 + dp[2][2] = 40 + 15 = 55)

4. Space Optimization

Key Insight: Only previous row needed → use 1D array
Use Reverse Iteration: Prevents overwriting values

public static int knapSackOptimized(int W, int[] wt, int[] val, int n) {
    int[] dp = new int[W+1];
    
    for (int i = 0; i < n; i++) {
        for (int w = W; w >= wt[i]; w--) {
            dp[w] = Math.max(dp[w], val[i] + dp[w - wt[i]]);
        }
    }
    return dp[W];
}

Dry Run (val = [60, 100, 120], wt = [10, 20, 30], W = 50):

Iteration	dp[50]	dp[40]	dp[30]	dp[20]	dp[10]
i = 0	60	60	60	60	60
i = 1	160	160	160	100	60
i = 2	220	180	120	100	60

Complexity Summary

Approach	Time	Space	When to Use
Naive Recursion	O(2ⁿ)	O(n)	Only for very small `n`
Memoization	O(n×W)	O(n×W)	When stack size isn’t a concern
Tabulation	O(n×W)	O(n×W)	Default go-to for most use cases
Space Optimized	O(n×W)	O(W)	When space is limited

Applications & Variants

Real-World Use Cases:

Investment portfolio optimization
Cloud resource allocation
Game item selection

Common Variants:

Variant	Key Difference	Recurrence / Change
Unbounded Knapsack	Reuse items multiple times	Replace `dp[i-1]` with `dp[i]`
Subset Sum	Check if sum exists	Use boolean DP
Equal Partition	Subset with sum = total/2	Reduce to subset sum
Multi-dimensional	Additional constraints (e.g., weight + volume) → 3D DP table	Add more dimensions to DP array

Key Takeaways for Interviews

Identify Knapsack Problems: Look for “max value” + constraint
State Transition: Always frame as pick vs skip
Optimize Space: 1D + reverse iteration for large inputs
Edge Cases:
- W = 0, all weights > W
- Negative weights or values (rare in 0/1)
Testing: Use degenerate test cases, boundary cases

Common Pitfalls:

Missing base case initialization
Forward iteration in space-optimized version
Using 0/1 logic in unbounded problems

“Knapsack is the gateway to DP mastery. Practice variants until you can derive the state transition in your sleep.” — Senior FAANG Interviewer