一、开篇引言本文核心定位——将理论落地通过真题拆解帮大家吃透0-1、完全、多重背包的实战用法。毕竟算法学习从来不是“背公式”而是“练真题”只有亲手敲代码、踩坑、调试才能真正掌握解题思路。真题价值这三道题可不是随便选的P10480-1背包入门、P1616完全背包拓展、P1776多重背包优化刚好覆盖背包问题的三大核心分类而且都是算法入门必刷、面试高频复刻题——很多大厂面试的基础背包题都是这三道题的变种刷会它们相当于掌握了80%的基础背包实战场景。博客核心目标每道题我都会从“题干分析→思路拆解→代码实现→易错点提醒”逐步讲解不跳步、不堆砌专业术语帮大家掌握“把题干转化为背包模型”的核心能力避开实战中容易踩的坑让新手也能轻松跟上。阅读前提建议大家先阅读博主的另一篇博客《动态规划之背包问题详解从入门到实战》掌握背包问题的核心理论状态定义、转移方程、遍历顺序同时具备基础的C语法能力数组、循环、输入输出。如果还没看基础篇也可以先收藏本文看完基础篇再回头刷效果会更好哦二、真题解析准备背包问题实战核心模板回顾在正式拆解真题前咱们花2分钟快速回顾一下核心知识点避免解题时混淆思路——毕竟基础打牢了真题拆解才能事半功倍这一步千万别跳过核心梳理三类背包的核心差异其实就两点物品选择次数和遍历顺序。0-1背包每种物品选1次→ 容量倒序遍历完全背包每种物品选无限次→ 容量正序遍历多重背包每种物品选有限次→ 二进制拆分后按0-1背包逻辑容量倒序。记准这一点解题时就不会慌。通用解题步骤实战版这是我总结的“万能模板”所有背包真题都能套用记好啦题干转化找物品、容量、目标的对应关系→ 状态定义明确dp数组的含义→ 推导转移方程核心逻辑→ 初始化边界条件→ 确定遍历顺序避坑关键→ 代码实现 → 调试找bug技巧。工具提醒咱们用C刷题有两个小细节要注意一是数组初始化避免随机值导致错误二是输入输出效率数据量大时用cin可能超时不过这三道题用cin完全够用另外一定要注意数组下标越界这是新手最容易踩的坑之一三、经典真题逐题详解核心部分重点来啦这一部分咱们逐题拆解每道题都结合我给大家准备的完整代码一步步讲透遇到关键代码会详细注释保证大家能看懂、能复制、能运行还能举一反三。3.1 0-1背包真题P1048 采药入门必刷作为0-1背包的入门真题P1048简直是“送分题”但很多新手第一次做还是会踩坑咱们慢慢拆解把每一步都讲明白。题干解析咱们先提炼题干核心条件把它转化为背包模型——毕竟解题的第一步就是“找对应关系”。题干说采药时间有限对应背包容量V每种药材有采集时间对应物品重量siz[i]和价值对应物品价值val[i]每种药材只能采一次对应0-1背包目标是求最大可获得价值。是不是一下子就清晰了思路拆解分步走步骤1确定背包模型。物品药材容量采药总时间V目标最大价值选择次数每种1次妥妥的0-1背包直接套用模板。步骤2定义状态。这里我们分两种写法——二维DP易理解适合新手和一维滚动数组优化空间实战常用。二维DP的dp[i][j]代表“前i个物品容量最大为j时的最大价值”一维DP的dp[j]代表“容量为j时的最大价值”是二维DP的空间优化版。步骤3推导转移方程。核心逻辑还是“选或不选当前药材”如果不选dp[j]就等于之前的最大值dp[i-1][j]或dp[j]如果选就要留出当前药材的采集时间价值就是“剩余容量的最大价值当前药材价值”也就是max(dp[j], dp[j-siz[i]]val[i])。步骤4初始化逻辑。无论是二维还是一维dp[0]容量为0时都要初始化为0——因为容量为0什么都装不下价值就是0其他位置也初始化为0因为一开始没有选择任何药材价值都是0。步骤5确定遍历顺序。0-1背包的关键的是“物品正序、容量倒序”为什么要倒序因为倒序能避免同一个药材被多次选择比如正序遍历会导致dp[j-siz[i]]已经包含当前药材的选择相当于重复选了这一点一定要记牢代码实现下面给大家两种完整可运行的C代码二维DP和一维滚动数组优化版每一行都加了详细注释大家可以直接复制到编译器运行对照思路理解。#includebits/stdc.h using namespace std; int siz[105],val[105]; //dp[i][j]代表前i个物品容量最大为j时最大价值 int dp[105][1005]; int main(){ //V代表总体积采药总时间n代表物品个数药材种类 int V,n; cin V n; //输入每种药材的采集时间siz和价值val for(int i1;in;i){ cin siz[i] val[i]; } //遍历物品药材从1到n因为dp[0][j]是初始状态 for(int i1;in;i){ //遍历容量时间从1到V避免j-siz[i]0出现负数下标 for(int j1;jV;j){ //如果当前容量能装下第i个药材就选或不选取最大值 if(j siz[i]){ //不选第i物品dp[i-1][j] vs 选第i个物品dp[i-1][j-siz[i]] val[i] dp[i][j] max( dp[i-1][j], dp[i-1][ j-siz[i] ] val[i] ); }else{ //装不下只能不选价值和前i-1个物品一致 dp[i][j] dp[i-1][j]; } } } //输出前n个物品、容量为V时的最大价值 cout dp[n][V]; return 0; }滚动数组优化#includebits/stdc.h using namespace std; int siz[105],val[105]; //dp[j]代表容量为j时的最大价值滚动数组覆盖之前的状态 int dp[1005]; int main(){ //V代表总体积采药总时间n代表物品个数药材种类 int V,n; cin V n; //输入每种药材的采集时间和价值 for(int i1;in;i){ cin siz[i] val[i]; } //遍历物品药材 for(int i1;in;i){ //容量倒序遍历关键避免重复选择从V到1 for(int jV;j1;j--){ //能装下当前药材就更新最大价值 if(j siz[i]){ dp[j] max( dp[j], dp[ j-siz[i] ] val[i] ); }else{ //装不下价值不变可省略这里写出来是为了新手理解 dp[j] dp[j]; } } } //输出容量为V时的最大价值 cout dp[V]; return 0; }重点补充滚动数组优化的具体解释新手必看1. 优化的核心目的二维DPdp[i][j]的空间复杂度是O(n*V)n是物品数V是背包容量当n和V较大时比如n1e4、V1e5二维数组会占用大量内存1e9个int类型约4GB滚动数组可将空间复杂度优化到O(V)大幅节省内存避免内存溢出。2. 优化的核心原理观察二维DP的转移方程dp[i][j] max(dp[i-1][j], dp[i-1][j-siz[i]]val[i])发现计算dp[i][j]时只用到了上一层i-1层的dp值不需要保留所有i层的历史数据。因此我们可以用一个一维数组dp[j]不断“覆盖”上一层的数值实现“滚动更新”这也是“滚动数组”名字的由来。3. 具体实现细节结合代码① 初始化一维dp数组初始化为0和二维DP的dp[0][j]无物品时价值为0完全一致保证初始状态正确。② 遍历顺序必须“物品正序、容量倒序”这是滚动数组不出现错误的关键。倒序遍历容量是为了保证计算dp[j]时dp[j-siz[i]]还是上一层i-1层的数值没有被当前i层的数值覆盖——如果正序遍历dp[j-siz[i]]会先被更新包含当前i物品的选择就会导致同一个物品被多次选择违背0-1背包“每种物品仅选1次”的规则。③ 数值覆盖每遍历一个物品i从1到n就用当前物品的信息倒序更新dp[j]从V到siz[i]的所有数值每一次更新都是用“上一层的dp值”计算“当前层的dp值”并覆盖原有数值相当于把二维数组的i层“滚动”到了一维数组中。4. 优化前后对比二维DP的dp[i][j]能看到每一层前i个物品的所有容量对应的价值便于调试滚动数组的dp[j]只能看到当前最新的状态前i个物品但空间更节省实战中更常用。大家可以结合上面的两段代码打印dp数组的每一步变化就能直观看到滚动更新的过程。易错点提醒新手最容易踩这3个坑一定要避开① 容量遍历顺序搞反把倒序写成正序导致同一个药材被多次选择② 输入数据顺序搞混把采集时间和价值输反结果完全错误③ 忽略数组下标越界没判断j siz[i]导致j-siz[i]出现负数。拓展思考给大家留一个小问题锻炼一下思路——如果题干改为“求恰好装满时间t的最大价值”代码该如何调整其实很简单只要修改初始化逻辑把dp[0]设为0其他dp[j]设为负无穷表示无法装满这样就能保证最终结果是“恰好装满”的最大价值啦大家可以动手试试3.2 完全背包真题P1616 疯狂的采药拓展必刷讲完0-1背包咱们来看它的“兄弟”——完全背包真题P1616《疯狂的采药》其实就是P1048的小小变种核心差异只有一个抓住这个差异就能秒解题干解析对比P1048题干几乎一模一样核心差异只有一个——每种药材可以无限次采集只要时间够想采多少采多少这就是完全背包的典型特征。其他条件不变时间限制背包容量采集时间重量价值价值目标还是求最大价值。思路拆解聚焦差异步骤1对比P1048分析题干差异对解题的影响。因为药材可以无限次采集所以我们不需要再“避免重复选择”反而希望能重复选择同一药材——这就导致了遍历顺序的变化这也是完全背包和0-1背包唯一的核心差异。步骤2状态定义。和P1048完全一致还是用一维DPdp[j]代表“容量为j时的最大价值”不需要做任何修改——因为无论能不能重复选我们关注的都是“容量j对应的最大价值”。步骤3转移方程。也和P1048完全一致还是dp[j] max(dp[j], dp[j-siz[i]]val[i])。为什么不需要修改因为转移方程的核心是“选或不选”只是“选”的时候完全背包允许重复选而这一点通过遍历顺序就能实现。步骤4遍历顺序核心差异。完全背包的容量的是正序遍历从1到V而不是0-1背包的倒序。为什么正序遍历的时候dp[j-siz[i]]已经被更新过可能包含了当前药材的选择此时再用dp[j-siz[i]]val[i]就相当于“再次选择当前药材”刚好满足“无限次采集”的需求是不是很巧妙代码实现下面是完整可运行的C代码大家可以对比P1048的滚动数组版会发现只有一个地方修改了——就是容量的遍历顺序其他代码完全一致是不是瞬间觉得完全背包很简单#includebits/stdc.h using namespace std; int siz[10005],val[10005]; //dp[j]代表容量为j时的最大价值用long long避免数据溢出 long long dp[10000005]; int main(){ //V代表总体积采药总时间n代表物品个数药材种类 int V,n; cin V n; //输入每种药材的采集时间和价值 for(int i1;in;i){ cin siz[i] val[i]; } //遍历物品药材 for(int i1;in;i){ //核心差异容量正序遍历允许重复选择同一药材 for(int j1;jV;j){ if(j siz[i]){ //转移方程和0-1背包完全一致 dp[j] max( dp[j], dp[ j-siz[i] ] val[i] ); }else{ //装不下价值不变可省略 dp[j] dp[j]; } } } cout dp[V]; return 0; }这里有个小细节dp数组用了long long类型因为当V很大、价值很高时int类型可能会溢出新手容易忽略这一点大家要记好哦易错点提醒① 最容易混淆的就是遍历顺序把完全背包的正序写成倒序就变成0-1背包了结果肯定错误② 超时问题当数据量较大时比如V达到1e7一维DP的效率优势就体现出来了二维DP容易超时所以实战中建议优先用一维DP。拓展思考如果题干增加“每种药材最多采集k次”该怎么解其实很简单这就转化成了多重背包问题——把“最多采k次”看成“每种药材有k个”然后用多重背包的二进制拆分法优化下一道题我们就会讲大家可以先思考一下3.3 多重背包真题P1776 宝物筛选优化必刷如果说0-1背包和完全背包是“基础款”那多重背包就是“进阶款”——它介于两者之间每种物品有有限个选择次数而P1776《宝物筛选》就是多重背包优化的经典真题重点考查二进制拆分技巧学会它就能轻松应对所有多重背包题。题干解析提炼核心条件每种宝物有重量、价值还有数量限制k[i]个背包有最大容量求能装入的最大价值。这就是典型的多重背包问题。为什么需要优化因为如果直接把“k[i]个宝物”拆成k[i]个独立物品转化为0-1背包当k[i]很大时比如1e5物品数量会急剧增加导致代码超时所以必须用二进制拆分优化。思路拆解重点讲优化步骤1基础解法转化为0-1背包。核心思路就是“拆分物品”——把每种有k[i]个的宝物拆成k[i]个独立的宝物每个只能选1次然后套用0-1背包的思路求解。这种方法简单易懂但效率极低k[i]很大时会超时只能应对小数据。步骤2二进制拆分优化原理核心。为什么用二进制拆分因为任何一个整数k都可以拆成若干个2的幂次之和比如k5拆成122k7拆成124这样拆分后选这些“组合物品”的不同组合就能覆盖“选0-k个原物品”的所有情况。比如k5选1、2、2的组合就能实现选0-5个原物品0个都不选1个选12个选23个选124个选225个选122。这样一来物品数量就从k[i]缩减到log2(k[i])效率大幅提升。步骤3状态定义。拆分后就转化成了0-1背包问题所以状态定义和0-1背包一致用一维DPdp[j]代表“容量为j时的最大价值”。步骤4转移方程。和0-1背包完全一致还是dp[j] max(dp[j], dp[j-siz[i]]val[i])只是这里的“物品”是我们拆分后的“组合物品”遍历这些组合物品即可。步骤5遍历顺序。拆分后按0-1背包的逻辑采用“物品正序、容量倒序”遍历避免重复选择组合物品。代码实现下面是完整可运行的C代码重点注释了二进制拆分的逻辑大家可以对照思路看看拆分过程是如何实现的尤其是拆分后物品的重量和价值计算#includebits/stdc.h using namespace std; //val和siz存储拆分后组合物品的价值和重量 int val[1000005],siz[1000005]; //dp[j]代表容量为j时的最大价值 int dp[100005]; int main(){ // n物品数量宝物种类V背包容量。 int n,V; cin n V; int cnt 0; //cnt表示当前拆分后有多少个组合物品 for(int i1;in;i){ int a,b,c; //a原宝物价值b原宝物重量c原宝物数量 cin a b c; //二进制拆分核心逻辑拆成2的幂次 for(int j1;jc;j*2){ val[cnt] a * j; //组合物品的价值 原价值 * 拆分数量j siz[cnt] b * j; //组合物品的重量 原重量 * 拆分数量j c - j; //剩余数量继续拆分 } //剩下的物品数量没办法表示成另一个2的整数次幂单独作为一个组合物品 if(c){ val[cnt] a * c; siz[cnt] b * c; } } //拆分后按0-1背包逻辑求解 for(int i1;i cnt;i){ for(int j V;j siz[i];j--){ dp[j] max(dp[j],dp[j-siz[i]] val[i]); } } cout dp[V]; return 0; }易错点提醒这道题的易错点主要在二进制拆分上大家要注意3点① 拆分时的循环条件j*2不要写成j2② 拆分后组合物品的重量和价值要乘以拆分的数量j③ 剩余数量c的处理如果c0要单独作为一个组合物品否则会遗漏选择另外数组容量要足够大避免因拆分后物品数量过多导致数组越界、超时。拓展思考如果宝物数量极大比如1e5二进制拆分仍有压力该如何进一步优化这里给大家提一个进阶方向——单调队列优化它能把多重背包的时间复杂度降到O(nV)不过这个方法难度较高新手可以先掌握二进制拆分后续再深入学习毕竟面试中二进制拆分已经能应对大部分多重背包题了。四、三道真题对比总结找规律、避坑点刷完这三道真题大家有没有发现一个规律其实背包问题的核心就是“找对应关系套模板”只要掌握了三类背包的差异就能轻松应对各种真题。下面我们来总结一下帮大家梳理思路、避开坑点。核心差异对比给大家整理了一个简单的对比一目了然真题编号背包类型核心特征遍历顺序核心考点P10480-1背包每种物品选1次物品正序、容量倒序基础模板、空间优化P1616完全背包每种物品选无限次物品正序、容量正序遍历顺序差异P1776多重背包每种物品选有限次拆分后倒序遍历二进制拆分优化实战通用技巧如何快速将题干转化为背包模型核心就是找三个东西物品题干中可选择的对象如药材、宝物、容量题干中的限制条件如时间、重量、目标求最大价值、最少数量等找到这三个就能快速定位背包类型。遍历顺序的判断技巧记住一句话——“0-1倒序完全正序多重拆分后倒序”再也不用混淆了。代码调试技巧遇到错误时不要盲目修改代码建议打印DP数组观察每一步的变化比如打印dp[j]的每一次更新就能快速定位错误——比如重复选择大概率是遍历顺序错了结果偏小可能是初始化或转移方程漏了边界条件。高频坑点汇总把三道题的易错点整合一下大家一定要记好避免重复踩坑① 遍历顺序错误最易错尤其是0-1和完全背包的混淆② 数组初始化错误如完全背包忘记用long long多重背包拆分后数组容量不足③ 二进制拆分逻辑错误剩余数量未处理、拆分后价值/重量计算错误④ 数组下标越界未判断j 物品重量。五、进阶练习同类真题推荐巩固提升刷完这三道真题相信大家已经掌握了核心思路但想要真正熟练还需要多练同类题下面给大家推荐几道贴合难度的真题大家可以课后练习巩固所学技巧答案可以在评论区交流哦0-1背包同类题LeetCode 416. 分割等和子集简化版。推荐理由和P1048难度一致也是0-1背包的基础应用题干转化稍微有一点难度能锻炼大家“把题干转化为背包模型”的能力。完全背包同类题LeetCode 322. 零钱兑换基础版。推荐理由贴合P1616难度虽然目标是“最少硬币数”但核心思路和完全背包一致能帮大家灵活运用完全背包的遍历顺序举一反三。多重背包同类题洛谷P2347 砝码称重简化版。推荐理由贴合P1776难度重点考查二进制拆分技巧题干场景新颖能帮大家巩固多重背包的优化思路避免只会套用模板。六、尾声到这里这篇真题解析博客就接近尾声啦相信大家看完之后对0-1背包、完全背包、多重背包的实战用法已经有了清晰的认识。总结这三道真题P1048帮我们打牢0-1背包基础P1616让我们掌握完全背包的核心差异P1776教会我们多重背包的优化技巧三者结合刚好覆盖了背包问题的基础和核心考点。其实背包问题一点都不难关键在于“理解理论多刷真题”多敲代码、多踩坑、多调试就能慢慢找到感觉。留言互动欢迎大家在评论区分享自己的解题过程——比如“二进制拆分还是不懂”“代码超时了怎么办”“拓展思考的答案是什么”只要是你遇到的问题我都会一一解答也欢迎大家分享自己的解题思路互相交流、共同进步后续预告下一篇博客我们会讲解背包问题的混合变种比如有的物品选1次、有的选无限次及更复杂的真题帮大家进一步提升实战能力应对更难的面试场景记得关注哦最后祝大家都能熟练掌握背包真题在算法学习的路上越走越顺刷题不踩坑面试拿高分加油记得点赞哦如果觉得本文有帮助的话请点个关注再走叭