编辑“︁0-1背包问题”︁

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

== 问题定义 ==  
给定一组物品，每个物品有重量<math>w_i</math>和价值<math>v_i</math>，以及一个容量为<math>W</math>的背包。目标是在不超过背包容量的前提下，选择物品使总价值最大。  

数学形式化表示为：  
<math>  
\text{最大化} \sum_{i=1}^n v_i x_i \quad \text{约束条件：} \sum_{i=1}^n w_i x_i \leq W, \; x_i \in \{0,1\}  
</math>  

== 动态规划解法 ==  
=== 状态定义 ===  
定义二维数组<code>dp[i][j]</code>表示前<math>i</math>个物品在容量<math>j</math>下的最大价值。  

=== 状态转移方程 ===  
对于第<math>i</math>个物品，有两种选择：  
1. **不装入**：<code>dp[i][j] = dp[i-1][j]</code>  
2. **装入**（需剩余容量足够）：<code>dp[i][j] = dp[i-1][j-w_i] + v_i</code>  

综合得：  
<math>  
dp[i][j] = \max(dp[i-1][j], dp[i-1][j-w_i] + v_i)  
</math>  

=== 初始化与边界条件 ===  
* <code>dp[0][j] = 0</code>（无物品时价值为0）  
* <code>dp[i][0] = 0</code>（容量为0时无法装入任何物品）  

=== 代码实现 ===  
以下是Python实现示例：  
<syntaxhighlight lang="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）  
</syntaxhighlight>  

=== 空间优化 ===  
可压缩为一维数组：  
<syntaxhighlight lang="python">  
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]  
</syntaxhighlight>  

== 示例分析 ==  
=== 输入与输出 ===  
* **输入**：  
  * 重量：<code>[1, 3, 4, 5]</code>  
  * 价值：<code>[1, 4, 5, 7]</code>  
  * 容量：<code>7</code>  
* **输出**：<code>9</code>（选择物品1和3）  

=== 动态规划表 ===  
<mermaid>  
gantt  
    title dp表（部分）  
    dateFormat  X  
    axisFormat %s  
    section 容量  
    0 : 0, 0  
    1 : 0, 1  
    3 : 0, 1, 4  
    5 : 0, 1, 4, 5, 7  
    7 : 0, 1, 4, 5, 9  
</mermaid>  

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

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

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

[[Category:计算机科学]]
[[Category:数据结构与算法]]
[[Category:动态规划]]