前两天我在一个算法交流群里看到有人问背包问题到底是在考什么底下一堆人回复“背模板就行”还有人说“二维dp先写出来再改成一维”。看着这些回答我心里挺不是滋味的。背包问题尤其是01背包在国内外面试、笔试和竞赛里出现频率极高但它真正难的从来不是背模板而是想明白状态是怎么递推过来的。作为“背包问题”系列的第一篇这篇文章我把01背包这个最经典的模型拆到底从状态设计、转移方程、一维优化到路径回溯全部过一遍最后再给多重背包问题留好接口。如果你准备校招笔试、算法竞赛入门或者遇到预算分配、资源调度这类业务场景这篇文章值得你花半小时照着推一遍。1. 这个背包问题到底在做什么1.1 先看三个最像的生活场景别一上来就想“背包”两个字先想三个更具体的画面。第一个场景你走进超市手里购物车限重10公斤面前摆着四件商品每件商品有重量、有价值你希望“装进去的总价值最大”。第二个场景项目排期团队每天投入的工时有限每个需求要消耗不同工时、带来不同收益你希望用有限的工时拿到最大收益。第三个场景家里装修预算固定每样家具都有价格和“幸福感”你希望在全屋预算内让幸福感最高。这三个场景如果把“重量/价格/工时”统一叫成本把“价值/收益/幸福感”统一叫收益本质上就是同一个问题资源总量有限每件物品都占资源、都有收益怎么选让总收益最大。而“背包问题”只是这个大类问题的一个数学化名字。在正式定义里01背包是其中最简单的形态每件物品要么选、要么不选不能选一半也不能选多次。这个名字里的“01”指的就是这个二选一的状态0表示不选1表示选。1.2 为什么01背包是动态规划的完美入门很多人第一次学动态规划就被“状态、转移、重叠子问题”这些词吓退其实01背包是把这些概念浓缩得最清晰的模型。动态规划要成立首先要有最优子结构也就是大问题的最优解能由子问题的最优解拼出来。带上了01背包你面对前 i 件物品、容量为 j 的背包时最优解只有两条路不拿第 i 件或者拿第 i 件之后去看前 i-1 件物品在更小容量下的最优解。这两种情况都不会“回溯影响”之前的决策所以子问题的结果可以被反复使用这就是重叠子问题。另外01背包里有一个非常干净的状态维度物品序号和当前容量。你每处理一件物品就是在某个容量区间上做一轮更新。这种“按物品顺序逐层推进”的过程把动态规划里最难感知的递推节奏完全暴露出来了。说实话我见过很多同学背了一堆动态规划的题最后对“为什么这题能dp”说不出个所以然。而从01背包入手你会很快建立一种直觉看到资源上限和一堆选项先考虑状态里要不要预留“已处理数量”和“剩余容量”两个维度。1.3 一句话把问题约束清楚用标准的数学语言说一遍已知 n 件物品第 i 件物品的重量为 w[i]、价值为 v[i]背包总容量为 C每个物品最多选一次求能装下的最大价值。这里有两个“坑”需要先排掉否则后面写代码很容易踩。第一个坑是下标习惯。有的题里物品编号从 1 开始有的从 0 开始。你写代码时一旦混用就会在 dp[i][j-w[i-1]] 这类表达式上反复出bug。我自己的习惯是做题推导时用 1 到 n数据存储时用 0 到 n-1代码里统一写成 w[i-1]、v[i-1]。第二个坑是“保证不超过容量”的边界。很多新手第一次写转移方程时会写 dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]]v[i])但这句话默认了 j w[i]。写代码时必须先判断容量够不够否则下标会出现负数一维数组更是会报错。2. 状态设计与转移方程跟着推导一遍就理解2.1 二维dp数组为什么长这样要处理的对象是前 i 件物品约束条件是容量不超过 j。所以最直接的状态就是二维数组 dp[i][j]它表示“从编号 1 到 i 中挑物品总重量不超过 j 时能获得的最大价值”。数组的第一维为什么是物品数量而不是物品编号的组合因为遍历物品时我们从第 1 件开始一件一件把决策做进去i 天然代表了“决策到了第几件”。第二维为什么是容量因为容量决定了当前可选范围而且它是一个整数非常适合数组下标。我见过不少人不理解为什么 dp 要初始化为 0。这是因为任何物品都不选时价值当然是 0。如果题目要求“恰好装满”那就得把 dp[0][0] 设置成 0其他 dp[0][j] 设置成一个很小的负数用来表达“凑不到这个容量是无意义状态”。这两种初始化对应不同语义是面试里常考的细节。用生活场景类比一下dp[i][j] 就像你在超市里手里推车已经决定好要处理前 i 件商品但购物车容量只留了 j 公斤。你站在第 i 件商品面前思考“要不要拿”。你不拿结论就是 dp[i-1][j]你拿了剩下容量变成 j-w[i]结论就是前 i-1 件物品在 j-w[i] 容量下的最优价值再加上 v[i]。2.2 方程的两个分支到底在说什么转移方程写出来其实就一行dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i])当 j w[i] 时成立否则 dp[i][j] dp[i-1][j]。第一项 dp[i-1][j] 表示不选第 i 件物品。此时问题退化成了“只在前 i-1 件物品里挑容量限制仍然是 j”。这个值跟第 i 件物品无关所以直接继承。第二项 dp[i-1][j-w[i]] v[i] 表示选第 i 件物品。选之前你并不知道前面的物品怎么挑但既然第 i 件已经占了 w[i] 的容量留给前面物品的容量就是 j-w[i]。这种情况下最优结果来自前 i-1 件物品在 j-w[i] 容量下的最优解加上第 i 件物品的价值 v[i]。有个细节值得反复品为什么“选第 i 件”对应的子问题容量是 j-w[i]而不是 j 减去已经选中的物品总重量因为我们在 dp 递推过程中并不会提前记下你已经选了哪些物品只记“在某个容量下的最大价值”。这就是最优子结构的体现前人怎么选我们不需要知道具体方案只需要知道它在那个容量下给出的最好价值。很多教材会把“不选”和“选”看成两个分支其实更准确的看法是每次处理第 i 件物品时你都在做一次“合并决策”。如果选了能更大就更新成更大值如果选了反而更小那就让旧值继续保留。这个“保留旧值”的动作很多人写一维优化时很容易漏掉。2.3 复杂度会告诉你数据范围怎么出题01背包的时间复杂度是 O(n×C)空间复杂度在二维实现下是 O(n×C)。这里的 C 是背包容量容量多大数组就开多大。这也就决定了题目卡数据的套路一般 n 在几百到几千之间容量 C 在几万以下时O(n×C) 还能接受如果 C 上到了 10 的 6 次方甚至更大直接开二维数组就会内存爆炸必须想别的办法。面试里如果你只在 dp 上硬开数组有时候连编译器都会直接崩原因就是内存占用太大。举个例子n200C100000二维 int 数组需要约 200×100001 个 int也就是约 2亿 个 int在 C 里接近 800MB直接超出内存限制。所以优化到一维把空间变成 O(C)往往是必须的。这也是为什么我们接下来要重点解决“怎么把二维压成一维同时保持逻辑正确”。3. 手写一遍01背包代码、推导、回溯一条龙3.1 最保险的二维版本边写边讲先用 Python 写一个最容易理解的二维版本适合笔试时快速验证思路def knapsack_01(n, capacity, w, v): # dp[i][j]: 前i件物品容量不超过j的最大价值 dp [[0] * (capacity 1) for _ in range(n 1)] for i in range(1, n 1): for j in range(0, capacity 1): # 不选第i件 dp[i][j] dp[i - 1][j] # 选第i件前提是当前容量放得下 if j w[i - 1]: dp[i][j] max(dp[i][j], dp[i - 1][j - w[i - 1]] v[i - 1]) return dp[n][capacity]代码里的两个循环顺序值得注意外层按物品遍历内层按容量从小到大遍历。内层为什么从小到大在二维版本里可以随便来因为当前行的 dp[i][j] 只依赖上一行 dp[i-1][...]不会依赖同一行里刚更新过的值。所以只要保证外层物品顺序正确内层正序倒序都不影响二维版本的结果。这个版本时间上已经是 O(n×capacity)在 n 和 capacity 都不大的笔试环境下通常是够用的。唯一的问题是空间n 件物品要开 n 行数组很多场景浪费非常严重。这时候就需要把它优化成一维。3.2 一维空间优化与逆序遍历的底层逻辑观察二维版本的转移方程dp[i][j] 只用了 dp[i-1][j] 和 dp[i-1][j-w[i]]。这个规律意味着等号右边的所有值都来自上一行和当前行、当前物品有没有被重复使用没有关系。于是我们可以用一维 dp[j] 滚动复用“上一行”的数据更新时直接覆盖。一维版本长这样def knapsack_01_1d(n, capacity, w, v): dp [0] * (capacity 1) for i in range(n): # 关键容量必须从大到小遍历 for j in range(capacity, w[i] - 1, -1): dp[j] max(dp[j], dp[j - w[i]] v[i]) return dp[capacity]为什么必须从大到小遍历容量这是我在教学中反复强调的一个点。假设内层循环正序从0遍历到capacity那么在更新 dp[j] 时dp[j-w[i]] 可能已经被当前物品更新过了。也就是说同一个物品可能在一次外层循环里被“用两次”。这恰好是完全背包的行为逻辑而不是01背包。01背包要求每件物品最多用一次所以我们要保证计算 dp[j] 时用到的 dp[j-w[i]] 还是上一轮物品处理后的旧值也就是还没被当前物品更新。倒序遍历容量保证 j-w[i] 小于 j而且这个更小值还没有在当前轮被覆盖正好满足条件。用购物车类比就是你一次只能对“是否拿这个商品”做决定不能站在同一个商品面前反复把它放进购物车好几次。为了保证这一点你从购物车满容量开始向后倒着检查这样检查小容量时小容量的结果还没被这次“拿”的动作污染。3.3 用一组数据把优化过程推演干净光看代码还不过瘾我们拿一组具体数据手动推一遍。假设容量 C10四件物品物品编号重量w价值v1262593384815初始化 dp 全为0第一件物品w2, v6处理完后从容量10到2的位置都被更新成6dp [0, 0, 6, 6, 6, 6, 6, 6, 6, 6, 6]第二件物品w5, v9逆序从10降到5更新j10max(dp[10]6, dp[5]96915) 15j9max(dp[9]6, dp[4]915) 15j8max(dp[8]6, dp[3]915) 15j7max(dp[7]6, dp[2]915) 15j6max(dp[6]6, dp[1]99) 9j5max(dp[5]6, dp[0]99) 9所以第二轮后 dp [0, 0, 6, 6, 9, 9, 15, 15, 15, 15, 15]。第三件物品w3, v8继续逆序更新j10max(dp[10]15, dp[7]815823) 23j9max(dp[9]15, dp[6]89817) 17j8max(dp[8]15, dp[5]89817) 17j7max(dp[7]15, dp[4]86814) 15j6max(dp[6]9, dp[3]86814) 14j5max(dp[5]9, dp[2]86814) 14j4max(dp[4]6, dp[1]88) 8j3max(dp[3]6, dp[0]88) 8第三轮后 dp [0, 0, 6, 8, 8, 14, 14, 15, 17, 17, 23]。第四件物品w8, v15从容量10到8更新j10max(dp[10]23, dp[2]1561521) 23j9max(dp[9]17, dp[1]1515) 17j8max(dp[8]17, dp[0]1515) 17最终 dp[10] 23最优方案是选物品1、2、3总重量 25310总价值 69823。物品4虽然单件价值高但太重导致组合不如前三个物品划算。如果你第一次接触这个推导过程建议你亲手在纸上画一轮循环把“旧值”和“新值”分别标出来。很多看起来玄乎的“逆序”问题画完就通了。3.4 拿到最优值还不够输出选中的物品有时候笔试或实际项目里不仅要最大价值还要知道具体选了哪些物品。比如业务上你要知道“哪个需求被接受了哪个被放弃了”。这时候用一维dp就不方便了因为滚动覆盖会让旧状态丢失。我的建议是需要回溯时直接用二维dp先不管空间优化。回溯的思路很直接从最后一个物品开始往前倒推。如果 dp[i][j] 等于 dp[i-1][j]说明第 i 件物品没有被选如果 dp[i][j] 等于 dp[i-1][j-w[i]] v[i]说明第 i 件物品被选了。两者相等时说明两种情况价值一样你选哪个方向都能得到一组最优解。def knapsack_with_selection(n, capacity, w, v): dp [[0] * (capacity 1) for _ in range(n 1)] for i in range(1, n 1): for j in range(capacity 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]) # 回溯 chosen [] j capacity for i in range(n, 0, -1): if j w[i - 1] and dp[i][j] dp[i - 1][j - w[i - 1]] v[i - 1]: chosen.append(i - 1) j - w[i - 1] return dp[n][capacity], chosen拿刚才的例子跑一遍最后一件物品4没被选背包容量还是10物品3被选容量变成7物品2被选容量变成2物品1被选容量变成0。选中的下标是 [2, 1, 0]对应物品3、2、1。4. 新手踩坑实录从报错到结果错附调试方法4.1 三个高频bug与正确姿势第一个坑是内层循环正序。这个我在前面已经反复强调过它导致的结果不是编译报错而是“答案居然也对”只是对上了完全背包。数据刁钻时你会得到一个偏大的错误答案。怎么预防写一维时容量循环一律从 capacity 开始往下到 w[i] 结束别走捷径。第二个坑是下标错位。很多同学在Python里用 w[i] 而不是 w[i-1]导致数组越界或者拿错物品。常见的面试笔试题会给1-indexed的描述但代码实现往往是0-indexed。我自己的处理方法是代码里所有地方统一写成 w[i-1]、v[i-1]这样不管题意从几开始代码都不会错。第三个坑是容量初始化语义搞混。如果你做的是“容量恰好用完”的变体初始化必须区分“不选任何物品价值是0”和“某个容量无法达到价值负无穷”。比如 LeetCode 上有一类题要求恰好等于某个金额很多人都栽在这里。面试官看到你初始化成0就知道你默认了“不超过容量”而不是“恰好容量”。4.2 肉眼debug一轮dp表胜过十次print遇到结果不对先别乱改代码。最好的调试方法就是把dp表整个打印出来检查每轮更新是否合理。还是以上面那组数据为例如果你想验证第3件物品更新是否正确就打印第3轮后的 dp 数组看容量6的 dp[6] 是从9变成14。手动算一下前两件物品在容量6内最优是选物品2价值9现在拿了物品3价值8、重量3还剩下容量3能放物品1价值6所以14。如果打印出来的数据和手算不一致说明你的遍历顺序或者下标有问题。我实际调试时会在外层循环每走一步后就打印一次当前dp数组。很多新手觉得 print 效率低但在小数据量调试时这一步比盯代码发呆高效得多。我看到学生遇到“答案小了”的报告时最常用的办法就是让他打印数据大多数情况一眼就能定位是容量循环少写了一个位置。4.3 边界、初始化、模运算实战中的隐藏细节边界问题最常见的三种表现容量为0时所有dp值都是0物品重量为0时虽然现实中很少但题目可能这样出需要特别注意是否会引发无限重复选择数据量极大时答案可能超过 int 范围这时要用 long long 或者对某个数取模。我在竞赛题里见过不少“答案需要取模”的变体这时 dp[j] max(dp[j], dp[j-w[i]]v[i]) 仍然一样只是如果你要求方案数转移方程就变了变成 dp[j] dp[j-w[i]] 这种累加形式。所以不要死记公式先问清楚题目要的是“最大价值”还是“方案数”。关于“恰好装满”还有一个独家技巧初始化时让 dp[0]0其他 dp[j] -inf。这样在滚动数组里只有能被精确组合出来的容量状态才会是正数其他状态一直停留在负无穷。最后 dp[capacity] 如果还是负无穷说明不存在方案否则就是最大价值。这个技巧在做装载类业务需求时特别有用。5. 从01到多重背包给下一篇留好接口5.1 多重背包和01背包的“父子关系”多重背包问题说的是第 i 种物品最多有 s[i] 件可用不再是01背包那样只能选一次。你会发现如果每种物品只能选一次那就是01背包如果每种物品可以无限选那就是完全背包如果每种物品限定次数那就是多重背包。多重背包和01背包到底有什么关系如果把 s[i] 件完全相同的东西拆开看成 s[i] 个独立物品那多重背包就退化成普通的01背包。问题是直接拆会让物品数量爆炸。比如有100种物品每种最多100000件拆成个体会变成一千万个物品这谁顶得住。于是就有了一个经典优化思路二进制拆分。5.2 二进制拆分把次数拆成物品二进制拆分的本质是任何一种数量都能用若干2的幂次组合表示。比如13件物品我可以不拆成13个物品而拆成1件、2件、4件、6件四组。为什么是1、2、4、6因为前三个组分别是2的0次、2的1次、2的2次加起来是7剩下13-76。这样四组能表示的“取的数量”范围是0到13之间的任意整数。不信你可以验证要取0件一组都不拿要取5件拿1和4要取10件拿4和6要取13件四组全拿。用四个物品代替十三个物品复杂度从13降到了log2(13)级别。对应到多重背包我们把每种物品的数量 s[i] 拆成若干组每组作为一个“新物品”新物品的重量是 w[i]乘上组数价值是 v[i]乘上组数。然后整个问题就变成了标准的01背包直接套前面的一维模板。伪代码如下def multiple_knapsack_binary(n, capacity, w, v, s): new_w [] new_v [] for i in range(n): k 1 while s[i] 0: take min(k, s[i]) new_w.append(w[i] * take) new_v.append(v[i] * take) s[i] - take k 1 # 现在 new_w / new_v 是一堆01背包物品 m len(new_w) dp [0] * (capacity 1) for i in range(m): for j in range(capacity, new_w[i] - 1, -1): dp[j] max(dp[j], dp[j - new_w[i]] new_v[i]) return dp[capacity]这段代码我建议你自己手写一遍不要复制。写完你就能理解为什么二进制拆分没有丢状态也能理解为什么它比直接拆成 s[i] 个物品要快得多。5.3 一条主线上的后面几个兄弟先消化01背包和多重背包后面的路会顺很多。完全背包只是把内层容量循环从逆序改成顺序分组背包只是在01背包外面多套一层组循环依赖背包则是在选择物品时加入“选主件才能选附件”的约束。我个人的学习建议是给每一类背包准备一个“最小可跑题”不要只看题解。题型核心特征入门练习建议01背包每件最多选一次先手写二维和一维再回忆路径回溯完全背包每件可选无限次把逆序改正序自己推一遍差异多重背包每件有限次掌握二进制拆分动手拆一个s13的例子分组背包每组最多选一种在01背包外层加一层组循环依赖背包选子件需要父件先做枚举主件再套01背包如果你把这一篇从头到尾读完了建议你现在就打开编辑器随便生成一组随机数据比如 n100、capacity500写一个枚举版本和一维01背包版本对比结果。跑完你大概就明白背包问题最难的不是模板而是你能不能解释清楚“每次更新到底覆盖的是哪个旧状态”。把01背包弄透后面那些“兄弟”都是在同一个循环结构上做文章。