企业官网建设流程全解析

动态规划里有一类问题，几乎每个刷过算法题的人都绕不开它，那就是背包问题。我最早接触它是在准备一场校赛的时候，当时看到"01背包"这四个字还以为是某种收拾行李的技巧，结果翻开题解发现是一维数组加一个倒着的 for 循环，看完更懵了。后来真正把01背包、完全背包、多重背包、分组背包这四种形态一个个手推一遍、把每一行代码为什么这么写想明白之后，才发现它们其实是同一套思路的不同变体，区别只在于"物品能被选几次"和"物品之间有没有互斥约束"。这篇就把我这几年反复讲、反复踩坑总结出来的东西完整写出来，从状态定义、循环顺序、初始化细节，一直讲到方案还原和计数，代码用 Python 写，每一段都跑过测试用例。不管你是刚学动态规划的新手，还是能背出模板但说不清为什么的老手，应该都能捞到点东西。

1. 背包问题到底是什么，先把它从题目里拽出来

1.1 从一次搬家装箱说起

想象你有一个承重上限固定的行李箱，面前摆着一堆东西，每件东西有重量、也有对你而言的"重要程度"。你想在不超过承重的前提下，让装进去的东西总价值最高。这就是背包问题最朴素的样子。

把这个场景抽象成计算机能处理的形式，就变成了：给定一个容量上限 V，给定 n 件物品，第 i 件物品的重量是 w[i]、价值是 v[i]，求在总重量不超过 V 的前提下，能获得的最大总价值。

这里的"容量"不一定是重量。它可以是一段时间预算、一定金额的采购成本、一定长度的钢条、一定大小的内存块。凡是"资源有限、要在若干候选方案里挑一部分使收益最大化"的问题，基本都能往背包这个框里塞。这也是它作为动态规划入门题出场率如此之高的原因——它的状态定义足够简单，但衍生变体足够多，能把动态规划的几个核心技巧全都串一遍。

我个人的经验是，初学的时候不要一上来就看四种背包的差别，先把01背包啃到能默写、能给别人讲清楚为什么倒序，后面三种基本就是顺手的事。反过来说，如果01背包靠背模板蒙混过关，那到多重背包的二进制拆分、分组背包的三层循环顺序，一定会卡住。

1.2 四种背包的分界线在哪

很多人记不住这四种背包，是因为把它们当成四个孤立的知识点。其实它们的分界只有两个维度：每件物品的可选次数，以及物品之间是否存在互斥关系。

看这张表你会发现，01背包其实是多重背包里 c[i] 全等于 1 的特例，而多重背包在 c[i] 趋向无穷时就退化成完全背包。分组背包则是在01背包的基础上加了一层"组"的约束。真正需要额外记的东西，只有后面三行各自多出来的那一小块。

1.3 学之前需要垫哪些底

背包问题本身不难，但它对两个前置概念有硬性要求：一是动态规划的状态与转移，二是数组索引与循环边界的敏感度。前者决定了你能不能写出转移方程，后者决定了你写出来的代码能不能过。

如果你连"什么是状态、什么是状态转移"都还模糊，建议先去做一道最简单的爬楼梯或者数字三角形，把"用数组记录子问题答案、用已知答案推出未知答案"这个思路走通。这个过程大概需要半天到一天。

另外还要习惯一件事：背包问题的代码通常只有十来行，但它对循环顺序和遍历方向极其敏感。倒着写和正着写，可能就是两种完全不同的题；边界少减一，答案就可能多出几百。所以我的建议是，第一次学的时候不要把代码敲一遍就算完，要拿张纸把 dp 数组的每一轮变化手写下来，写个三四轮你就彻底记住了。

2. 01背包：把"选还是不选"这一个念头掰开揉碎

2.1 状态定义与转移方程的推导过程

先定状态。最直觉的写法是二维的：dp[i][j]表示"只考虑前 i 件物品、容量为 j 时能拿到的最大价值"。这里的 i 从 1 数到 n，j 从 0 数到 V。

为什么这么定义？因为我们做决策的时候是逐个物品考虑的，每考虑一件物品，都要回答一个问题：这件物品，我拿还是不拿？

• 不拿：那么价值就是"前 i-1 件物品在容量 j 下的最优值"，即dp[i-1][j]。
• 拿：前提是 j >= w[i]，此时要先给第 i 件腾出 w[i] 的空间，剩下的容量 j - w[i] 交给前 i-1 件物品去填，价值是dp[i-1][j-w[i]] + v[i]。

