0/1背包问题可视化

动态规划经典优化问题

0/1背包问题是一个经典的组合优化问题：给定n个物品（每个有重量和价值）和一个容量为W的背包，如何选择物品使得总价值最大，同时不超过背包容量？

物品列表 (容量: 10)
DP表格
最大价值 ?
选中物品
点击"开始"查看动画

动态规划状态定义

设 dp[i][w] 表示考虑前i个物品、容量为w时的最大价值。

  • 不选第i个物品：dp[i][w] = dp[i-1][w]
  • 选第i个物品（需要能装下）：dp[i][w] = dp[i-1][w-wi] + vi
  • 取两者最大值

时间与空间复杂度

指标 复杂度 说明
时间复杂度 O(N × W) N是物品数，W是容量
空间复杂度 O(N × W) 存储DP表格
优化空间 O(W) 使用一维数组，逆序遍历

注意：这是伪多项式时间，因为W可能很大。当W以二进制表示时，算法是指数级的。

应用场景

  • 资源分配问题（预算分配）
  • 货物装载优化
  • 投资组合选择
  • 文件选择备份（磁盘空间限制）
  • 密码学中的子集和问题
资源分配 货运优化 投资决策 组合优化

代码实现

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
    }
}