0/1 背包问题

将 n 种各只有一件的物品装入容量为 W 的背包中，每种物品只能选择装或不装，要求在总重量不超过背包容量的前提下，使得装入物品的总价值最大。

March 5, 2004背包问题1分钟阅读

假设你有一个容量为 $W$ 的背包，现在有 $n$ 种物品，每种物品都有自己的重量 $w_i$ 和价值 $v_i$ 。 “01”的含义是：每种物品只有一件，你只有两个选择——要么把它完整地装入背包（1），要么不装（0）。

目标：在不超过背包容量的前提下，使背包中物品的总价值最大。

该问题具有以下两个核心特征，使其非常适合使用动态规划解决：

最优子结构：大问题的最优解可以由小问题的最优解推导出来。
重叠子问题：在求解过程中，会多次计算相同的子问题。

设 dp[i][j] 表示从前 i 个物品中（物品编号 1 到 $i$ ）选出若干物品，放入容量为 j 的背包中所能获得的最大价值。

$i$ 的取值范围： $0 \sim n$ （ $n$ 是物品总数）。
$j$ 的取值范围： $0 \sim W$ （ $W$ 是背包总容量）。

对于每一个物品 $i$ ，其重量为 $w_i$ ，价值为 $v_i$ ，我们面临“取”或“不取”的决策：

不放入第 $i$ 个物品：

此时价值完全等于“前 $i-1$ 个物品放入容量为 $j$ 的背包”的价值。

结果为： $dp[i-1][j]$
放入第 $i$ 个物品（前提： $j \ge w_i$ ）：

此时价值为“前 $i-1$ 个物品放入容量为 $j - w_i$ 的背包”的价值 + 第 $i$ 个物品本身的价值。

结果为： $dp[i-1][j - w_i] + v_i$

因此，状态转移方程为：

$dp[i][j] = \max(dp[i-1][j], \ dp[i-1][j - w_i] + v_i)$

$dp[0][j] = 0$ （当无物品可选时，价值为 0）。
$dp[i][0] = 0$ （当背包容量为 0 时，价值为 0）。

外层循环遍历物品 ( $i: 1 \to n$ )，内层循环遍历容量 ( $j: 0 \to W$ )。

#include <vector>
#include <algorithm>

/**
 * 0/1 背包问题 - 二维数组实现
 * weights: 物品重量数组，下标从 1 开始保存（weights[0] 为占位符）
 * values: 物品价值数组，下标从 1 开始保存（values[0] 为占位符）
 * W: 背包容量
 */
int solveKnapsack(const std::vector<int>& weights, const std::vector<int>& values, int W) {
    int n = weights.size() - 1; // 实际物品数量
    // dp[i][j] 表示考虑前 i 个物品，容量为 j 时的最大价值
    // 大小为 (n+1) * (W+1)，天然初始化为 0
    std::vector<std::vector<int>> dp(n + 1, std::vector<int>(W + 1, 0));

    // 从下标 1 开始遍历物品
    for (int i = 1; i <= n; ++i) {
        int w = weights[i];
        int v = values[i];

        for (int j = 0; j <= W; ++j) {
            if (j < w) {
                // 容量不足，继承上一轮（不选该物品）的结果
                dp[i][j] = dp[i - 1][j];
            } else {
                // 决策：选与不选，取两者中的最大值
                dp[i][j] = std::max(dp[i - 1][j], dp[i - 1][j - w] + v);
            }
        }
    }

    return dp[n][W];
}

如果你仔细观察状态转移方程，会发现计算 dp[i][j] 时，只需要用到上一行 dp[i-1] 的数据，更早之前的数据完全不需要了。

因此，我们可以把二维数组压缩成一维数组 dp[j]。但这里有一个极容易出错的细节：内层循环必须从大到小（逆序）遍历。

#include <vector>
#include <algorithm>

/**
 * 0/1 背包问题 - 空间优化版 (一维数组)
 * weights: 物品重量数组（下标 1 到 n）
 * values: 物品价值数组（下标 1 到 n）
 * W: 背包容量
 */
int solveKnapsackOptimized(const std::vector<int>& weights, const std::vector<int>& values, int W) {
    int n = weights.size() - 1;
    // 使用一维数组 dp[j] 表示容量为 j 时的最大价值
    std::vector<int> dp(W + 1, 0);

    for (int i = 1; i <= n; ++i) {
        // 内层循环必须逆序遍历，确保计算 dp[j] 时，dp[j-w] 是上一轮（不含当前物品）的状态
        for (int j = W; j >= weights[i]; --j) {
            dp[j] = std::max(dp[j], dp[j - weights[i]] + values[i]);
        }
    }

    return dp[W];
}

为什么必须逆序？

如果从小到大遍历，在计算较大的 dp[j] 时，它所依赖的 dp[j - weight] 可能在当前这轮循环中已经被更新过了（变成了包含当前物品的值）。这就意味着一个物品被重复放了多次，这就变成了“完全背包问题”，而不是“01背包问题”了。逆序遍历保证了更新当前状态时，用到的都是“上一轮”的干净数据。

动态规划

状态定义

状态转移方程

初始化与边界条件

遍历顺序

参考代码

空间优化（一维数组）