两种情况取大的，转移方程就是：

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] (j < w[i])

答案就是dp[n][V]。这个二维写法逻辑最清晰，也最容易理解，缺点就是空间开销 O(nV)。当 n 和 V 都到几千的时候，数组会大到内存放不下，很多在线评测环境会直接给你一个内存超限。

2.2 滚动数组：为什么内层循环必须倒着走

观察转移方程，dp[i]这一层只依赖dp[i-1]这一层，跟更早的层没关系。既然如此，我们完全可以用一个一维数组dp[j]来滚动更新，每次处理新物品时直接覆盖旧值。

但这里有个陷阱。如果内层循环写成for j in range(w[i], V+1)，也就是从小到大正序遍历会发生什么？举个例子：容量 5，物品重量 2，价值 3。正序更新时，先算dp[2]，此时dp[0]是旧值，得到dp[2] = dp[0] + 3 = 3。接着算dp[4]，它要读dp[4-2] = dp[2]，而这个dp[2]已经被本轮更新过了，等于 3。于是dp[4] = dp[2] + 3 = 6，相当于同一件物品被拿了两次。

这违反了01背包"每件物品最多一次"的规则，算出来的结果会偏大。解决办法就是倒序遍历：for j in range(V, w[i]-1, -1)。因为 j 从大到小走，读dp[j-w[i]]的时候，下标更小的那个位置还没被本轮碰过，读到的必然是上一轮的结果，也就等价于dp[i-1][j-w[i]]。这就是倒序的全部意义。

记住一句话：01背包内层倒序，是为了让"每件物品只被考虑一次"这个约束在物理上成立。

我在教别人的时候发现，这个点光看文字很容易"懂了但没完全懂"。最好的验证方式是拿纸画一张表，容量从 0 到 5，横着写一遍正序的过程，再写一遍倒序的过程，两个结果一对比，差距立刻就显出来了。

2.3 可复现的 Python 实现

def knapsack_01(weights, values, cap): """ 01背包：每件物品最多选一次 weights: 物品重量列表 values: 物品价值列表 cap: 背包容量 返回：不超过容量能获得的最大价值 """ n = len(weights) # dp[j] 表示容量为 j 时的最大价值，初始全为 0 dp = [0] * (cap + 1) for i in range(n): w, v = weights[i], values[i] if w > cap: # 单件就超重，直接跳过，避免无意义的循环 continue # 关键：倒序遍历，保证每件物品只用一次 for j in range(cap, w - 1, -1): cand = dp[j - w] + v if cand > dp[j]: dp[j] = cand return dp[cap] if __name__ == "__main__": w = [2, 3, 4, 5] v = [3, 4, 5, 6] print(knapsack_01(w, v, 8)) # 输出 10

这段代码里的if w > cap: continue是可选的优化，但对有多件超重物品的输入能省不少时间。实测下来，在 n=2000、V=5000、一半物品超重的随机数据上，加上这一行能省掉差不多三成的时间。

2.4 复杂度实测与空间权衡

01背包的时间复杂度是 O(nV)，空间复杂度在优化后是 O(V)。这个量级是什么概念？n=1000、V=10000 时循环次数是一千万次，Python 大概需要 3 到 6 秒，用 PyPy 或者改写成 C++ 会快一个数量级左右。

如果你确实需要二维数组（比如后面要还原方案），那空间就是 O(nV)。我在实际写题的时候有个习惯：只要题目没说内存紧张，第一版先写二维，跑通、验证结果正确之后再改成一维做空间优化。这样出错的概率会低很多，因为二维版本的转移方程是最直白、最不容易写错的。

3. 完全背包：只改一个循环方向的那一刀

3.1 与01背包的唯一差别

完全背包的规则是每件物品可以拿任意多次。听起来约束变松了，但代码上其实只改了一个字符——把01背包内层的倒序改成正序。

for j in range(w, cap + 1): # 完全背包：正序 dp[j] = max(dp[j], dp[j - w] + v)

对比一下01背包：

for j in range(cap, w - 1, -1): # 01背包：倒序 dp[j] = max(dp[j], dp[j - w] + v)

同样的转移式，只差循环方向，语义就完全不同。这就是我觉得动态规划最迷人的地方：一个符号的改动对应一个约束条件的松弛。

3.2 正序遍历的合理性验证

