C++如何实现完全背包问题求解-C++-PHP中文网

完全背包状态转移方程为 dp[j] = max(dp[j], dp[j - weight[i]] + value[i])，内层 j 需升序遍历 weight[i] 到 W；与 0-1 背包区别在于物品可重复使用，故正向遍历确保多次选取。

c++如何实现完全背包问题求解

完全背包和0-1背包的核心区别在于：每个物品可以无限次使用。因此状态转移时，dp[j] 不仅能从 dp[j - weight[i]] 转移来，还要考虑「已经选过第 i 个物品」的情况——也就是从 dp[j - weight[i]] 再加一个，所以必须用正向遍历容量。

正确写法是：dp[j] = max(dp[j], dp[j - weight[i]] + value[i])，且内层循环 j 从 weight[i] 到 W（背包总容量）升序遍历。

常见错误是沿用0-1背包的逆序遍历，结果变成只能选一次；或者把 i 和 j 循环顺序写反，导致逻辑错乱。

用一维 vector dp(W + 1, 0) 实现最简洁，但初始化和更新顺序必须严格：

dp[0] 初始化为 0 是安全的，其余位置也设为 0（求最大价值，非必要不设负无穷）
外层循环遍历物品 i（0 到 n-1），内层循环 j 从 weight[i] 到 W，不可颠倒
若题目要求「恰好装满」，则除 dp[0] 外，其余初始化为 INT_MIN，并在更新时加判断：if (dp[j - weight[i]] != INT_MIN)
注意 weight[i] 为 0 的情况，会导致无限循环或未定义行为，需提前过滤

一维 dp 数组无法直接还原路径，必须额外维护一个选择记录。常用做法是用二维布尔数组 chosen[i][j]，但空间大；更省空间的方式是用一维数组 last[i] 记录达到 dp[j] 时最后加入的物品编号，或用 from[j] 记录前一个容量位置。

C++14

C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。

下载

实际还原时，从 dp[W] 开始倒推：

当 W 达到 1e5 甚至更大，而物品数量 n 很小（比如 ≤ 100），标准 O(nW) 解法会超时或爆内存。这时要考虑优化：

若所有 weight[i] 都较大，可尝试「二进制拆分 + 0-1背包」，但完全背包不适用；正确方向是「单调队列优化」，将内层复杂度降到 O(W) 总体——适用于价值随容量线性变化的场景
更实用的是剪枝：先按单位价值排序，优先处理高性价比物品；对相同重量不同价值的物品，只保留最大价值的那个
如果 value[i] 很小（如 ≤ 1000），可交换状态定义：令 f[v] 表示获得价值 v 所需最小重量，转为 O(n × total_value) 求解

别忽略 int 溢出风险——dp 数组建议用 long long，尤其在价值累加或 W 很大时。