0-1背包问题

0-1背包问题是动态规划中的经典问题，用于解决有限容量的背包如何装入价值最大的物品组合。其核心特点是每种物品仅有一件，选择装入（1）或不装入（0），因此称为“0-1”背包。

问题定义[编辑 | 编辑源代码]

给定一组物品，每个物品有重量 $w_{i}$ 和价值 $v_{i}$ ，以及一个容量为 $W$ 的背包。目标是在不超过背包容量的前提下，选择物品使总价值最大。

数学形式化表示为： $最大化 \sum_{i = 1}^{n} v_{i} x_{i} 约束条件： \sum_{i = 1}^{n} w_{i} x_{i} \leq W, x_{i} \in {0, 1}$

动态规划解法[编辑 | 编辑源代码]

状态定义[编辑 | 编辑源代码]

定义二维数组dp[i][j]表示前 $i$ 个物品在容量 $j$ 下的最大价值。

状态转移方程[编辑 | 编辑源代码]

对于第 $i$ 个物品，有两种选择： 1. **不装入**：dp[i][j] = dp[i-1][j] 2. **装入**（需剩余容量足够）：dp[i][j] = dp[i-1][j-w_i] + v_i

综合得： $d p [i] [j] = \max (d p [i - 1] [j], d p [i - 1] [j - w_{i}] + v_{i})$

初始化与边界条件[编辑 | 编辑源代码]

dp[0][j] = 0（无物品时价值为0）
dp[i][0] = 0（容量为0时无法装入任何物品）

代码实现[编辑 | 编辑源代码]

以下是Python实现示例：

  
def knapsack_01(weights, values, W):  
    n = len(weights)  
    dp = [[0] * (W + 1) for _ in range(n + 1)]  
    for i in range(1, n + 1):  
        for j in range(1, W + 1):  
            if weights[i-1] <= j:  
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]] + values[i-1])  
            else:  
                dp[i][j] = dp[i-1][j]  
    return dp[n][W]  

# 示例输入  
weights = [2, 3, 4, 5]  
values = [3, 4, 5, 6]  
W = 5  
print(knapsack_01(weights, values, W))  # 输出：7（选择物品0和1）

空间优化[编辑 | 编辑源代码]

可压缩为一维数组：

  
def knapsack_01_optimized(weights, values, W):  
    dp = [0] * (W + 1)  
    for i in range(len(weights)):  
        for j in range(W, weights[i] - 1, -1):  # 逆序避免覆盖  
            dp[j] = max(dp[j], dp[j - weights[i]] + values[i])  
    return dp[W]

示例分析[编辑 | 编辑源代码]

输入与输出[编辑 | 编辑源代码]

**输入**：

 * 重量：[1, 3, 4, 5]  
 * 价值：[1, 4, 5, 7]  
 * 容量：7

**输出**：9（选择物品1和3）

动态规划表[编辑 | 编辑源代码]

实际应用[编辑 | 编辑源代码]

**资源分配**：如云计算中的任务调度。
**投资组合**：在预算内选择收益最高的投资项目。
**密码学**：解决子集和问题。

变种问题[编辑 | 编辑源代码]

**完全背包**：物品可无限选取。
**多重背包**：物品有数量限制。
**分组背包**：物品分组，每组只能选一件。

总结[编辑 | 编辑源代码]

0-1背包问题通过动态规划将指数级复杂度降为 $O (n W)$ ，是理解动态规划思想的重要案例。掌握其状态转移和空间优化技巧，可扩展到更复杂的场景。