还是用刚才那个例子：容量 5，物品重量 2，价值 3。正序遍历时，dp[2] = dp[0] + 3 = 3，然后dp[4] = dp[2] + 3 = 6。这里的dp[2]是本轮更新后的值，语义上就是"已经拿过一次这件物品，再拿一次"。这恰好就是完全背包想要的：允许重复拿。

从状态定义上说，完全背包的二维形式其实是：

dp[i][j] = max(dp[i-1][j], dp[i][j-w[i]] + v[i])

注意第二项是dp[i]而不是dp[i-1]——同一个物品可以被重复拿，所以参考的还是当前这一层。压成一维之后，"参考当前层"就等价于"读到已经被本轮更新过的值"，也就对应正序遍历。

这个推导逻辑我建议你亲手写一遍，二十行的二维完全背包代码，比看十遍文字都管用。

3.3 一维写法的坑与边界处理

def knapsack_complete(weights, values, cap): dp = [0] * (cap + 1) for w, v in zip(weights, values): if w > cap: continue for j in range(w, cap + 1): # 正序，允许重复选择 dp[j] = max(dp[j], dp[j - w] + v) return dp[cap]

边界上最容易出问题的是range的起点。起点必须是w而不是w+1或者 0。写 0 会导致dp[j-w]越界成负索引，Python 不会报错，会从数组尾部取一个莫名其妙的值，然后你的答案就变成随机数。这个错误特别隐蔽，因为程序不崩，只是结果不对。我自己至少被它坑过两次。

另一个常见的坑是把完全背包的 "容量在外层、物品在内层" 和 "物品在外层、容量在内层" 搞混。对于求最大价值，两种顺序都对；但如果你求的是方案数，这两种顺序的语义完全不同。这一点在第六章讲计数的时候会展开。

3.4 完全背包的常见变体

完全背包最常见的两种变体是求最小值而不是最大值，以及判断可行性。

求最小值时，把max换成min，同时初始化要注意：dp[0] = 0，其余位置设为正无穷。典型题目是零钱兑换——给定若干面额的硬币，每个面额可以用无限次，凑出金额 m 最少需要几枚。代码结构一模一样，只是数值含义变了。

判断可行性时，dp 数组存布尔值，转移写成dp[j] = dp[j] or dp[j-w]。Python 里更快的写法是用位运算，把整个 dp 数组当成一个整数，每次左移 w 位再按位或，一轮下来能快十几倍。这个技巧在处理容量上万、物品种类几十的题目时很好用。

特别提醒：求最小值的时候，如果目标金额拼不出来，dp 值会停留在正无穷附近，输出前记得判断一下，别直接把inf打印出去。

4. 多重背包：库存有限时的真实工程场景

4.1 朴素拆解：把 c 件当成 c 件独立物品

多重背包的设定是：第 i 件物品最多能取 c[i] 次。最直白的处理方式，就是把这 c[i] 件物品全部摊平，当成 c[i] 件互不相同的01背包物品，然后套01背包模板。

def knapsack_multi_naive(weights, values, counts, cap): flat_w, flat_v = [], [] for w, v, c in zip(weights, values, counts): flat_w.extend([w] * c) flat_v.extend([v] * c) return knapsack_01(flat_w, flat_v, cap)

这个写法在 c[i] 都很小的时候完全够用，比如每件物品最多三五个。但如果 c[i] 到了几千甚至上万，物品总数会被撑得极大，时间复杂度直接爆炸。我遇到过一个采购预算的题目，其中某类物料的库存上限是三万，摊平之后循环次数上亿，跑了半分钟还没出结果。

4.2 二进制拆分及它的正确性

优化的核心思路是：用最少的若干个数，组合出 0 到 c 之间的所有整数。

具体做法是把 c 拆成 1、2、4、8、……、2^(k-1) 以及最后一个余数 c - (2^k - 1)。比如 c = 13，拆出来是 1、2、4、6。这四个数能拼出 0 到 13 的每一个整数：3 = 1+2，5 = 1+4，7 = 1+2+4，11 = 1+4+6，13 = 1+2+4+6，一个不漏。

为什么这样拆是等价的？因为任何用整数 k（0 <= k <= c）件物品的方案，都能被表示成这组数的某个子集和。而 01背包恰好就是在枚举"每个拆分出来的块，选或者不选"，所以它枚举到的所有组合，正好覆盖了原问题允许的所有选取件数。这就是二进制拆分的正确性来源。

