一、问题理解：什么是完全背包？
先明确完全背包的核心定义，避免与 0-1 背包混淆：
给定一个容量为
V的背包，n个物品，每个物品有体积volume[i]和价值value[i]，每个物品可以无限次选取。要求在不超过背包容量的前提下，选择物品使总价值最大。二、第一版代码：暴力递归（思路对但效率极低）
这是我最初的实现，完全贴合 “选 / 不选” 的递归逻辑，但存在诸多致命问题：
#include <iostream> using namespace std; int bag1(int value[], int volume[], int current_volume, int n) { if (current_volume == 0 || n == 0) { return 0; } if (current_volume < volume[n - 1]) { return bag1(value, volume, current_volume, n - 1); } if (current_volume >= volume[n - 1]) { return bag1(value, volume, current_volume - volume[n - 1], n) + value[n - 1] > bag1(value, volume, current_volume, n - 1) ? bag1(value, volume, current_volume - volume[n - 1], n) + value[n - 1] : bag1(value, volume, current_volume, n - 1); } } int main1() { // 请在此输入您的代码 int N, V; cin >> N >> V; int volume[10000], value[10000]; for (int i = 0; i < N; i++) { cin >> volume[i] >> value[i]; } cout << bag1(value, volume, V, N); return 0; }第一版代码的核心问题
- 重复计算子问题（效率灾难）递归过程中，大量相同的 “剩余容量
current_volume+ 剩余物品数n” 组合被反复计算。比如计算bag1(..., 5, 2)时，会多次调用bag1(..., 3, 2)，时间复杂度远超 O(2^n)（因为允许重复选物品，递归分支更多），当n>20时几乎无法运行。- 语法与规范性问题
- 函数末尾无默认返回值，编译器会报警告；
int volume[10000], value[10000]是 C99 变长数组特性，C++ 标准不支持，在 MSVC 等编译器中直接报错；- 递归栈溢出风险递归深度随物品数和容量增加而剧增，当
N或V较大时，会触发栈溢出。- 代码冗余三元运算符重复调用递归函数，同一子问题被计算多次（比如
bag1(..., current_volume - volume[n-1], n)被调用了两次）。三、第一轮优化：记忆化搜索（递归 + 备忘录）
针对 “重复计算子问题” 的核心痛点，我首先想到用记忆化搜索—— 新增一个 “备忘录” 数组，记录已计算过的子问题结果，避免重复递归。这是对暴力递归最直接的优化，且能保留递归的直观逻辑。
#include <iostream> #include <vector> #include <cstring> // 用于memset初始化 using namespace std; // 备忘录：memo[n][v] 表示“前n个物品、剩余容量v”时的最大价值 int** memo; // 封装max函数，避免冗余的三元运算符 int max(int a, int b) { return a > b ? a : b; } // 记忆化搜索版完全背包 int bag_memo(vector<int>& value, vector<int>& volume, int current_volume, int n) { // 基准条件 if (current_volume == 0 || n == 0) { return 0; } // 核心优化：查备忘录，有结果直接返回 if (memo[n][current_volume] != -1) { return memo[n][current_volume]; } int res; // 当前物品体积超容量，只能不选 if (current_volume < volume[n - 1]) { res = bag_memo(value, volume, current_volume, n - 1); } else { // 选当前物品（n不递减，可重复选） vs 不选当前物品 int select = bag_memo(value, volume, current_volume - volume[n - 1], n) + value[n - 1]; int not_select = bag_memo(value, volume, current_volume, n - 1); res = max(select, not_select); } // 存入备忘录，供后续复用 memo[n][current_volume] = res; return res; } int main() { int N, V; cin >> N >> V; // 用vector替代变长数组，兼容所有C++编译器 vector<int> volume(N), value(N); for (int i = 0; i < N; i++) { cin >> volume[i] >> value[i]; } // 初始化备忘录：(n+1)行（物品数）、(V+1)列（容量） memo = new int*[N + 1]; for (int i = 0; i <= N; i++) { memo[i] = new int[V + 1]; // 初始值-1，表示该子问题未计算 memset(memo[i], -1, (V + 1) * sizeof(int)); } int max_value = bag_memo(value, volume, V, N); cout << max_value << endl; // 释放内存，避免内存泄漏 for (int i = 0; i <= N; i++) { delete[] memo[i]; } delete[] memo; return 0; }关键优化点详解
- 备忘录的核心作用
memo[n][v]缓存 “前 n 个物品、剩余容量 v” 的最大价值，每个子问题仅计算一次，时间复杂度从指数级骤降到 O(n∗V)（n为物品数，V为背包容量）。- 修复代码冗余将 “选 / 不选” 的递归调用结果先保存到变量，再用
max函数比较，避免同一子问题被重复调用。- 规范性优化
- 用
vector替代变长数组，解决编译器兼容性问题；- 补充内存释放逻辑，符合 C++ 内存管理规范；
- 完全背包的递归特性选当前物品时，递归参数是
n而非n-1—— 这是完全背包与 0-1 背包的核心区别，保证了物品可以被重复选取。四、第二轮优化：迭代版二维 DP（消除递归栈）
记忆化搜索解决了效率问题，但递归仍有栈开销。我进一步将递归逻辑转化为迭代填充二维 DP 表，彻底摆脱递归，这也是理解完全背包状态转移的关键一步。
优化后代码（二维 DP）
#include <iostream> using namespace std; int max(int a, int b) { return a > b ? a : b; } int bag(int value[], int volume[], int total_volume, int n) { int max_value[n+1][total_volume+1];//max_value[i][j]表示容量为j时，前i个物品中挑选能选到的最大值 for (int i = 0; i <= n; i++) { max_value[i][0] = 0; } for (int j = 0; j <= total_volume; j++) { max_value[0][j] = 0; } for (int i = 1; i <= n; i++) { for (int j = 1; j <= total_volume; j++) { if (volume[i - 1] > j) { max_value[i][j] = max_value[i - 1][j]; } else { max_value[i][j] = max(max_value[i][j - volume[i - 1]] + value[i - 1], max_value[i - 1][j]); } } } return max_value[n][total_volume]; } int main() { // 请在此输入您的代码 int N, V; cin >> N >> V; int volume[N], value[N]; for (int i = 0; i < N; i++) { cin >> volume[i] >> value[i]; } cout << bag(value, volume, V, N); return 0; }关键优化点详解
- 完全背包的状态转移方程（核心）这是与 0-1 背包最核心的区别，我用公式清晰总结：dp[i][j]={dp[i−1][j]max(dp[i−1][j],dp[i][j−volume[i−1]]+value[i−1])若 volume[i−1]>j(物品体积超容量，不选)否则（选/不选取最大值）选当前物品时，用
dp[i][j-volume[i-1]]而非dp[i-1][j-volume[i-1]]—— 这意味着 “选了当前物品后，仍可以继续选该物品”，实现了 “无限次选取” 的逻辑。- 消除递归栈迭代方式无函数调用开销，避免了栈溢出风险，执行效率更高；
- 状态定义更直观
dp[i][j]直接对应 “前 i 个物品、容量 j” 的状态，新手更容易理解 “状态” 和 “决策” 的关系。五、终极优化：一维 DP（空间压缩到极致）
观察二维 DP 的状态转移方程可以发现：
dp[i][j]仅依赖dp[i-1][j]（上一行同列）和dp[i][j-volume[i-1]]（当前行左侧列）。因此，我可以将二维数组压缩为一维数组，空间复杂度从 O(n∗V) 降到 O(V)—— 这是完全背包的最优实现。#include <iostream> #include <vector> using namespace std; int max(int a, int b) { return a > b ? a : b; } // 一维DP版完全背包（空间最优，推荐） int bag_dp_1d(vector<int>& value, vector<int>& volume, int total_volume, int n) { // 状态定义：dp[j] 表示“背包容量j”时的最大价值 vector<int> dp(total_volume + 1, 0); // 遍历每个物品 for (int i = 0; i < n; i++) { // 完全背包核心：容量正序遍历（允许重复选当前物品） for (int j = volume[i]; j <= total_volume; j++) { dp[j] = max(dp[j], dp[j - volume[i]] + value[i]); } } return dp[total_volume]; } int main() { int N, V; cin >> N >> V; vector<int> volume(N), value(N); for (int i = 0; i < N; i++) { cin >> volume[i] >> value[i]; } cout << bag_dp_1d(value, volume, V, N) << endl; return 0; }关键优化点详解
- 空间压缩原理一维数组
dp[j]复用了二维数组的 “当前行” 数据，每次处理新物品时，从左到右（正序）更新，保证dp[j-volume[i]]已经包含了 “选当前物品多次” 的结果。- 完全背包的一维核心：正序遍历容量这是与 0-1 背包最直观的区别：
- 0-1 背包：容量逆序遍历（避免重复选同一物品）；
- 完全背包：容量正序遍历（允许重复选同一物品）。正序遍历会让
dp[j]在更新时，优先使用已更新的dp[j-volume[i]]（包含当前物品的选取结果），从而实现 “无限次选取”。- 代码极简且高效一维 DP 是完全背包的工业级写法，代码行数最少、空间占用最小，也是面试和竞赛中最常考察的版本。
六、总结：完全背包优化的核心思想
从暴力递归到一维 DP，我的优化过程本质上是对 “动态规划核心思想” 的逐步落地，同时紧扣完全背包的独特性：
- 重叠子问题：用备忘录 / DP 表缓存重复计算的子问题，将指数级时间复杂度降到多项式级别；
- 最优子结构：“选 / 不选” 的决策依赖子问题的最优解，且完全背包通过 “选物品时不递减物品数（递归）/ 用当前行状态（二维 DP）/ 正序遍历容量（一维 DP）” 实现 “无限次选取”；
- 空间压缩：通过观察状态转移的依赖关系，移除冗余的物品维度，实现空间最优。
对于新手来说，建议按 “暴力递归→记忆化搜索→二维 DP→一维 DP” 的顺序学习：先理解递归的 “选 / 不选” 逻辑，再掌握二维 DP 的状态转移，最后吃透一维 DP 的正序遍历技巧 —— 这不仅能解决完全背包问题，也能为后续学习 “多重背包”“混合背包” 等扩展问题打下基础。
核心要点再强调：完全背包与 0-1 背包的唯一核心区别，就是 “选物品时是否允许重复选”—— 反映在代码上，递归是 n 是否递减、二维 DP 是用 i 还是 i-1、一维 DP 是容量正序还是逆序。抓住这一点，就能彻底区分两类背包问题。