13 背包问题 — 完全背包

GESP C++ 六级：背包问题—完全背包

核心目标：掌握完全背包的问题模型、二维DP推导、一维DP空间优化，深入理解“容量正序遍历”的根本原因，能区分“最大价值”“恰好装满”“方案数”三种问法的初始化，能独立完成代码实现与真题变体。
完全背包 = 每件物品可以选无限次；一维DP靠“容量正序”实现无限选取；与01背包的唯一区别就是内层循环方向——01背包倒序，完全背包正序。

一、考纲定位

根据CCF官方考纲，GESP六级明确要求掌握“简单动态规划（一维动态规划、简单背包问题） ”。在GESP六级真题中，完全背包是编程题的最高频考点之一。

完全背包在六级考试中的考查分布：

考点	重要程度	典型真题
完全背包问题模型	★★★★★	条形蛋糕（P17012）、学习小组（P13015）
一维DP空间优化与正序遍历		选择题高频、代码填空
完全背包与01背包的区别		选择题高频
恰好装满的初始化	★★★★☆	编程题
方案数与排列/组合	★★★★☆	编程题
完全背包的变体建模	★★★★★	小杨和整数拆分（P11246）

六级完全背包的命题趋势是“题面包装千变万化，底层模型不变”。真题中，“条形蛋糕”把完全背包包装成切蛋糕问题，“学习小组”把完全背包包装成分组问题，“计算得分”把完全背包包装成字符串分割问题。识别出完全背包模型，是解题的关键。

二、问题模型

有 n 种物品，第 i 种物品重量为 w[i]，价值为 v[i]。背包容量为 W。每种物品可以选择无限次，求背包能装入的最大总价值。

关键约束：每种物品可以选任意多件，因此称为完全背包（Unbounded Knapsack Problem）。

与01背包的唯一区别：01背包每件物品最多选一次，完全背包每件物品可以选无限次。

三、二维DP解法

3.1 状态定义

dp[i][j]：考虑前 i 种物品，背包容量为 j 时能获得的最大价值。

3.2 转移方程

对于第 i 种物品：

不选：dp[i][j] = dp[i-1][j]
选（前提 j >= w[i]）：dp[i][j] = dp[i][j-w[i]] + v[i]

注意这里的区别：01背包选第 i 件时依赖的是 dp[i-1][j-w[i]]（上一行，即前 i-1 件物品的状态），而完全背包选第 i 种物品时依赖的是 dp[i][j-w[i]]（同一行，即已经考虑了第 i 种物品的状态），因为第 i 种物品可以重复选取。

取两者最大值：

if (j >= w[i])
    dp[i][j] = max(dp[i-1][j], dp[i][j-w[i]] + v[i]);
else
    dp[i][j] = dp[i-1][j];

3.3 边界条件

dp[0][j] = 0，表示没有物品时价值为 0。

3.4 代码模板

int dp[105][10005];

for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= W; j++) {
        dp[i][j] = dp[i-1][j];
        if (j >= w[i]) {
            dp[i][j] = max(dp[i][j], dp[i][j-w[i]] + v[i]);
        }
    }
}
cout << dp[n][W] << endl;

复杂度：时间 O(nW)，空间 O(nW)。

四、一维DP空间优化（核心）

4.1 优化思路

完全背包的一维优化与01背包类似，但遍历方向完全不同。

4.2 一维代码模板

int dp[10005] = {0};

for (int i = 1; i <= n; i++) {
    for (int j = w[i]; j <= W; j++) {   // 关键：从小到大（正序）！
        dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
    }
}
cout << dp[W] << endl;

复杂度：时间 O(nW)，空间 O(W)。

4.3 为什么容量必须正序遍历？

这是完全背包最核心、最高频的考点。

正序 j = w[i] → W：当处理到 dp[j] 时，dp[j-w[i]] 已经在本轮循环中被更新过了，也就是说，dp[j-w[i]] 可能已经包含了第 i 种物品。那么 dp[j] = dp[j-w[i]] + v[i] 就相当于在“已经选了第 i 种物品”的基础上，再添加一件，从而实现同一物品被多次选取。
倒序 j = W → w[i]：dp[j-w[i]] 尚未被第 i 种物品更新，代表的是“前 i-1 种物品”的状态。这样第 i 种物品只会被选一次，即退化为01背包。

记忆口诀：01背包倒着走，完全背包正着走。

积木比喻：