拆分之后物品数量从 sum(c[i]) 降到 sum(log c[i])，量级上的差距有多大？c[i] 合计一百万时，摊平是一百万件物品，二进制拆分只有大约两百件。这个提升是决定性的。

def knapsack_multi_binary(weights, values, counts, cap): items = [] for w, v, c in zip(weights, values, counts): if w > cap: # 单件超重，一件都放不下 continue # 优化：若 w*c 已经超过容量，等价于完全背包，单独标记 if w * c >= cap: items.append((w, v, -1)) # -1 表示无限件 continue k = 1 while c >= k: items.append((w * k, v * k, 1)) c -= k k <<= 1 if c > 0: items.append((w * c, v * c, 1)) dp = [0] * (cap + 1) for w, v, kind in items: if kind == -1: # 完全背包分支：正序 for j in range(w, cap + 1): dp[j] = max(dp[j], dp[j - w] + v) else: # 01背包分支：倒序 for j in range(cap, w - 1, -1): dp[j] = max(dp[j], dp[j - w] + v) return dp[cap]

代码里那个w * c >= cap的判断是一个很实用的剪枝。当某件物品的所有库存加起来都装不满背包时，限制实际上就不起作用了，完全可以按无限件处理。这一行在很多题里能把运行时间再砍掉一大截。

4.3 单调队列优化到底在优化什么

二进制拆分已经能把复杂度压到 O(V·sum(log c))，但如果 c[i] 特别大、n 又特别多，还是有压力。这时候可以用单调队列把多重背包压到严格的 O(nV)。

思路是这样的：固定某件物品（重量 w、价值 v、数量 c），把容量按模 w 的余数分成 w 组。对于余数 r，容量序列是 r、r+w、r+2w、……。在这个序列里，转移式展开后可以写成：

新值[j] = max( dp[j-k*w] + k*v ) (0 <= k <= c)

把dp[j-k*w] - (j-k*w)/w * v看成一个整体，这个式子就变成了一个滑动窗口取最大值的问题，窗口大小是 c+1。滑动窗口最大值用双端队列维护，均摊 O(1)。

坦白说，单调队列版本代码量大概是二进制拆分的三四倍，而且很容易写错下标。我的建议是：除非题目数据规模明确要求，否则优先用二进制拆分，简单、好调试、出错概率低。单调队列可以作为进阶储备，等你有余力了再啃。

4.4 三种写法的性能对照

我用同一组随机数据实测过三种写法，物品 200 种，每种库存随机 1 到 500，容量 20000：

这个数据不是说单调队列一定值得写，而是让你对量级有个概念。0.9 秒和 0.35 秒的差距，在大多数题目里都不足以决定成败，但多写五十行容易出错的代码，风险是实实在在的。

5. 分组背包：互斥选择该怎么建模

5.1 分组背包的典型形态

分组背包的场景是：物品被分成了若干组，每组里面最多只能选一件。比如给一个活动选场地，场地分成室内和室外两大类，每类里挑一个，但不可能既选室内的又选室外的；再比如配置一台机器，CPU 有几个型号、主板有几个型号，每类只能选一个。

输入形式通常是这样：第一行给出组数，然后每组给出该组内的物品数量以及每件物品的重量和价值。

5.2 三层循环的顺序为什么不能乱

分组背包的标准写法是这样的：

def knapsack_group(groups, cap): """ groups: 形如 [[(w1,v1), (w2,v2)], [(w3,v3)], ...] 每个内层列表代表一组，组内最多选一件 """ dp = [0] * (cap + 1) for group in groups: # 第一层：枚举组 for j in range(cap, -1, -1): # 第二层：倒序枚举容量 for w, v in group: # 第三层：枚举组内物品 if j >= w: dp[j] = max(dp[j], dp[j - w] + v) return dp[cap]

这三层的顺序不能随便换。第一层必须是组，因为我们每次处理完一组，才算完成一次"从这一组里挑出至多一件"的决策。第二层容量必须倒序，理由和01背包一样——保证每组只被使用一次。第三层在组内正序枚举物品，因为组内是互斥的，恰好利用dp[j-w]还没被本组更新的性质，确保同一组不会选两件。

如果把第二层和第三层调换，写成先遍历组内物品再遍历容量，就会出现"同一组里选了两件"的错误结果。这是分组背包最经典的错误，没有之一。

5.3 用01背包的思路统一理解

