01背包

1. 问题描述

想象你是一个小偷，潜入一间宝库。你背着一个容量有限的背包，容量为 W。宝库里有 N 件宝物，每件宝物都有两个属性：

• 重量 (weight): w[i]
• 价值 (value): v[i]

对于每一件宝物，你只有两种选择：拿（放入背包）或者不拿。你不能把一件宝物切开，只拿一部分（这就是“0-1”的含义）。

你的目标是：在背包能装下的前提下，如何选择宝物，才能使背包内宝物的总价值最大？

2. 核心思想分析

为什么贪心算法不行？

初学者可能会想到一些简单的贪心策略：

1. 价值优先：每次都选价值最高的宝物。

   • 反例：背包容量 W=10。宝物A(w=10, v=10)，宝物B(w=3, v=6)，宝物C(w=3, v=6)，宝物D(w=3, v=6)。如果选了A，总价值为10。但选B+C+D，总价值为18。

2. 重量优先：每次都选重量最轻的宝物。

   • 反例：背包容量 W=10。宝物A(w=1, v=1)，宝物B(w=10, v=100)。显然应该选B。

3. 价值密度优先：每次都选 价值/重量 最高的宝物。

   • 反例：背包容量 W=10。宝物A(w=5, v=8)，宝物B(w=6, v=9)，宝物C(w=5, v=7)。
     • 价值密度：A(1.6), B(1.5), C(1.4)。
     • 贪心选择A，背包剩余容量5，价值8。还能装C，总价值 8+7=15，总重量10。
     • 但最优解是选择B和C，总价值 9+7=16，总重量11，装不下。
     • 让我们换个例子：背包 W=6。宝物A(w=3, v=5)，宝物B(w=4, v=6)。
     • 价值密度：A(1.67), B(1.5)。贪心选择A，背包剩余容量3，总价值5。B装不下了。
     • 但最优解是只选B，总价值6。

结论：贪心算法在每一步做出局部最优选择，但这些选择无法保证最终得到全局最优解。问题的关键在于，当前的选择会影响未来的选择空间（选了一个物品会减少背包容量）。

为什么适合动态规划？

0-1背包问题完美符合动态规划的两个核心特征：

1. 最优子结构 (Optimal Substructure)：

   • 问题的最优解包含了其子问题的最优解。
   • 具体来说，对于前 i 个物品的最优解，它一定是在“不放第 i 个物品时，前 i-1 个物品的最优解”和“放了第 i 个物品时，前 i-1 个物品在剩余容量下的最优解”两者之间产生的。

2. 重叠子问题 (Overlapping Subproblems)：

   • 在递归求解时，很多子问题会被反复计算。例如，“在前3个物品中，当容量为5时的最大价值”这个子问题，在后续的决策中可能会被多次用到。DP通过dp表来存储这些子问题的解，避免重复计算。

3. 动态规划解法（二维数组）

我们遵循动态规划的设计四部曲。

第一步：定义状态 (State)

这是最关键的一步。我们需要一个数组来存储子问题的解。这个数组需要包含解决问题所需的所有信息。对于背包问题，信息有两个维度：物品和容量。

我们定义一个二维数组 dp[i][j]： dp[i][j] 表示：从下标为 0 到 i 的物品中任意选择，放入容量为 j 的背包里，所能获得的最大价值。

• i：代表我们当前考虑到了第 i 个物品（从0开始计数）。
• j：代表当前的背包容量。

我们的最终目标就是求 dp[N-1][W]。

第二步：找出状态转移方程 (Function)

状态转移方程是DP的核心，它描述了 dp[i][j] 如何由之前的状态推导出来。

当我们面对第 i 个物品和容量为 j 的背包时，我们有两种决策：

1. 不放入第 i 个物品：

   • 这种情况可能是因为我们主动选择不放，也可能是因为根本放不下（即 j < w[i]）。
   • 如果不放第 i 个物品，那么 dp[i][j] 的值就等于“在前 i-1 个物品中，容量为 j 的背包能获得的最大价值”。
   • 所以：dp[i][j] = dp[i-1][j]

