0/1 Knapsack Problem Visualization

Classic dynamic programming optimization problem

The 0/1 Knapsack is a classic combinatorial optimization problem: given n items (each with weight and value) and a knapsack of capacity W, how to select items to maximize total value without exceeding capacity?

Item List (Capacity: 10)
DP Table
Maximum Value ?
Selected Items
Click 'Start' to view animation

DP State Definition

Let dp[i][w] represent max value considering first i items with capacity w.

  • Don't take item i: dp[i][w] = dp[i-1][w]
  • Take item i (if it fits): dp[i][w] = dp[i-1][w-wi] + vi
  • Take the maximum of both

Time and Space Complexity

Metric Complexity Description
Time Complexity O(N × W) N is items, W is capacity
Space Complexity O(N × W) Store DP table
Optimized Space O(W) 1D array with reverse iteration

Note: This is pseudo-polynomial time because W can be large. When W is represented in binary, algorithm is exponential.

Applications

  • Resource allocation (budget allocation)
  • Cargo loading optimization
  • Investment portfolio selection
  • File backup selection (disk space limit)
  • Subset sum problem in cryptography
Resource Allocation Cargo Optimization Investment Combinatorial Optimization

Implementation

def knapsack_01(weights, values, capacity):
    """0/1背包问题 - 二维DP"""
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for w in range(capacity + 1):
            # 不选第i个物品
            dp[i][w] = dp[i - 1][w]
            
            # 选第i个物品
            if w >= weights[i - 1]:
                dp[i][w] = max(dp[i][w],
                    dp[i - 1][w - weights[i - 1]] + values[i - 1])
    
    return dp[n][capacity]


def knapsack_01_optimized(weights, values, capacity):
    """0/1背包问题 - 空间优化O(W)"""
    dp = [0] * (capacity + 1)
    
    for i in range(len(weights)):
        # 逆序遍历，保证每个物品只使用一次
        for w in range(capacity, weights[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    
    return dp[capacity]


# 使用示例
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
capacity = 8
print(knapsack_01(weights, values, capacity))  # 10
public class Knapsack {
    
    /**
     * 0/1背包问题 - 二维DP
     */
    public static int knapsack01(
            int[] weights, int[] values, int capacity) {
        
        int n = weights.length;
        int[][] dp = new int[n + 1][capacity + 1];
        
        for (int i = 1; i <= n; i++) {
            for (int w = 0; w <= capacity; w++) {
                // 不选第i个物品
                dp[i][w] = dp[i - 1][w];
                
                // 选第i个物品
                if (w >= weights[i - 1]) {
                    dp[i][w] = Math.max(dp[i][w],
                        dp[i - 1][w - weights[i - 1]] + values[i - 1]);
                }
            }
        }
        
        return dp[n][capacity];
    }
    
    /**
     * 0/1背包问题 - 空间优化O(W)
     */
    public static int knapsack01Optimized(
            int[] weights, int[] values, int capacity) {
        
        int[] dp = new int[capacity + 1];
        
        for (int i = 0; i < weights.length; i++) {
            // 逆序遍历
            for (int w = capacity; w >= weights[i]; w--) {
                dp[w] = Math.max(dp[w], 
                    dp[w - weights[i]] + values[i]);
            }
        }
        
        return dp[capacity];
    }
    
    public static void main(String[] args) {
        int[] weights = {2, 3, 4, 5};
        int[] values = {3, 4, 5, 6};
        System.out.println(knapsack01(weights, values, 8));  // 10
    }
}