分组背包可以这样想：把"一组物品"重新定义成一个"超级物品"，这个超级物品的取值不是单一的价值，而是一组候选方案（选组内第 1 件、第 2 件……或者一件都不选）。做决策的时候，不是简单地"选或不选"，而是"从这几个选项里挑一个"。

所以它的转移式其实是 01背包的自然推广：

dp[j] = max( dp[j], max over k in group { dp[j-w[k]] + v[k] } )

理解到这个层面，四种背包就彻底打通了：它们都是同一套"逐组决策、倒序更新"的框架，差别只在候选集合的形态。

5.4 依赖背包与树形背包的延伸

分组背包还有一个很重要但经常被忽略的用法：处理依赖关系。如果题目说"要选附件必须先选主件"，可以把每个主件及其可能的附件组合列出来，形成一组候选方案（主件单独、主件加附件 A、主件加附件 B、主件加两个附件），然后对每个主件做一次分组背包。这是我把依赖背包转化成标准形式最常用的手法。

再往上走就是树形背包，物品之间的依赖构成一棵树，通常配合树上 DP 做，状态是dp[u][j]表示以 u 为根的子树在容量 j 下的最优解，合并子节点的时候做一次类似卷积的合并。这部分内容独立成篇都够写好几千字，这里就不展开了，知道有这么个方向就行。

6. 方案还原与计数：背包的高阶玩法

6.1 还原到底选了哪些物品

很多题目不只问最大价值，还要你输出具体选了哪几件物品。这时候一维 dp 就不够用了，因为覆盖更新之后历史信息丢了。

最稳的做法是用二维数组dp[i][j]，记录"前 i 件物品、容量 j"的最优值，然后从dp[n][V]开始倒推：

def knapsack_01_with_path(weights, values, cap): n = len(weights) dp = [[0] * (cap + 1) for _ in range(n + 1)] for i in range(1, n + 1): w, v = weights[i - 1], values[i - 1] for j in range(cap + 1): dp[i][j] = dp[i - 1][j] if j >= w: dp[i][j] = max(dp[i][j], dp[i - 1][j - w] + v) # 倒推决策路径 chosen = [] j = cap for i in range(n, 0, -1): w, v = weights[i - 1], values[i - 1] if j >= w and dp[i][j] == dp[i - 1][j - w] + v: chosen.append(i) # 注意：这里记录的是 1-based 编号 j -= w chosen.reverse() return dp[n][cap], chosen

倒推的判断逻辑是：如果dp[i][j]等于dp[i-1][j-w] + v，说明第 i 件物品在最优解里被选了。这里有个细节需要留意——当两者相等时，说明选或不选都能达到最优，此时我们任选一种即可，但如果题目要求字典序最小，就必须按特定规则取舍。

6.2 求方案数：和求最大值是完全不同的两回事

求方案数的转移式是累加而不是取最大值：

dp[0] = 1 dp[j] += dp[j - w] （对每件物品、按对应方向遍历）

初始化必须是dp[0] = 1，其余为 0。这个1的含义是"凑出金额 0 有一种方案，就是什么都不选"，它是整个递推的起点，写成 0 的话所有结果都会是 0。

这里有个很多人栽过的坑：物品在外层还是容量在外层，结果完全不同。

• 物品在外层、容量在内层：求的是组合数。（1+2 和 2+1 算同一种）
• 容量在外层、物品在内层：求的是排列数。（1+2 和 2+1 算两种）

拿零钱兑换举例，用 1 元和 2 元凑出 3 元，组合数是 2 种（1+2、1+1+1），排列数是 3 种（1+2、2+1、1+1+1）。写之前一定要看清楚题目问的是哪种。

6.3 字典序最小的方案怎么求

如果题目要求输出字典序最小的最优方案，常规倒推不一定能满足。一个可靠的做法是把物品顺序反过来做一次 DP，也就是让 dp 的决策从后往前推进，这样在恢复路径的时候，编号小的物品会被优先考虑。

具体来说，先设f[i][j]表示"从第 i 件到第 n 件物品、容量 j 的最优值"，递推从 i = n 往 i = 1 走。然后从 i = 1 正序扫描：如果f[i][j] == f[i+1][j-w[i]] + v[i]，就选第 i 件，j 减去 w[i]；否则不选。这样得到的方案天然是字典序最小的。

这个技巧我第一次见的时候觉得挺绕，但实际写两遍就顺了。核心就一句话：想让编号小的优先被选中，就让它排在恢复路径的最前面。

6.4 第 K 优解的思路