2. 放入第 i 个物品：

   • 这个决策的前提是必须能放得下，即 j >= w[i]。
   • 如果决定放入第 i 个物品，那么背包的价值就增加了 v[i]。同时，背包的容量也减少了 w[i]。
   • 剩下的问题就变成了：“在前 i-1 个物品中，放入容量为 j - w[i] 的背包里，能获得的最大价值是多少？” 这个值正好是 dp[i-1][j - w[i]]。
   • 所以，这种情况下的总价值是：dp[i][j] = v[i] + dp[i-1][j - w[i]]

综合以上两种情况，我们需要取其中的最大值： dp[i][j] = max(不放第i个物品的价值, 放第i个物品的价值)

最终的状态转移方程为：

• 如果 j < w[i] (当前背包容量装不下第i个物品): dp[i][j] = dp[i-1][j]
• 如果 j >= w[i] (能装下第i个物品): dp[i][j] = max(dp[i-1][j], v[i] + dp[i-1][j - w[i]])

第三步：初始化 (Initialization)

我们需要初始化 dp 数组的边界条件，作为递推的起点。

• 第一行 dp[0][j]：只考虑第0个物品。
  • 对于任意容量 j，如果 j >= w[0]，那么 dp[0][j] = v[0]。
  • 如果 j < w[0]，那么 dp[0][j] = 0。
• 第一列 dp[i][0]：当背包容量为0时，什么也装不下，所以价值永远是0。dp[i][0] = 0。

在实际编码中，一个更简单的做法是直接将整个 dp 数组初始化为0，然后直接使用状态转移方程进行迭代。

第四步：确定计算顺序 (Order)

观察状态转移方程，dp[i][j] 依赖于 dp[i-1] 行的值。因此，我们必须先计算完第 i-1 行，才能计算第 i 行。 所以，计算顺序应该是：

• 外层循环遍历物品 i 从 0 到 N-1。
• 内层循环遍历背包容量 j 从 0 到 W。

4. 实例推演

假设有3个物品，背包容量为4。

• 物品0: w=1, v=15
• 物品1: w=3, v=20
• 物品2: w=4, v=30

我们来填充 dp 表 (dp[3][5]，索引从0开始):

详细解释几个关键格子的计算：

• dp[1][3] (考虑物品0,1，容量3):
  • 第1个物品 w[1]=3, v[1]=20。当前容量 j=3。能装下。
  • 不放物品1: 价值为 dp[0][3] = 15。
  • 放物品1: 价值为 v[1] + dp[0][3-w[1]] = 20 + dp[0][0] = 20 + 0 = 20。
  • dp[1][3] = max(15, 20) = 20。
• dp[1][4] (考虑物品0,1，容量4):
  • 第1个物品 w[1]=3, v[1]=20。当前容量 j=4。能装下。
  • 不放物品1: 价值为 dp[0][4] = 15。
  • 放物品1: 价值为 v[1] + dp[0][4-w[1]] = 20 + dp[0][1] = 20 + 15 = 35。
  • dp[1][4] = max(15, 35) = 35。
• dp[2][4] (考虑物品0,1,2，容量4):
  • 第2个物品 w[2]=4, v[2]=30。当前容量 j=4。能装下。
  • 不放物品2: 价值为 dp[1][4] = 35。
  • 放物品2: 价值为 v[2] + dp[1][4-w[2]] = 30 + dp[1][0] = 30 + 0 = 30。
  • dp[2][4] = max(35, 30) = 35。

最终答案是 dp[2][4] = 35。

5. 空间优化（一维数组 / 滚动数组）

我们再次观察状态转移方程：dp[i][j] = max(dp[i-1][j], v[i] + dp[i-1][j - w[i]])。 可以发现，计算第 i 行的状态时，我们只用到了第 i-1 行的数据。之前行的数据都用不到了。这提示我们可以进行空间优化。

我们可以用一个一维数组 dp[j] 来代替二维数组。dp[j] 的含义是：在当前物品迭代轮次中，容量为 j 的背包能获得的最大价值。

如何更新？

如果我们还像之前一样，内层循环 j 从 0 到 W： dp[j] = max(dp[j], v[i] + dp[j - w[i]]) 这里会有一个问题：dp[j] (等号左边) 代表第 i 轮的状态，dp[j] (等号右边的 max 第一个参数) 代表第 i-1 轮的状态。但 dp[j - w[i]] 呢？当我们计算 dp[j] 时，dp[j - w[i]] 可能已经是第 i 轮更新过的值了。这不符合我们从 i-1 轮推导的逻辑。