01背包：每种积木只有一块，搭完了就不能再用。倒序遍历保证你拿到的积木块永远是“还没用过的”。
完全背包：每种积木无限供应，搭完一块还可以再拿一块。正序遍历让你拿到的积木块“可能已经用过”，于是可以继续累加。

4.4 二维与一维对比

对比项	01背包	完全背包
二维转移	`dp[i-1][j-w]+v`	`dp[i][j-w]+v`
一维容量遍历	倒序 `W→w[i]`	正序 `w[i]→W`
物品使用次数	每件最多1次	每件无限次

五、三种常见问法与初始化

5.1 最大价值（不要求装满）

背包不要求恰好装满，求最大价值。

初始化：dp[j] = 0（所有容量初始为 0）。

int dp[10005] = {0};

5.2 恰好装满

要求背包恰好装满，求最大价值。

初始化：dp[0] = 0，其余 dp[j] = -INF。

const int INF = 1e9;
int dp[10005];
dp[0] = 0;
for (int j = 1; j <= W; j++) dp[j] = -INF;

// 转移同上
if (dp[W] < 0) cout << "无解" << endl;
else cout << dp[W] << endl;

原理：只有容量 0 能由“什么都不装”恰好达到；其他容量初始为 -INF，表示不可达。转移时只有可达状态才能更新。

5.3 方案数统计

组合数（不区分顺序）

求用物品凑出容量 W 的方案数，不区分物品选取顺序。外层遍历物品，内层正序遍历容量。

int dp[10005] = {0};
dp[0] = 1;

for (int i = 1; i <= n; i++) {
    for (int j = w[i]; j <= W; j++) {   // 正序
        dp[j] += dp[j-w[i]];
    }
}
cout << dp[W] << endl;

排列数（区分顺序）

求用物品凑出容量 W 的方案数，区分物品选取顺序。外层遍历容量，内层遍历物品。

int dp[10005] = {0};
dp[0] = 1;

for (int j = 1; j <= W; j++) {          // 外层容量
    for (int i = 1; i <= n; i++) {      // 内层物品
        if (j >= w[i]) {
            dp[j] += dp[j-w[i]];
        }
    }
}
cout << dp[W] << endl;

组合数与排列数的区别：如果求组合数就是外层for循环遍历物品，内层for遍历背包；如果求排列数就是外层for遍历背包，内层for遍历物品。五级/六级考试中，组合数是更常见的考法。

六、完全背包与01背包的对比

对比项	01背包	完全背包
物品使用次数	每件最多1次	每件无限次
二维转移	`dp[i-1][j-w] + v`	`dp[i][j-w] + v`
一维容量遍历	倒序 `W → w[i]`	正序 `w[i] → W`
典型题	采药、装箱	条形蛋糕、学习小组、疯狂的采药
选择题高频	“把01背包容量改成正序会怎样？”	答案：变成完全背包

七、GESP 六级完全背包真题精讲

真题1：条形蛋糕（2026年06月）

题目描述：蛋糕店有一条长度为 n 的长条蛋糕，长度为 i 的蛋糕块价值为 p[i]。店长想知道怎么切才能卖得最多。

建模转化：

物品：长度为 i 的蛋糕块，价值 p[i]
背包容量：蛋糕总长度 n
约束：每种长度可以切任意多块（无限供应）
目标：总长度恰好为 n 时，总价值最大

代码：

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> p(n + 1);
    for (int i = 1; i <= n; i++) cin >> p[i];

    vector<long long> dp(n + 1, 0);
    for (int i = 1; i <= n; i++) {           // 遍历物品（长度）
        for (int j = i; j <= n; j++) {        // 正序遍历容量
            dp[j] = max(dp[j], dp[j - i] + p[i]);
        }
    }
    cout << dp[n] << endl;
    return 0;
}

关键点：本题是“资源分割”问题的典型代表——给定总资源（蛋糕长度），和若干种分割方式（不同长度的切块），每种方式可以无限使用，求最大总价值。

真题2：学习小组（2025年06月）

题目描述：将 n 名学生分成若干个连续编号的小组，每个小组人数为 i 时有对应的奖励值 a[i]，求分组后奖励值之和的最大值。

建模转化：

物品：人数为 i 的小组，价值 a[i]
背包容量：总人数 n
约束：每种人数的小组可以选任意多次

代码：

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<long long> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];

    vector<long long> dp(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j++) {        // 正序
            dp[j] = max(dp[j], dp[j - i] + a[i]);
        }
    }
    cout << dp[n] << endl;
    return 0;
}

易错提醒：本题容易误判为01背包（每个小组人数不同）。但题目并未限制小组人数不能重复，因此同一人数的小组可以出现多次——这是完全背包。

