背包问题在动态规划里的地位大概相当于Hello World在编程入门里的地位——几乎所有讲DP的教程都拿它开刀但真正能把01背包和完全背包讲透、讲到你合上电脑还能自己推出来的其实没几个。我前后带过不少刚接触算法的朋友发现大家卡住的地方高度一致不是不会写那几行代码而是脑子里没有建立起状态怎么定义、转移为什么长这样、循环方向凭什么这么写的清晰图像。这篇就把01背包和完全背包从建模、推导、空间优化到边界处理,一层层拆开讲代码用Python写力求让你看完能自己默写、自己调对。适合刚学DP的新手也适合学过但总在细节上翻车的老手。1. 背包问题不是装箱游戏它凭什么成为动态规划的入门样板很多人第一次看到背包问题第一反应是这不就是个装东西的排列组合吗暴力枚举不就行了这个想法本身没错但很快就撞墙。假设有30件物品每件选或不选那就是2的30次方大约10亿种组合。要是40件、50件呢指数级增长会瞬间让暴力法失去意义。背包问题的价值恰恰在这里——它用一个巧妙的状态设计把指数级的枚举压缩成了多项式时间的递推。1.1 问题原型到底在问什么先把最朴素的版本说清楚。你有一个背包容量是C。面前摆着n件物品第i件物品重量是w[i]价值是v[i]。每件物品你只有两种选择要么整个拿走要么完全不拿不能拆开拿一半。问在不超过背包容量的前提下能装走的最大总价值是多少这里的01两个字就是关键——每件物品的状态只有0不拿和1拿两种这才叫01背包。注意这个约束后面完全背包就是把每件只能拿一次改成每件可以拿无限次差别全在这。理解问题之后你要形成第一个直觉这是一个在约束下求最优的问题而动态规划处理这类问题的通用套路就是把大问题拆成一串小问题每个小问题只关心到目前为止我做到哪了。1.2 为什么暴力枚举会崩DP又是怎么接住的我试着用生活的例子讲。假设你逛超市预算100块货架上有20样东西你想买得最值。如果你一根筋地枚举所有组合就是2的20次方约100万种人脑和电脑都扛不住。但如果你换个思路一件一件地看每看一件就问自己在剩下这么多预算的情况下加上这件东西划不划算并且把每一件物品、每一个预算档位的答案都记下来——这就是DP。DP能成立的前提是最优子结构一个大问题的最优解可以由小问题的最优解拼出来。背包恰好满足当你在考虑前i件物品、容量j的最优值时你只需要知道前i-1件物品在某个容量下的最优值再加一次比较就能得出。这种用小答案推大答案的结构就是背包能进DP殿堂的根本原因。1.3 状态设计是整件事的灵魂新手最常犯的错是把精力全放在背代码上忽略了状态定义。我反复跟人强调写背包之前先在纸上把一句话写下来——dp代表什么。以01背包为例我们定义dp[i][j]表示只考虑前i件物品在容量为j的背包里能装到的最大价值。这句话每个字都有用。前i件限定了物品范围容量为j限定了约束最大价值是你要优化的目标。把这句话想清楚转移方程几乎是顺着念出来的面对第i件物品我要么不拿它那答案就是前i-1件、容量j的结果要么拿它那得先给它腾出w[i]的空间答案就是前i-1件、容量j-w[i]再加v[i]。二者取大完事。记住状态定义决定了你能不能写出正确的转移后面的空间优化、边界处理全都建立在这一步之上。定义错了代码再漂亮也是错的。2. 01背包把选或不选逐字翻译成状态转移方程第一节我们把状态定义立住了这一节就正式动手写01背包从二维数组版本开始。为什么先写二维因为二维版本最贴近人的思维方式它把前i件物品这个维度明明白白摆在你眼前你写起来不容易错。先把它写对、写顺再去谈优化这是我一贯的顺序。2.1 二维DP的完整推导过程先说清楚变量。dp是一个 (n1) 行 (C1) 列的二维表第i行第j列就是dp[i][j]。多留出来的第0行和第0列是给空集和零容量用的边界值统一取0因为一件东西都没考虑或者容量为0能装的价值自然是0。核心转移方程我写出来只有两行# 不选第 i 件物品 dp[i][j] dp[i-1][j] # 选第 i 件物品前提是 j w[i] if j w[i]: dp[i][j] max(dp[i][j], dp[i-1][j-w[i]] v[i])我用一个具体例子走一遍你跟着感受一下。设C5有两件物品物品1重量2、价值3物品2重量3、价值4。我来填表。i1时物品1重量2价值3。j从0到5j小于2的时候装不下dp0j2时dp[1][2]max(dp[0][2], dp[0][0]3)3j3、4、5同样都是3。i2时物品2重量3价值4。j小于3装不下沿用上一行。j3时dp[2][3]max(dp[1][3], dp[1][0]4)max(3,4)4j4时dp[2][4]max(dp[1][4], dp[1][1]4)max(3,4)4j5时dp[2][5]max(dp[1][5], dp[1][2]4)max(3,34)7。最终答案7拿两件都装。这个手推过程特别重要因为它让你真的看到腾空间再加价值是怎么运作的。很多人写不出转移是因为从没手推过一遍。2.2 遍历顺序里藏着的两个细节代码骨架长这样n, C len(w), capacity dp [[0] * (C 1) for _ in range(n 1)] for i in range(1, n 1): for j in range(0, C 1): dp[i][j] dp[i-1][j] if j w[i-1]: dp[i][j] max(dp[i][j], dp[i-1][j-w[i-1]] v[i-1]) print(dp[n][C])有两个地方新手特别容易翻车。第一物品下标。如果你用w[i]当第i件物品的重量那么循环里的i从1开始但Python列表下标从0开始所以真实访问要写成w[i-1]。我见过太多人栽在这里报IndexError或者算错结果排查半天。我的建议是要么在w和v前面各补一个占位元素让下标对齐要么全程用w[i-1]并且提醒自己。第二j的遍历顺序。二维版本里j从0到C还是从C到0都无所谓因为dp[i][j]只依赖上一行dp[i-1][...]的数据跟本行没关系。这一点请牢牢记住——它是理解一维优化为什么必须倒序的基础。2.3 复杂度与它的现实意义二维版本的时间复杂度是 O(nC)空间复杂度也是 O(nC)。时间上这个已经是多项式级别对于n和C都不大的场景完全够用。但空间上如果容量C是几千、物品n是几百那表格就是几十万到上百万个格子内存吃紧。提示在面试或竞赛里如果题目只要求你算出最终答案而不需要还原具体选了哪几件那二维表就是浪费的——因为每一行只依赖上一行。这直接引出下一节的空间压缩。但这里要说一句公道话如果题目需要你还原选了哪些物品二维表反而是方便的因为你可以从dp[n][C]往回倒推。所以别一上来就否定二维写法它是很多回溯类题目的基础。把二维写熟再学一维才是稳的顺序。3. 二维压成一维滚动数组背后那笔空间账空间优化是背包问题里最能体现理解程度的一步。很多人会背01背包一维要倒序但你要问他为什么倒序他就卡壳了。这一节我把这笔账算给你看算明白了你以后不光不会写反还能解释给面试官听。3.1 逐行覆盖从两张表到一张表观察二维转移dp[i][j]只用到dp[i-1][j]和dp[i-1][j-w[i]]全都来自上一行。也就是说算第i行的时候第i-2行及更早的数据统统没用了可以直接扔掉。那能不能只用一行dp[j]让它在处理每件物品时被原地更新可以但要小心如果你按 j 从小到大更新那么当你算dp[j]时用到的dp[j-w[i]]可能已经在本轮当前这件物品被更新过了而它本该是上一轮的旧值。用旧值才能保证每件物品只用一次用新值就等于这件物品被重复添加了——这正是完全背包的行为。所以01背包一维写法的铁律是内层循环 j 必须从 C 倒序遍历到 w[i]。倒着走你更新dp[j]时更小的dp[j-w[i]]还没被本轮碰过它保留的是上一轮的旧值语义正确。3.2 一维写法的标准模板n, C len(w), capacity dp [0] * (C 1) for i in range(n): for j in range(C, w[i] - 1, -1): dp[j] max(dp[j], dp[j - w[i]] v[i]) print(dp[C])range(C, w[i]-1, -1)的意思是从C开始一路递减直到w[i]因为终点写w[i]-1是开区间实际取到w[i]。j小于w[i]的位置装不下这件物品保持原样即可。我把这段代码和二维版本对着看dp[j] max(dp[j], dp[j-w[i]]v[i])里的第一个dp[j]对应二维的dp[i-1][j]不选第二个dp[j-w[i]]v[i]对应dp[i-1][j-w[i]]v[i]选。因为倒序保证了右边的dp[j-w[i]]还是旧值所以这个对应关系成立。3.3 为什么这个倒序值得单独强调我见过不止一个人代码写得一字不差就是把range(C, w[i]-1, -1)手滑写成了range(w[i], C1)正序然后程序不报错结果却偏大。为什么偏大因为正序时同一件物品被算了很多次等价于完全背包而完全背包的解一般大于等于01背包所以看起来数字大了一点不易察觉。这类bug最阴险的地方在于小数据有时候碰巧也对大数据才暴露。我的经验是写完之后拿一个极简用例手工验一下比如只有一件物品、容量正好等于它的重量答案应该等于它的价值。如果这个用例都错那一定是循环方向或者下标出了问题。注意把二维转一维前提是题目不需要还原选中物品。如果题目要求输出具体方案老老实实用二维表回推别为了省那点空间把自己绕进去。到这里01背包的从二维到一维的完整链路就走通了。真正的考验在下一节——完全背包看起来只是把循环方向反过来但背后的状态语义变化值得单独拎出来讲透。4. 完全背包内层循环反过来写凭什么就能重复拿了完全背包的改动极其小每件物品可以拿无限次。就这么一句话导致内层循环方向从倒序变正序一维写法其他一字不改。很多人靠死记01倒序、完全正序糊弄过去但真遇到变形题立刻就懵。这一节我要把正序为什么等价于重复拿这件事讲清楚。4.1 完全背包的问题描述与二维方程问题n种物品每种有无限多个重量w[i]、价值v[i]容量C求最大价值。二维状态依然设dp[i][j]为前i种物品、容量j的最大价值。转移的时候多了个选择拿0个、拿1个、拿2个……但仔细想想如果你拿了1个第i种物品之后还可以继续拿那拿了1个之后的剩余问题其实和原问题结构一样——只不过物品集合没变。更优雅的写法不去枚举拿几个而是直接利用可以重复这一点把转移写成dp[i][j] max(dp[i-1][j], dp[i][j-w[i]] v[i]) # 若 j w[i]注意第二个式子是dp[i][j-w[i]]而不是dp[i-1][j-w[i]]差异就在于这里用的是本行的数据。含义是当前容量j我拿了一个物品i之后剩下的容量j-w[i]还允许继续拿物品i因为本行的状态里物品i还是可用的。这一字之差就是完全背包和01背包的根本区别。4.2 正序遍历为什么正好表达可以重复现在把它压成一维。一维转移仍然是dp[j] max(dp[j], dp[j-w[i]]v[i])但内层循环改成从w[i]到C正序。正序时你算dp[j]用到的dp[j-w[i]]已经是本轮更新过的新值了。这个新值意味着什么它代表已经拿过若干次物品i的状态。所以用新值来更新相当于允许你再拿一次物品i——重复就自然发生了。我拿一个数字例子验证。容量C5只有一种物品重量2、价值3。正序走dp[2]3拿1个dp[4]max(0, dp[2]3)6拿2个dp[5]不变还是6容量5塞不下第3个还剩1。结果6等于拿2个正确。如果换成倒序01行为只能拿1个结果是3。这个小例子特别适合拿来验证你到底理解没有。4.3 二维与一维的对照记忆法为了让你不记混我总结一个对照表维度01背包完全背包二维转移选dp[i-1][j-w] vdp[i][j-w] v一维内层方向倒序 C → w正序 w → C本质含义上一行旧值不可重复本行新值允许重复看这张表的第三行一切就清楚了。01背包要的是上一轮的数据所以要用还没被本轮污染的旧值必须倒序完全背包要的是本轮已含重复的数据所以要用被本轮更新过的新值必须正序。方向不是规则是结果。提示判断一道题该用哪种别只看能不能重复这几个字要回到我更新dp[j]时想引用的是哪一轮的状态这个问题上去。想清楚这个方向自然就定了。完全背包的变体题比如每种物品拿有限个的多重背包都可以从这两条基础出发去变形。掌握引用哪一轮状态这个判据你就能举一反三。5. 初始化与边界三个坑让程序看起来对但结果是错的把两套模板背下来只是入门真正决定你能不能通过一道题的是初始化和边界条件。我见过太多人模板写得滚瓜烂熟一上题就WA最后发现栽在初始值上。这一节把几个高频坑一次性说透。5.1 恰好装满和最多能装是两类问题题目如果不做特殊要求通常问的是最大价值容量可以有剩余也就是最多能装。但如果题目明确说恰好装满容量C那就完全不同了。最多能装dp数组全部初始化为0。因为容量j没装满也是合法状态价值为0。恰好装满dp[0]0其余所有位置初始化为负无穷-inf。理由是只有容量0是天然恰好装满的合法状态其他容量在没有任何物品时是无法恰好装满的属于非法状态用负无穷标记防止它被误当作有效解传递下去。最后判断答案时如果dp[C]还是负无穷说明无法恰好装满题目要求的输出可能就得是特定值否则dp[C]就是答案。5.2 为什么用负无穷而不是0很多人问为什么不干脆用0因为0会被当成这个状态合法且价值为0于是不合法的状态会被误认为可行进而污染后续的转移让程序输出一个虚假的解。用负无穷就是明确告诉转移过程这条路径走不通。我举个具体场景。假设容量5只有一件重量3的物品问恰好装满的最大价值。dp[0]0dp[3]可以由dp[0]推出是合法但dp[5]需要从dp[2]来dp[2]是负无穷所以dp[5]也传不下去最终dp[5]负无穷正确表示装不满。如果dp[2]初始化成0dp[5]就会错误地算出一个值。这个例子我建议你亲手跑一遍。5.3 下标越界与物品编号的隐形杀手除了初始化边界里第二大类就是下标问题前面提过但我再强调一次因为它真的太常见。如果你在w、v前面补了占位常见做法循环是for i in range(1, n1)那么用w[i]没问题。如果你没补循环是for i in range(n)那么用w[i]必须写成w[i]不能再减1。两套写法不要混用混用必错。我自己的习惯是统一用for i in range(n)然后用w[i]、v[i]简洁且不容易乱。省得那个多补一个0的占位让人算错总长度。选一种坚持到底。# 我自己常用的写法不补占位 dp [0] * (C 1) for i in range(n): for j in range(C, w[i] - 1, -1): # 01背包 dp[j] max(dp[j], dp[j - w[i]] v[i])注意负数重量、重量为0的物品完全背包里可能无限拿导致价值爆炸都是隐蔽的坑遇到这类输入一定要先处理别硬套模板。初始化和边界看起来是小事但它们决定了你的解是不是数学上正确。把这两类问题分清你的正确率会立刻上一个台阶。6. 背包的家族方案数、多重背包和二进制拆分只会写01和完全两个模板遇到稍微变形的题还是会卡。背包其实是个大家族很多高频题都是它的亲戚。这一节我把几个最常考的变体讲一下重点讲它们和基础模板的联系而不是另起炉灶。6.1 求方案数把 max 换成加法有一类题不问最大价值而问有多少种方法能凑出容量C或者有多少种子集和为C。这类题的状态定义换成dp[j]表示凑出容量j的方案数。转移里那个求最大值的max直接换成加法累加dp [0] * (C 1) dp[0] 1 # 凑出容量0有一种方案什么都不选 for i in range(n): for j in range(C, w[i] - 1, -1): # 01背包倒序 dp[j] dp[j - w[i]]注意关键点初始化dp[0]1因为什么都不选是一种合法方案是计数的起点。循环方向依然遵循01背包倒序、完全背包正序的规则。这套求方案数的写法在组合类题目里出现频率极高值得单独练熟。6.2 多重背包每个物品有有限个多重背包介于01和完全之间每种物品有个数量上限。最直接的想法是把第i种物品当成「把它拆成好几个独立的相同物品」然后按01背包处理。但这样当数量很大时代价很高。更好的办法是二进制拆分。假设某种物品有k个我们不去一个一个拆而是拆成 1、2、4、8…… 这样的块每块打包成一个新物品重量和价值都按块大小成倍放大。用这些块做01背包可以组合出 0 到 k 之间的任意数量。这样就把它转化成了01背包问题。举个例子某物品有7个拆成1、2、4三块1247用这三块能组合出1到7的所有数量若有10个拆成1、2、4、3124310最后一块是余数同样能覆盖0到10。二进制拆分的核心作用就是把 O(k) 的复杂度压到 O(log k)这在数据量大的时候是质的区别。6.3 分组背包与每组最多选一个还有一种常见变形叫分组背包物品被分成若干组每组里最多只能选一个。思路是按组来遍历外层组内每件物品作为一次01背包决策并且要求组内互斥同一组只会被选中一件。处理这类题时一个稳妥的做法是在每组内先复制一份上一轮的dp作为参照再在组内枚举物品做转移从而避免同组物品被叠加选中。这个技巧在很多模拟题里都会用到属于进阶但很实用。把这些变体串起来看你会发现它们都没离开那个核心定义清楚dp代表什么想清楚转移时该引用哪一轮的状态再决定循环方向。背包家族五花八门但骨架是同一副骨架。7. 我踩过的那些坑从能过样例到真正吃透背包写到这里基础知识都齐了。我想单独用一节聊聊实战里的真实感受因为很多细节只有你自己反复写过、错过、改过之后才会内化成直觉。这些内容网上教程很少提但恰恰是区分背模板和真理解的分水岭。7.1 样例能过不代表逻辑对我最开始学背包那会儿最大的错觉就是样例过了就等于对了。后来才明白背包的经典样例往往很小小到各种错误写法都可能碰巧通过。比如循环方向写反在小容量小物品数下可能不出问题一旦数据放大就偏。所以我后来养成了一个习惯每写完一个背包必定自己构造三组小数据手工推演尤其是只有一个物品恰好装满容量正好等于重量这三种极端情况。7.2 手推二维表是绕不过去的基本功我认识一些朋友一直跳过二维直接背一维短期能做题但只要题目要求还原方案、或者稍作变形就彻底不会了。原因是他们没有在脑子里建立起那张表只有一行代码。我的强烈建议是初学阶段老老实实把二维表手推三到五道题用纸笔把每一格都填出来感受腾空间再加价值的过程。当你手推过之后一维的倒序、完全的正序你会觉得理所当然根本不需要背。7.3 把抽象问题翻译成背包模型才是真的难模板写熟之后真正拉开差距的其实是识别能力——给你一道绕了弯的题你能不能看出它本质是个背包这类题往往把重量换成花费、价值换成收益、容量换成预算或时间字面上完全看不到背包的影子。我的经验是抓两个信号一是题目里有一个不能超过的限制对应容量二是每个选择项有选或不选或选几个的决策对应物品。两个信号同时出现基本可以往背包方向靠。比如用有限的预算买若干课程收益各不相同每门课最多选一次——这就是01背包每门课可以反复学很多遍每遍收益一样——这就是完全背包每门课有若干期、每期都能选——这就是多重背包。识别出模型剩下的就是套模板难题立刻降级。7.4 一些能救你于水火的实用小贴士最后分享几个我平时用得最多的技巧。写之前先写注释一行字把dp的含义标清楚比如# dp[j]: 容量j下的最大价值。这能帮你在调试时快速定位语义错误。涉及价值的题基本都用最大化和负数初始化涉及方案数的题都用加法和dp[0]1。两套语境不要混。一旦结果偏大优先怀疑循环方向该倒序写成了正序一旦结果偏小或异常优先怀疑初始化该负无穷写成了0。Python里如果数据量大二维表尽量改一维省内存也能提速。背包问题说到底考的不是你记了多少行代码而是你有没有建立起状态—转移—方向—边界这套完整的思考链条。01背包和完全背包这两块基石打牢了后面无论遇到什么变形你都有一条清晰的推导路径可以走。我自己到现在遇到没见过的背包变形题也还是用这套先定义状态、再想引用哪一轮、再定循环方向的流程去推屡试不爽。你把这两道基本功练到能闭眼写对、能讲清楚每一行的来龙去脉就已经超过绝大多数初学的人了。