解决方案：倒序遍历容量 j！

将内层循环改为从 W 向下遍历到 w[i]：

for (int i = 0; i < N; ++i) {
    for (int j = W; j >= w[i]; --j) {
        dp[j] = max(dp[j], v[i] + dp[j - w[i]]);
    }
}

为什么倒序可以？ 当我们计算 dp[j] 时，我们需要用到 dp[j - w[i]] 的值。因为我们是倒序遍历，j - w[i] 比 j 小，所以 dp[j - w[i]] 还没有在本轮（第 i 轮）被更新。它存储的仍然是上一轮（第 i-1 轮）的状态。这恰好满足了我们的状态转移方程的要求！

这样，空间复杂度就从 O(N*W) 优化到了 O(W)。

6. C++ 代码实现

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
// 版本一：使用二维数组
// 时间复杂度: O(N * W)
// 空间复杂度: O(N * W)
int knapsack_2d(int W, const vector<int>& weights, const vector<int>& values) {
    int n = weights.size();
    if (n == 0 || W == 0) {
        return 0;
    }
 
    // dp[i][j]: 从前 i 个物品中选择，放入容量为 j 的背包的最大价值
    // 为了方便处理 i-1，我们将 dp 表大小设为 (n+1) x (W+1)
    // dp[i][j] 表示从前 i 个物品里选
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
 
    // i 代表物品编号 (1 to n), j 代表背包容量
    for (int i = 1; i <= n; ++i) {
        int w = weights[i - 1]; // 当前物品的重量
        int v = values[i - 1];  // 当前物品的价值
 
        for (int j = 1; j <= W; ++j) {
            // 如果当前背包容量装不下第 i 个物品
            if (j < w) {
                dp[i][j] = dp[i - 1][j];
            } else {
                // 不放第 i 个物品 vs 放第 i 个物品
                dp[i][j] = max(dp[i - 1][j], v + dp[i - 1][j - w]);
            }
        }
    }
 
    return dp[n][W];
}
 
// 版本二：使用一维数组（空间优化）
// 时间复杂度: O(N * W)
// 空间复杂度: O(W)
int knapsack_1d(int W, const vector<int>& weights, const vector<int>& values) {
    int n = weights.size();
    if (n == 0 || W == 0) {
        return 0;
    }
 
    // dp[j]: 容量为 j 的背包所能装的最大价值
    vector<int> dp(W + 1, 0);
 
    // 遍历每一个物品
    for (int i = 0; i < n; ++i) {
        int w = weights[i];
        int v = values[i];
        
        // 倒序遍历背包容量，确保 dp[j-w] 是上一轮的状态
        for (int j = W; j >= w; --j) {
            dp[j] = max(dp[j], v + dp[j - w]);
        }
    }
 
    return dp[W];
}
 
int main() {
    vector<int> weights = {1, 3, 4};
    vector<int> values = {15, 20, 30};
    int W = 4;
 
    cout << "Using 2D DP table:" << endl;
    cout << "Max value: " << knapsack_2d(W, weights, values) << endl; // 应输出 35
 
    cout << "\nUsing 1D DP table (space optimized):" << endl;
    cout << "Max value: " << knapsack_1d(W, weights, values) << endl; // 应输出 35
 
    return 0;
}

7. 总结

0-1背包问题是许多更复杂背包问题的基础（如完全背包、多重背包），务必牢固掌握。希望这份详细的讲解对你有所帮助！

完全背包

1. 问题定义

完全背包问题描述如下：

有 N 种物品和一个容量为 C 的背包。第 i 种物品的重量是 w[i]，价值是 v[i]。 与0/1背包不同的是，每种物品都有无限件可用。 问：在不超过背包总容量的前提下，能获得的最大总价值是多少？

关键词：N种物品，背包容量C，每种物品无限件，求最大价值。

2. 与0/1背包的核心区别

要理解完全背包，最好的方法就是和0/1背包进行对比。

• 0/1背包：对于第 i 种物品，你只有两种选择：不放（0个）或者放（1个）。
• 完全背包：对于第 i 种物品，你有很多选择：不放（0个）、放1个、放2个、放3个… 直到放不进去为止。

