c++中如何实现背包问题_c++ 01背包动态规划解法

二维dpi定义最稳妥，因逻辑清晰、不易出错；初始化全0即可满足边界条件；转移时需判断j≥weight[i-1]避免越界；一维优化须倒序遍历以防重复选取。

为什么 dp[i][j] 定义成「前 i 个物品、容量为 j 时的最大价值」最稳妥

很多初学者会尝试用 dp[j] 一维数组直接推，但容易搞错遍历顺序或覆盖未使用的状态。二维定义虽然多占空间，但逻辑清晰、不易出错，尤其在调试和理解转移关系时更可靠。

关键点在于：每个物品只能选 0 次或 1 次，所以状态转移必须区分「不选第 i 个」和「选第 i 个」两种情况：

• 不选：dp[i-1][j]
• 选（前提是 j >= weight[i-1]）：dp[i-1][j - weight[i-1]] + value[i-1]

注意物品数组通常从 0 开始索引，所以第 i 个物品对应 weight[i-1] 和 value[i-1]。

如何正确初始化 dp 数组并避免越界访问

初始化时，dp[0][j] 表示「前 0 个物品」能装下的最大价值，显然全为 0；dp[i][0] 表示「容量为 0」时的价值，也全为 0。但实际编码中，只要把整个 dp 数组初始化为 0，就能自然满足这两个边界条件。

立即学习“C++免费学习笔记（深入）”；

真正容易出错的是状态转移中的下标检查：

VIVA

一个免费的AI创意视觉设计平台

下载

• 必须判断 j >= weight[i-1] 才能尝试选择第 i 个物品，否则跳过
• 二维数组大小应为 (n+1) x (W+1)，其中 n 是物品数量，W 是背包容量
• 如果用 vector>，记得先 resize 正确维度，否则运行时可能崩溃

一维优化版 dp[j] 的核心约束和遍历方向

一维写法节省空间，但必须倒序遍历容量 j（从 W 到 weight[i-1]），否则会重复使用刚更新过的值，导致一个物品被多次选取（退化成完全背包）。

常见错误现象：dp[W] 结果明显偏大，甚至超过所有物品价值之和——大概率是正向遍历了 j。

实操建议：

• 初始化 vector dp(W+1, 0)
• 外层循环 i 从 0 到 n-1
• 内层循环 j 从 W 降序到 weight[i]（含）
• 转移式：dp[j] = max(dp[j], dp[j - weight[i]] + value[i])

#include 
#include 
using namespace std;
int knapsack01(const vector& weight, const vector& value, int W) {
int n = weight.size();
vector> dp(n + 1, vector(W + 1, 0));
for (int i = 1; i zuojiankuohaophpcn= n; ++i) {
    for (int j = 0; j zuojiankuohaophpcn= W; ++j) {
        dp[i][j] = dp[i-1][j]; // 不选第 i 个
        if (j >= weight[i-1]) {
            dp[i][j] = max(dp[i][j], dp[i-1][j - weight[i-1]] + value[i-1]);
        }
    }
}
return dp[n][W];
}
一维优化看似简洁，但一旦数据规模变大或需要输出具体选了哪些物品，二维结构反而更容易回溯路径。别为了省几 MB 内存，让逻辑变得脆弱。