1. 项目概述从“装满背包”到“最优价值”如果你接触过算法尤其是准备信息学奥赛那么“背包问题”绝对是一个绕不开的经典。它不像某些高深的理论一听就让人头大。恰恰相反它的场景极其生活化你有一个容量有限的背包面前有一堆物品每个物品有自己的重量和价值。你的目标很简单——怎么装能让背包里的总价值最大今天要拆解的是“完全背包问题”。题目编号1268来自经典的《信息学奥赛一本通》。别看它只是书里的一道例题它所代表的“完全背包”模型是动态规划领域里的一块重要基石其思想渗透在无数实际的优化问题中从资源分配到资金规划都能看到它的影子。和它著名的兄弟“0-1背包”每个物品最多选一次不同“完全背包”允许你无限次选取同一种物品。这种“无限供应”的特性让问题的思考方式和解决方法产生了微妙而关键的变化。很多初学者在学完0-1背包后碰到完全背包容易想当然地套用老方法结果要么出错要么效率低下。这道题的价值就在于帮你清晰地划清这两种模型的界限并掌握解决完全背包的“标准动作”。接下来我会把自己在刷题和教学中总结的思路、代码细节和易错点毫无保留地分享出来无论你是正在备赛的选手还是希望夯实动态规划基础的开发者相信都能从中获得可以直接“抄作业”的实战经验。2. 问题核心与思路解析为什么不能直接套用0-1背包在深入代码之前我们必须把“完全背包问题”的骨髓给抽出来理解透。题目通常是这样描述的给定一个容量为V的背包和N种物品。每种物品有无限件可用第i种物品的体积是v[i]价值是w[i]。求解将哪些物品装入背包可使这些物品的总体积不超过背包容量且总价值最大。2.1 与0-1背包的本质区别这是最关键的思维转折点。0-1背包的状态转移方程是dp[j] max(dp[j], dp[j - v[i]] w[i])注意在实现时为了保证每个物品只被计算一次内层对背包容量的循环是从大到小j V; j v[i]; j--遍历的。这是因为dp[j]依赖于上一轮即考虑前i-1件物品时的dp[j - v[i]]。从大到小遍历可以避免本轮的dp[j - v[i]]已经被当前物品更新过从而保证了“只选一次”。那么完全背包呢既然物品无限我在考虑容量为j的背包时完全可能已经装入过若干个当前物品i了。也就是说dp[j]应该依赖于本轮即已经考虑过物品i的dp[j - v[i]]。因为从dp[j - v[i]]转移到dp[j]相当于在dp[j - v[i]]的最优解基础上再添加一个物品i。由于物品无限dp[j - v[i]]这个状态本身可能已经包含了若干个物品i所以这个转移是合法的。这个依赖关系的不同直接导致了内层循环顺序的颠倒完全背包的内层循环对背包容量的遍历是从小到大j v[i]; j V; j。实操心得这里最容易混淆。一个简单的记忆方法是——“0-1背包怕重复所以倒着走完全背包欢迎重复所以正着走”。每次写代码前在心里默念一遍这个区别。2.2 动态规划状态定义我们采用最经典的一维滚动数组解法定义状态dp[j]表示容量为j的背包所能装载物品的最大价值。状态转移方程dp[j] max(dp[j], dp[j - v[i]] w[i])(其中j从小到大遍历)方程形式和0-1背包一样但正是循环顺序的不同赋予了它“无限选取”的含义。当j从小到大遍历时计算dp[j]所用的dp[j - v[i]]可能已经在本次循环中被更新过即已经考虑过放入当前物品i这就实现了多次选取。2.3 初始化与边界条件初始化是动态规划正确起步的关键。对于求最大价值的背包问题dp[0] 0容量为0的背包价值自然是0。其他dp[j]初始化为0。这是因为我们求的是最大值初始化为0表示在没有任何物品时任何容量的背包价值都为0合法状态。如果题目要求恰好装满背包的最大价值则需将dp[0]初始化为0其他dp[j]初始化为一个负无穷表示非法状态但本题是典型的“不超过容量”所以初始化为0即可。3. 代码实现与逐行精讲理论清晰后我们来看代码。这里提供C版本的实现并附上详细的注释。信息学奥赛通常使用C因其运行效率高。#include iostream #include algorithm using namespace std; const int MAXV 10010; // 根据题目数据范围设定容量V的最大值 const int MAXN 10010; // 物品种类N的最大值 int v[MAXN]; // v[i] 存储第i种物品的体积 int w[MAXN]; // w[i] 存储第i种物品的价值 int dp[MAXV]; // dp数组 int main() { int V, N; // V-背包总容量 N-物品种数 cin V N; // 1. 读入数据 for (int i 1; i N; i) { cin v[i] w[i]; } // 2. 初始化dp数组全局变量默认初始化为0这里显式强调逻辑 // dp[0] 0; 其他位置在全局区已为0符合“不超过容量”的初始状态 // 3. 核心动态规划过程 for (int i 1; i N; i) { // 遍历每一种物品 // 关键点内层循环从小到大遍历容量 for (int j v[i]; j V; j) { // 状态转移比较“不选当前物品”和“选当前物品”哪种更优 // dp[j]不选当前物品i继承之前考虑前i-1种物品时的最优解 // dp[j - v[i]] w[i]为当前背包腾出v[i]的空间然后加上物品i的价值 // 由于j从小到大遍历dp[j-v[i]]可能已经包含物品i实现了多次选取 dp[j] max(dp[j], dp[j - v[i]] w[i]); } } // 4. 输出结果 // dp[V] 就是容量为V的背包能装下的最大价值 cout dp[V] endl; return 0; }逐行精讲与避坑指南数据范围与数组大小这是竞赛编程的第一道坎。题目一般会给出V和N的上限比如V 10000, N 10000。我们的数组大小必须至少比这个上限大一点防止越界。const int MAXV 10010;这里的10010就是一个略大于10000的安全值。注意事项永远不要恰好按最大值开数组比如int dp[10000]。因为循环中可能会访问到dp[V]如果V10000数组下标就是0-9999访问dp[10000]会导致越界产生未定义行为可能是WA也可能是诡异的RE。循环起始点内层循环for (int j v[i]; j V; j)。这里j从v[i]开始是一个非常自然的优化。因为如果当前背包容量j连一个物品i都放不下j v[i]那么dp[j]肯定无法通过放入物品i来更新直接继承上一轮的值即可没必要进入判断和max运算。状态转移的语义dp[j] max(dp[j], dp[j - v[i]] w[i])。这行代码是动态规划的灵魂。dp[j]等号右边的代表在本轮更新前容量j背包的最大价值。这个值是在考虑前i-1种物品时得到的。dp[j - v[i]] w[i]代表尝试放入一个物品i后的价值。注意此时的dp[j - v[i]]是已经考虑过当前第i种物品的最优解因为j从小到大遍历。它可能已经包含了0个、1个或多个物品i。 w[i]操作就意味着在它的基础上再增加一个。max操作在这两种策略不拿i和 拿一个i中选更优的。时间复杂度算法的时间复杂度是 O(N * V)空间复杂度是 O(V)。对于题目常见的数据范围V在几千到几万这个复杂度是可以接受的。4. 从理论到实践手算推演与过程模拟看懂代码后我强烈建议你拿出纸笔跟着我模拟一个简单例子这是理解动态规划“填表”过程最有效的方式。假设背包容量V 5物品种类N 2物品1体积v[1]2, 价值w[1]3物品2体积v[2]3, 价值w[2]4初始化dp[0]~dp[5]全部为0。第一轮循环 (i1 处理物品1体积2价值3)内层循环j从2到5j2:dp[2] max(dp[2]0, dp[0]33) 3(放入一个物品1)j3:dp[3] max(dp[3]0, dp[1]303) 3(放入一个物品1剩余容量1无用)j4:dp[4] max(dp[4]0, dp[2]333) 6(这里很关键dp[2]是3代表已经放了一个物品1。现在dp[4]在dp[2]的基础上再放一个物品1价值为6即放两个物品1)j5:dp[5] max(dp[5]0, dp[3]333) 6(放两个物品1剩余容量1无用) 第一轮结束后dp数组为[0, 0, 3, 3, 6, 6]。这表示只考虑物品1时各容量背包的最大价值。可以看到容量4和5都能通过放两个物品1达到价值6。第二轮循环 (i2 处理物品2体积3价值4)内层循环j从3到5j3:dp[3] max(dp[3]3, dp[0]44) 4(不拿物品2价值3拿一个物品2价值4取4)j4:dp[4] max(dp[4]6, dp[1]404) 6(不拿物品2价值6拿一个物品2但剩余容量1无用价值4取6)j5:dp[5] max(dp[5]6, dp[2]4347) 7(关键)这里dp[5]原来是通过放两个物品1达到6。现在考虑放入物品2为物品2腾出容量3查看dp[2]3这是一个只考虑物品1时的最优解代表一个物品1。那么dp[2]47就代表先装一个物品1价值3再装一个物品2价值4总价值7。这比原来的6更优。 第二轮结束后dp数组为[0, 0, 3, 4, 6, 7]。最终结果dp[5] 7。方案是一个物品1 一个物品2。通过这个推演你可以清晰地看到dp数组是如何被逐步更新的。在j4时dp[4]利用了本轮刚更新过的dp[2]值为3从而实现了放入两个物品1。在j5时dp[5]通过dp[2]4实现了物品1和物品2的组合这正是完全背包“无限选取”与“组合优化”能力的体现。5. 常见问题、变形与实战技巧掌握了标准解法我们来看看在实战中容易遇到的问题和一些高阶技巧。5.1 常见错误排查清单问题现象可能原因解决方案输出结果比预期小内层循环顺序错误误用了0-1背包的倒序遍历。检查内层for循环确保j是从v[i]递增到V。程序运行结果错误或随机数组越界。dp或v, w数组开小了。检查题目给出的V和N的最大值将数组大小MAXV和MAXN设置为最大值10或更大。超时 (Time Limit Exceeded)输入规模大O(N*V)复杂度在极限数据下可能卡时。确认算法正确。对于C使用scanf/printf或关闭流同步 (ios::sync_with_stdio(false);) 来加速输入输出。答案正确但感觉不放心对状态转移理解不深担心有遗漏。像第4节那样用小数据手工模拟整个dp表更新过程这是建立信心的最佳方式。5.2 完全背包的经典变形完全背包的模型非常灵活稍作修改就是一道新题。求方案数问“装满容量为V的背包有多少种方法”。状态定义dp[j]表示容量为j的背包的装满方案数。转移方程dp[j] dp[j - v[i]]。初始化dp[0] 1容量为0的背包不放任何物品算一种方案其他为0。循环顺序依然是物品在外层容量在内层从小到大遍历。求最小物品数问“装满容量为V的背包最少需要多少件物品”。状态定义dp[j]表示装满容量为j的背包所需的最少物品数量。转移方程dp[j] min(dp[j], dp[j - v[i]] 1)。注意这里的w[i]恒为1每件物品计数为1。初始化dp[0] 0其他dp[j]初始化为一个很大的数如INF表示无法装满。循环顺序同上完全背包模式。实操心得遇到变形题最关键的一步是重新定义dp数组的含义。一旦定义清楚状态转移方程往往就是dp[j] combine(dp[j], dp[j - v[i]] op w[i])的形式其中combine是max/minop是/*等。然后根据问题要求确定初始化值和循环顺序。5.3 性能优化与技巧虽然O(N*V)是标准复杂度但在一些情况下可以优化物品去重与贪心剪枝体积大价值小必淘汰如果存在两种物品i和j满足v[i] v[j]且w[i] w[j]那么物品j就是完全被物品i淘汰的体积不小价值不高可以直接忽略物品j。性价比排序在某些特定条件下如求最小数量可以按单位体积价值w[i]/v[i]排序优先考虑性价比高的物品有时能结合贪心提前结束。但这在标准完全背包求最大价值中不适用因为物品无限高性价比物品可以一直拿直到容量不够这本质上就是贪心了而贪心对于背包问题并不总是正确考虑物品不能分割。二进制优化思想延伸这不是用于优化标准完全背包而是当题目把“无限件”改为“每种物品有s[i]件”时的多重背包问题。一个朴素的思路是把s[i]件物品拆成s[i]个“0-1物品”但这样复杂度是 O(V * Σs[i])可能太高。二进制优化的思想是将s[i]件物品拆分成若干组每组物品数分别是1, 2, 4, ..., 2^(k-1), s[i] - (2^k -1)使得这些组通过组合能表示出0到s[i]之间的任何取件数。这样就把多重背包转化为了物品数为 log(s[i]) 的0-1背包问题复杂度降为 O(V * Σlog(s[i]))。这是完全背包和0-1背包知识的一个重要结合点。6. 总结与扩展学习路径走到这里你已经掌握了完全背包的标准解法、内在原理、代码实现和常见变形。信息学奥赛一本通上的这道例题就像一把钥匙帮你打开了动态规划中“无限选取”优化问题的大门。我个人在教授和刷题中最大的体会是理解循环顺序背后的“状态依赖”关系远比死记硬背代码更重要。无论是0-1背包的逆序还是完全背包的顺序其本质都是为了满足状态转移时对“历史数据”的特定要求。想不明白的时候就画一张dp表手动填两行一切都会豁然开朗。如果你想在动态规划这条路上走得更远我建议的路径是夯实基础把0-1背包、完全背包、多重背包朴素二进制优化的模板题反复刷熟做到能闭着眼睛写出正确循环顺序。挑战变形去找一些背包问题求方案数、求具体方案、二维费用背包体积重量限制、分组背包每组内互斥的题目。你会发现它们都是基础模型上的扩展。识别模型开始尝试解决一些不那么像“背包”的背包问题。例如零钱兑换问题给定面额无限硬币凑成总额就是标准的完全背包而一些资源分配、预算规划问题也常常能抽象成背包模型。训练自己从问题描述中抽象出“容量”、“物品”、“价值”的能力。最后再分享一个调试小技巧当你觉得程序答案不对又找不到原因时不要只盯着大数据。构造一个像本文第4节那样V5, N2的极小测试案例用cout把每一轮循环后的dp数组全部打印出来然后和你手算的过程一步一步对比。几乎所有的逻辑错误在这种“显微镜”式的调试下都会无所遁形。编程和算法学习很多时候就是需要这样一点耐心和笨功夫。