这个“无限件”的特性，是导致两者解法出现细微但关键差异的根本原因。

3. 核心思想与动态规划

和0/1背包一样，完全背包问题也是一个经典的动态规划（DP）问题。我们同样使用一个DP数组来记录状态。

我们定义一个二维DP数组 dp[i][j]：

dp[i][j] 的含义是：从前 i 种物品中任意选择（每种可选0或多件），放入容量为 j 的背包中所能获得的最大价值。

我们的目标就是求出 dp[N][C]。

4. 状态转移方程推导

对于 dp[i][j]，我们考虑第 i 种物品。同样，我们有两种决策：

1. 不放入第 i 种物品： 如果我们决定不放第 i 种物品，那么 dp[i][j] 的值就等于只考虑前 i-1 种物品放入容量为 j 的背包的最大价值。 即：dp[i][j] = dp[i-1][j]

2. 放入第 i 种物品： 如果我们决定要放第 i 种物品，因为物品有无限件，我们可以放1件、2件、3件…k件。

   • 放1件：价值为 dp[i-1][j - w[i]] + v[i] (前提是 j >= w[i])
   • 放2件：价值为 dp[i-1][j - 2*w[i]] + 2*v[i] (前提是 j >= 2*w[i])
   • …
   • 放k件：价值为 dp[i-1][j - k*w[i]] + k*v[i] (前提是 j >= k*w[i])

dp[i][j] 应该取这所有可能情况中的最大值。所以，朴素的状态转移方程是：

dp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i]] + v[i], dp[i-1][j - 2*w[i]] + 2*v[i], ...)

这个方程需要一个额外的循环来枚举 k，效率较低。我们可以对其进行优化。

优化的关键： 观察上面的式子，我们再写出 dp[i][j - w[i]] 的表达式： dp[i][j - w[i]] = max(dp[i-1][j - w[i]], dp[i-1][j - 2*w[i]] + v[i], ...)

把这个式子两边都加上 v[i]： dp[i][j - w[i]] + v[i] = max(dp[i-1][j - w[i]] + v[i], dp[i-1][j - 2*w[i]] + 2*v[i], ...)

看到了吗？dp[i][j - w[i]] + v[i] 的结果正好是我们朴素方程中“放入第i种物品”那一长串的最大值！

所以，原方程可以简化为： dp[i][j] = max(不放第i件, 放第i件) dp[i][j] = max(dp[i-1][j], dp[i][j - w[i]] + v[i])

最终的状态转移方程（二维）： dp[i][j] = max(dp[i-1][j], dp[i][j - w[i]] + v[i]) (当 j >= w[i] 时)

对比0/1背包的方程：dp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i]] + v[i]) 唯一的区别在于，完全背包的第二项是 dp[i][...]，而0/1背包是 dp[i-1][...]。这个细微差别意义重大：

• dp[i-1][j - w[i]]：表示在背包容量为 j-w[i] 时，我们还没有考虑过物品i。所以加上 v[i] 后，物品i只被放了1次。
• dp[i][j - w[i]]：表示在背包容量为 j-w[i] 时，我们已经考虑过物品i（可能已经放了好几个了）。所以 dp[i][j - w[i]] + v[i] 的含义是：在已经放了若干个物品i的基础上，再放一个。这完美地体现了“无限件”的特性。

5. 代码实现（二维DP）

def unbounded_knapsack_2d(weights, values, capacity):
    n = len(weights)
    # dp[i][j] 表示考虑前i个物品，容量为j时的最大价值
    # 注意：为了方便处理 i-1，通常将dp数组大小设为 (n+1) x (capacity+1)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
 
    # 遍历物品
    for i in range(1, n + 1):
        # 遍历背包容量
        for j in range(1, capacity + 1):
            # 当前物品的索引是 i-1
            w = weights[i-1]
            v = values[i-1]
            
            # 1. 不放第 i 个物品
            dp[i][j] = dp[i-1][j]
            
            # 2. 如果当前容量 j 能装下至少一个物品 i，尝试放入
            if j >= w:
                # 比较“不放”和“放”哪个价值大
                dp[i][j] = max(dp[i][j], dp[i][j - w] + v)
    
    return dp[n][capacity]
 
