‍ 关于作者会编程的土豆“不是因为看见希望才坚持而是坚持了才看见希望。”你好我是会编程的土豆一名热爱后端技术的Java学习者。正在更新中的专栏《数据结构与算法》《leetcode hot 100》《数据库mysql》作者简介后端学习者背包问题是动态规划的经典入门题型也是面试和算法竞赛中的常客。但对于初学者来说最困惑的不是状态转移方程而是为什么01背包要倒序遍历为什么完全背包要正序遍历本文将用最通俗的语言和图解帮你彻底理解这两种背包的核心区别。读完这篇文章你将掌握01背包与完全背包的标准模板正序与倒序的本质原理P1048 采药 和 P1616 疯狂的采药 的 AC 代码什么是背包问题问题描述有一个容量为m的背包有n件物品每件物品有重量w[i]和价值v[i]。问如何选择物品装入背包使得总重量不超过容量且总价值最大现实场景旅行打包行李箱空间有限怎么装最值钱投资理财资金有限怎么投收益最高时间管理时间有限怎么安排收获最大二、01背包每个物品最多选一次经典例题P1048 [NOIP2005 普及组] 采药题目大意有M株草药每株有采摘时间time和价值value总时间T内每株最多采一次求最大总价值。#includeiostream #includevector #includealgorithm using namespace std; int main() { int T, M; cin T M; vectorintdp(T 1, 0); for (int i 0; i M; i) { int time, value; cin time value; for (int j T; j 0; j--) { if(jtime) dp[j] max(dp[j], dp[j - time] value); } } cout dp[T] endl; return 0; }状态定义dp[j]表示在时间不超过j的前提下能获得的最大价值。状态转移方程dp[j] max(dp[j], dp[j - time] value)dp[j]不采这株草药dp[j - time] value采这株草药花time时间得value价值核心代码for (int i 0; i M; i) { int time, value; cin time value; for (int j T; j time; j--) { // 倒序遍历 dp[j] max(dp[j], dp[j - time] value); } }为什么必须倒序正序会导致同一物品被多次使用。举例T 3物品time 1, value 10正序错误j 1: dp[1] max(0, dp[0]10) 10 j 2: dp[2] max(0, dp[1]10) 20 ← 用了刚更新的 dp[1] j 3: dp[3] max(0, dp[2]10) 30 ← 又用了刚更新的 dp[2]一个物品被用了3次倒序正确j 3: dp[3] max(0, dp[2]10) 10 ← dp[2] 还是旧值 0 j 2: dp[2] max(0, dp[1]10) 10 ← dp[1] 还是旧值 0 j 1: dp[1] max(0, dp[0]10) 10每个物品只用了1次。一句话理解倒序用旧值生新值各容量状态相互隔离保证物品只用一次。三、完全背包每个物品可选无限次经典例题P1616 疯狂的采药题目大意与采药相同但每种草药可以无限次采摘。#include iostream #include vector #include algorithm using namespace std; int main() { int T, M; cin T M; vectorlong long dp(T 1, 0); // 注意可能很大用 long long for (int i 0; i M; i) { int time, value; cin time value; // 完全背包正序遍历 for (int j time; j T; j) { dp[j] max(dp[j], dp[j - time] value); } } cout dp[T] endl; return 0; }核心代码for (int i 0; i M; i) { int time, value; cin time value; for (int j time; j T; j) { // 正序遍历 dp[j] max(dp[j], dp[j - time] value); } }为什么正序就能无限用正序让新值立刻变成基础值供后续使用形成链式叠加。举例T 3物品time 1, value 10正序正确j 1: dp[1] max(0, dp[0]10) 10 j 2: dp[2] max(0, dp[1]10) 20 ← 用了刚更新的 dp[1]叠加一次 j 3: dp[3] max(0, dp[2]10) 30 ← 用了刚更新的 dp[2]再叠加一次物品被用了3次正是完全背包想要的效果一句话理解正序让新值生新值形成滚雪球效应允许物品无限次使用。四、对比总结表背包类型限制遍历顺序核心原理口诀01背包每件最多1次倒序j T; j time; j--旧值生新值相互隔离01 倒着走完全背包每件无限次正序j time; j T; j新值生新值链式叠加完全正着来五、变种不选也有价值P1802 5倍经验日有些题目中不选这个决策也会产生价值。例如 P1802打不过好友也能获得失败经验。状态转移for (int j x; j 0; j--) { long long no_use dp[j] lose; // 不打得失败经验 long long use (j num) ? dp[j - num] win : -1; // 打得胜利经验 dp[j] max(no_use, use); }本质仍是 01 背包只是不选的价值从 0 变成了lose。六、常见问题 FAQQ1为什么循环可以从time开始而不是0因为当j time时物品装不下dp[j]不会改变所以可以跳过。两种写法等价// 写法1简洁 for (int j T; j time; j--) // 写法2直观 for (int j T; j 0; j--) { if (j time) dp[j] max(dp[j], dp[j - time] value); }Q2j - time会不会越界不会。因为循环条件是j time保证了j - time 0。Q3dp数组为什么要用long long当数据范围较大时最大价值可能超过int上限约 21 亿用long long更安全。八、结语背包问题的核心不在于背模板而在于理解正序与倒序背后的原理倒序 旧值生新值 01背包正序 新值生新值 完全背包理解了这一点所有背包变种都能举一反三。希望这篇文章能帮你彻底搞懂背包问题。如果有任何疑问欢迎在评论区交流