真题3：疯狂的采药

题目描述：LiYuxiang 需要在总时间 t 内采摘草药，每种草药可以无限制地疯狂重复采摘，求最大总价值。

代码：

#include <bits/stdc++.h>
using namespace std;

int main() {
    int t, m;
    cin >> t >> m;
    vector<int> a(m + 1), b(m + 1);
    for (int i = 1; i <= m; i++) cin >> a[i] >> b[i];

    vector<long long> dp(t + 1, 0);
    for (int i = 1; i <= m; i++) {
        for (int j = a[i]; j <= t; j++) {     // 正序
            dp[j] = max(dp[j], dp[j - a[i]] + b[i]);
        }
    }
    cout << dp[t] << endl;
    return 0;
}

关键点：本题是「采药」的进阶版，唯一区别是每种草药可以重复采摘多次。数组需要开 long long 防止溢出。

八、完全背包的变体与建模技巧

变体	转化思路	典型真题
切蛋糕	长度=物品，价值=售价，总量=容量	条形蛋糕
分组问题	人数=物品，奖励=价值，总人数=容量	学习小组
整数拆分	完全平方数=物品，价值=1，目标数=容量	小杨和整数拆分
无限采药	时间=物品，价值=价值，总时间=容量	疯狂的采药
字符串分割	子串长度=物品，得分=价值	计算得分

建模口诀：“每种东西可以无限用，总量作容量，单个贡献作价值” —— 这就是完全背包。

九、易错点汇总

一维DP容量倒序遍历：导致物品只能选一次，退化为01背包。
忘记完全背包是正序遍历：与01背包的倒序恰好相反，这是最高频错误。
二维DP中转移用 dp[i-1][j-w] ：完全背包应该用 dp[i][j-w]（同一行）。
恰好装满忘记初始化：dp[0]=0，其余 -INF，否则无解会被误判为 0。
方案数统计的遍历顺序混淆：组合数用“物品外层+容量内层”，排列数用“容量外层+物品内层”。
dp数组未初始化：全局数组默认 0，局部数组需要手动初始化。
价值/容量溢出：大数用 long long（如疯狂的采药数据范围较大）。
W过大导致数组越界：数组大小要开到 W+1。
建模时误判为01背包：题目若未明确限制每种物品只能选一次，优先考虑完全背包。
容量循环边界写错：j >= w[i]，不能写成 j > w[i]。

十、速查表

需求	写法	关键注意
二维完全背包	`dp[i][j]=max(dp[i-1][j], dp[i][j-w]+v)`	依赖同一行
一维完全背包	`for(j=w[i]; j<=W; j++) dp[j]=max(dp[j], dp[j-w]+v)`	正序
最大价值	`dp[j]=0`	不要求装满
恰好装满	`dp[0]=0`，其余 `-INF`	最后判 `dp[W]<0`
方案数（组合）	外层物品，内层正序容量	`dp[0]=1`
方案数（排列）	外层容量，内层物品	`dp[0]=1`
01 vs 完全	01倒序，完全正序	选择题高频
时间复杂度	O(nW)	空间 O(W)

十一、总结

完全背包是GESP六级动态规划模块的核心模型，与01背包并列为背包问题的两大基础。

完全背包每件物品可以选无限次，选或不选不再是二选一。
二维DP：dp[i][j] = max(dp[i-1][j], dp[i][j-w]+v)，注意是 dp[i] 不是 dp[i-1]。
一维DP去掉第一维，空间从 O(nW) 降为 O(W)。
一维完全背包容量必须从小到大遍历。
倒序遍历会变成01背包，正序遍历才是完全背包——这是两者唯一的区别。
不要求装满：dp 全初始化为 0。
恰好装满：dp[0]=0，其余 -INF。
方案数（组合）：外层物品，内层正序容量，dp[0]=1。
方案数（排列）：外层容量，内层物品。
多练“条形蛋糕”“学习小组”“疯狂的采药”“小杨和整数拆分”四类题。

复习建议：先把一维完全背包的代码写熟，重点记住“正序遍历”与01背包的“倒序遍历”的区别，这是选择题和代码填空的最高频考点；再通过“条形蛋糕”和“学习小组”两道真题，练习把实际问题转化为完全背包模型的能力；然后掌握“恰好装满”和“方案数”的初始化方式；最后对比01背包，整理两者的完整差异表。考试中先判断题目是否满足“每种物品可无限使用”的特征，再确定完全背包模型，套用正序遍历模板，最后检查初始化和循环边界。