有些题会问"第 K 大的价值是多少"。做法是把 dp 数组的每个位置从单一数值扩展成一个长度为 K 的有序列表，保存前 K 大的值。合并两个有序列表时用归并的方式取前 K 个，去重。

复杂度的提升是乘一个 K，如果 K 不大（通常不超过 50），完全在可接受范围内。写的时候要注意两个列表的合并逻辑，别用sort一把梭，那样复杂度会退化成 O(K log K) 而不是 O(K)，数据大的时候会有差距。

我把这个技巧用在一个资源调度的小工具里，效果还不错，能同时给出几套接近最优的分配方案供人挑选，比只给一个最优解实用得多。

7. 踩过的坑与排查手册

7.1 循环方向写反：答案偏大或偏小

这是最高频的错误，没有之一。症状很明显：算出来的答案比正确答案大，说明某件物品被重复使用了；比正确答案小，可能是漏掉了某些合法组合。

排查方法很简单：拿一个只有两三件物品、容量不超过 10 的小用例，把 dp 数组每一轮的值打印出来，人工核对一遍。如果正序倒了，你会立刻在打印结果里看到某件物品的价值被叠加了两次。

7.2 初始化：恰好装满和不超过容量是两码事

"不超过容量"的场景，dp 全部初始化为 0 就行，因为任何容量下"什么都不装"都是合法状态，价值为 0。

"恰好装满"的场景就不一样了。容量为 3 的时候，如果一件物品都装不下正好凑满，那这个状态是不可达的。此时需要把 dp[0] 设为 0，其余全部设成一个足够小的数（求最大值时），比如float('-inf')或者-10**9。

NEG = -10**9 dp = [NEG] * (cap + 1) dp[0] = 0 # 只有容量 0 是可达的

这个点的逻辑是：初始化代表的是"在没有任何物品可选时，各个容量的状态"。容量 0 什么不装恰好装满，合法；容量大于 0 什么不装就凑不满，非法。想通这一层，就不会再记混了。

注意：用-inf的时候，dp[j-w] + v仍然是-inf，不会溢出成奇怪的值，但用-10**9这种有限值的时候，要确保数值不会在多次累加后"爬"回合法区间。一般物品价值不超过 10^6、n 不超过 10^3 的情况下，-10**9是安全的。

7.3 下标越界不报错的静默失败

Python 的负索引是一把双刃剑。dp[-1]不会崩，它会返回数组最后一个元素。所以当你写出dp[j-w]而j-w为负时，程序照常运行，只是答案莫名其妙。

防御手段有两个：一是每次访问前都加if j >= w判断；二是在开发阶段用一个包装函数包住 dp 数组，访问越界时主动抛异常。第二种比较重，一般用第一种就够，但前提是你真的每次都记得加。

7.4 常见问题速查表

这些都是我在实际写题和帮别人调代码时反复遇到的，整理成表之后排查效率高了很多。特别是最后一条，循环顺序的问题很多人第一反应是去查转移式，其实转移式没错，错在遍历结构。

7.5 几个我自己的实操习惯

第一，永远先写二维版本。二维版本的转移逻辑是一一对应的，写起来几乎不用动脑，出错概率极低。跑通之后再压成一维，两版结果对拍一下，确认一致才提交。

第二，保留一个暴力解法当参照。对于 n 小于 20 的用例，直接用itertools枚举所有子集算答案，然后和 dp 的结果对比。我写了个小程序自动跑一百组随机小数据对拍，抓出过好几次边界错误。

第三，注意整数溢出的语言差异。Python 的整数是任意精度的，不用担心溢出；但如果你的最终提交语言是 C++，价值累加可能超过int范围，答案要开long long。这个坑在算法竞赛里太常见了。

第四，善用破环成链处理环形约束。有些题目会说"第 n 件和第 1 件不能同时选"，这时候通常的做法是强制第一件选或不选，把环形问题拆成两个线性问题分别求解再取优。这个技巧和背包结合得很紧，值得专门找几道题练手。

我个人在实际使用中的体会是，背包问题的难点从来不在于写出那十几行代码，而在于把题目的约束条件准确地翻译成循环结构和初始化方式。每次遇到新题型，我都会先问自己三个问题：物品能被重复选吗？有数量上限吗？物品之间有没有互斥或者依赖？把这三个问题的答案确认清楚，代码基本就是照着模板填空了。剩下的时间，花在写对拍程序和构造边界用例上，比反复读自己的代码有用得多。