# 示例
weights = [1, 2, 3]
values = [15, 20, 30]
capacity = 4
print(f"最大价值是: {unbounded_knapsack_2d(weights, values, capacity)}") # 输出应为 60 (4个物品1)

6. 空间优化（一维DP）

观察二维状态转移方程 dp[i][j] = max(dp[i-1][j], dp[i][j - w[i]] + v[i])。 我们发现，计算第 i 行的状态时，只依赖于第 i-1 行（上一行）和第 i 行（本行）的数据。这提示我们可以用滚动数组或一维数组来优化空间。

我们定义一维DP数组 dp[j]： dp[j] 的含义是：容量为 j 的背包所能获得的最大价值。

状态转移方程变为： dp[j] = max(dp[j], dp[j - w[i]] + v[i])

这里的 dp[j] (等号左边) 相当于二维的 dp[i][j]，而 dp[j] (等号右边 max 的第一个参数) 相当于二维的 dp[i-1][j]，dp[j - w[i]] 相当于二维的 dp[i][j - w[i]]。

关键点：循环顺序

为了实现这个等价，我们需要特别注意内层循环（遍历容量 j）的顺序。

• 0/1背包的优化，内层循环必须是从大到小（倒序）。因为 dp[j - w[i]] 必须是上一轮 i-1 的结果，倒序遍历可以保证在计算 dp[j] 时，dp[j - w[i]] 还是未被本次循环更新过的值。
• 完全背包的优化，内层循环必须是从小到大（正序）。因为我们需要 dp[j-w[i]] 是本轮 i 的结果（即dp[i][j-w[i]]），正序遍历可以保证在计算 dp[j] 时，dp[j - w[i]] 已经被本次循环更新过，这恰好实现了“可以重复放第i个物品”的效果。

这是两种背包问题在空间优化后最核心、最本质的区别。

def unbounded_knapsack_1d(weights, values, capacity):
    n = len(weights)
    # dp[j] 表示容量为 j 的背包的最大价值
    dp = [0] * (capacity + 1)
 
    # 遍历物品
    for i in range(n):
        w = weights[i]
        v = values[i]
        # 遍历背包容量 (正序！)
        for j in range(w, capacity + 1):
            dp[j] = max(dp[j], dp[j - w] + v)
    
    return dp[capacity]
 
# 示例
weights = [1, 2, 3]
values = [15, 20, 30]
capacity = 4
print(f"最大价值是 (优化后): {unbounded_knapsack_1d(weights, values, capacity)}") # 输出应为 60

7. 举例说明

我们用一维DP的方式，走一遍上面的例子：weights = [1, 2, 3], values = [15, 20, 30], capacity = 4

初始化: dp = [0, 0, 0, 0, 0]

1. 考虑物品0 (w=1, v=15) for j from 1 to 4:

• j=1: dp[1] = max(dp[1], dp[0] + 15) = 15
• j=2: dp[2] = max(dp[2], dp[1] + 15) = max(0, 15+15) = 30 (dp[1]已经是本轮算出的)
• j=3: dp[3] = max(dp[3], dp[2] + 15) = max(0, 30+15) = 45
• j=4: dp[4] = max(dp[4], dp[3] + 15) = max(0, 45+15) = 60 处理完物品0后, dp 数组变为: [0, 15, 30, 45, 60]

2. 考虑物品1 (w=2, v=20) for j from 2 to 4:

• j=2: dp[2] = max(dp[2], dp[0] + 20) = max(30, 0+20) = 30
• j=3: dp[3] = max(dp[3], dp[1] + 20) = max(45, 15+20) = 45
• j=4: dp[4] = max(dp[4], dp[2] + 20) = max(60, 30+20) = 60 处理完物品1后, dp 数组变为: [0, 15, 30, 45, 60] (值没有变化)

3. 考虑物品2 (w=3, v=30) for j from 3 to 4:

• j=3: dp[3] = max(dp[3], dp[0] + 30) = max(45, 0+30) = 45
• j=4: dp[4] = max(dp[4], dp[1] + 30) = max(60, 15+30) = 60 处理完物品2后, dp 数组变为: [0, 15, 30, 45, 60]

最终结果: dp[4] = 60。 这个结果的含义是：拿4个重量为1的物品，总价值为 4 * 15 = 60。

8. 总结与对比