企业官网建设流程全解析

背包问题在算法圈的出镜率，高得有点离谱。不管是打ACM、刷LeetCode，还是准备大厂笔试，背包问题经常以“动态规划入门题”的身份出现，结果一上来就把不少人劝退。其实背包问题的变体看着多，核心就那两行状态转移。01背包、完全背包、多重背包、分组背包，说到底都是在同一个框架里打转。折腾了这么多年，我发现自己每次写背包题，用的模板几乎没变过。今天就把这套模板整理出来，顺带把每个公式背后的原因、以及各种容易踩的坑，一次性说清楚。如果你是刚开始学动态规划的萌新，或者刷了不少题但背包老写不对的老手，这篇都能帮你把背包问题理成一套能直接抄作业的东西。

1. 背包问题的整体脉络与模板设计思路

1.1 背包问题到底在考什么

背包问题的本质，是一个“有限资源下的组合选择优化”问题。给你一个容量为V的背包，和若干种物品，每种物品有重量w、价值v、可用的数量c，问在不超过背包容量的前提下，能拿到的最大总价值是多少。这个模型听起来很具体，但换个马甲就变成了很多现实问题：手里预算有限，怎么搭配商品组合收益最高；项目有固定工时，怎么分配任务让产出最大化；服务器有内存上限，怎么给不同容器分配资源。所以面试官和出题人都特别喜欢拿它当动态规划的入门题，因为它简单到能一眼看出状态，又复杂到能把循环顺序、初始化的细节都考进去。

学习背包问题，最关键的一步是先把问题抽象成三个要素：物品、体积/费用、价值/收益。物品可能只有一种属性，也可能有体积和重量两个属性；数量可能为1，可能无限，也可能有限。题目问的可能是最大价值、最小花费，也可能是方案总数。当你把一道题翻译成这三个要素，它到底是哪种背包，基本就清楚了。

1.2 为什么需要一套模板

我见过很多同学刷背包题，每道题都现场推状态转移，推一次错一次。不是推导能力不行，而是背包的细节太多：一维数组为什么要倒序？初始化用0还是负无穷？方案数要不要取模？这些问题在考场高压下特别容易记混。准备一套模板，本质上是把“从零推导”变成“按类型填空”。看到题目先分类，然后选择对应的模板，把数据填进去，再处理边界条件。模板不是用来死记硬背的，而是用来做“思考跳板”的。有了模板，你可以把精力放在题目的特殊限制上，而不是在基础转移上反复纠结。

我自己的习惯是维护一个“背包模板文件”，里面包含01背包、完全背包、多重背包、分组背包的代码，以及每个代码的注释说明：什么时候用正序、什么时候用倒序、dp数组初始值应该是什么。比赛前翻一遍，心里就有底了。这篇文章也会按这个思路，把模板和背后的原因一起给你。

1.3 常见背包类型与模板的横向关系

先看一张表，把四类最常考的背包问题摆在一起，心里有个整体认知。这些模型之间并不是孤立的，它们可以互相转化，尤其是多重背包，二进制拆分之后就直接变成01背包。

从表格里可以看到，01背包是绝对的地基。完全背包只是01背包把倒序改成正序；多重背包通过二进制拆分变成若干个01背包；分组背包则是在01背包外面多了一层“组”的循环。所以接下来先从01背包讲透，后面所有扩展都会轻松很多。

2. 01背包：一切背包问题的地基

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

01背包的定义再强调一次：有n件物品，每件重量为w[i]、价值为v[i]，每件最多取一次，背包容量为V，求能装下的最大价值。

我们用dp[i][j] 表示“只考虑前i件物品，背包容量不超过j时能获得的最大价值”。这里有个小细节，j表示“容量不超过j”而不是“恰好等于j”，这是我们后面初始化问题的关键。对于第i件物品，决策只有两个：不选它，那么状态就是dp[i-1][j]；选它，前提是j >= 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]。

这个转移方程可以说是整个背包问题家族的“总纲”。它本质上是一个多阶段决策：每处理一件物品，就是对“选”和“不选”两个分支做一次取优。你可以把dp数组想象成一张表格，行是物品编号，列是容量，表格里的每个格子都记录当前这个状态下的最优解。这样想的话，很多变体其实都是在往这张表格里填不同规则。

2.2 一维数组优化的倒序原理

二维dp虽然直观，但空间复杂度是O(nV)，当n和V都在1000以上时，需要1e6个状态，勉强可以；但如果n是1e5，V是1e5，就是1e10，直接爆内存。所以竞赛里几乎都用一维滚动数组。

一维数组dp[j]直接表示“容量为j时的最大价值”。外层循环枚举第i件物品，内层循环必须从V向w[i]递减。关键点来了：为什么必须倒序？

因为dp[j-w[i]]在一维数组中既可能是上一轮的结果，也可能是本轮已经被更新过的结果。如果正序更新，当你计算dp[j]时，dp[j-w[i]]可能已经被当前物品更新过了，也就是说当前物品被使用了不止一次，这就变成了完全背包。而倒序可以保证，在计算dp[j]时，dp[j-w[i]]还没有被本轮更新，它存储的仍然是“只考虑前i-1件物品”时的最优值，所以每个物品最多被选一次。

用生活化的例子说：你往背包里装东西，倒序相当于每件物品只拿一次，正序相当于同一件物品可以反复拿。算法没有魔法，顺序决定了物品的使用次数。

2.3 01背包标准模板

下面给出最常用的C++模板。数组下标从1开始存物品，重量存在w[1..n]，价值存在v[1..n]，容量为V。

#include <bits/stdc++.h> using namespace std; const int MAXN = 1005; const int MAXV = 1005; int w[MAXN], v[MAXN]; int dp[MAXV]; int main() { int n, V; cin >> n >> V; for (int i = 1; i <= n; i++) { cin >> w[i] >> v[i]; } // 求“不超过容量V”的最大价值：dp数组全部初始化为0即可 for (int i = 1; i <= n; i++) { for (int j = V; j >= w[i]; j--) { dp[j] = max(dp[j], dp[j - w[i]] + v[i]); } } cout << dp[V] << endl; return 0; }

Python版本也一并给出来，刷LeetCode或者面试手写时更常用：

n, V = map(int, input().split()) w = [0] * (n + 1) v = [0] * (n + 1) for i in range(1, n + 1): w[i], v[i] = map(int, input().split()) dp = [0] * (V + 1) for i in range(1, n + 1): for j in range(V, w[i] - 1, -1): dp[j] = max(dp[j], dp[j - w[i]] + v[i]) print(dp[V])

注意两个边界：内层循环从V到w[i]，小于w[i]的容量不用更新，因为放不下第i件物品，dp[j]自动保留上一轮结果。在Python里，range(V, w[i] - 1, -1)是倒序遍历的正确写法，步长-1时结束位置要减1，这个细节很容易写错。

2.4 基础变种：恰好装满、求最小值和方案数

模板最容易被坑的地方，是dp数组的初始化。

如果题目问“恰好装满背包时能得到的最大价值”，那么初始化时dp[0]=0，dp[1..V]=负无穷（比如-1e9）。理由是：只有容量0这个状态是合法起点，从0开始一步步凑出其他容量；其他容量在还没放任何物品时不可能是“恰好装满”的合法状态。在转移时，dp[j - w[i]]为负无穷的状态不应该被选进来，所以答案还是有效的。

如果题目问“总重量不超过V的最大价值”，则dp数组全部初始化为0，因为容量有多余无所谓，空背包本身就是合法方案。

如果题目问的是“最小价值”，就把初始化反过来：恰好装满时dp[0]=0，其余为+INF；不超过容量时全部为0。转移方程里的max改成min即可。至于“有多少种方案恰好装满”，属于一个独立的变体，后面专门用一章说。先把这三种基础搞明白，后面的变体才能不慌。

3. 完全背包与多重背包：模板的横向扩展

3.1 完全背包模板与正序原因

完全背包和01背包唯一的区别，是每件物品可以取无限次。很多人第一次学完全背包，会觉得它和01背包差别很大，其实只需要把内层循环倒过来。

for (int i = 1; i <= n; i++) { for (int j = w[i]; j <= V; j++) { dp[j] = max(dp[j], dp[j - w[i]] + v[i]); } }

正序的意思，是计算dp[j]时，dp[j - w[i]]可能已经在当前这轮物品i中被更新过了，这意味着当前物品可以重复使用。比如容量是10，物品重量是3，在正序更新到dp[6]时，dp[3]已经是“装了1个物品i”的价值，所以dp[6]可以再装1个，变成“装了2个物品i”。这样一路推下去，同一件物品可以被取任意多次。这就是完全背包的核心逻辑。

这里有个常见误区：有人觉得完全背包需要再加一层k循环，枚举物品选了几件。没错，暴力解法确实是这样，但复杂度是O(nVc)，完全不可接受。一维正序已经隐式地完成了“无限制取用”的优化，记住这个结论能省下大量时间。

3.2 多重背包二进制拆分优化

多重背包给了每件物品一个数量上限c[i]，既不是最多1次，也不是无限次，而是有限次。朴素想法是把c[i]件物品当成c[i]个01背包物品处理，但总复杂度会变成O(V * Σc[i])，很容易超时。

二进制拆分是竞赛里的标准做法。原理是：任何一个正整数c，都可以拆成若干个2的幂和一个余数，这些拆分出来的组可以表示0到c之间的任意整数。比如c=13，拆成1、2、4、6（剩余），其中1+2+4+6=13，这四个数通过选或不选，能组合出0到13的所有数量。于是原本13件相同物品，被压缩成4个“组合物品”，每个组合物品有重量w*k、价值v*k，再跑一遍01背包即可。

代码模板如下：

struct Node { int weight, value; }; vector<Node> items; // 拆分过程 for (int i = 1; i <= n; i++) { int cnt = c[i]; for (int k = 1; k <= cnt; k <<= 1) { items.push_back({w[i] * k, v[i] * k}); cnt -= k; } if (cnt > 0) { items.push_back({w[i] * cnt, v[i] * cnt}); } } // 对items跑01背包 for (auto &it : items) { for (int j = V; j >= it.weight; j--) { dp[j] = max(dp[j], dp[j - it.weight] + it.value); } }

注意二进制拆分的结束条件：剩余数量cnt不断减去k，当k大于剩余cnt时循环终止，然后要把剩下的cnt作为一个组补进去。这个“补余数”的步骤特别容易漏，漏了之后有些数量凑不出来，答案就会偏小。

3.3 分组背包与二维费用背包

分组背包是另一个高频变体。题目会给出若干组物品，每组内只能选一个，比如“每组代表一种选择方案，互斥”。模板的关键是循环顺序：先遍历组，再倒序遍历容量，最后遍历组内物品。写成C++大概是：

for (int g = 1; g <= groupCount; g++) { for (int j = V; j >= 0; j--) { for (int k = 0; k < group[g].size(); k++) { if (j >= group[g][k].weight) { dp[j] = max(dp[j], dp[j - group[g][k].weight] + group[g][k].value); } } } }

为什么容量循环要放在组内物品之前？因为要保证每个组最多选择一个物品。如果先枚举物品再枚举容量，同一个组里的多个物品可能在同一轮里被选进背包，就失去了“互斥”的含义。这一点从代码顺序上就能看出来，很多新手写反后答案会偏大。

二维费用背包则是在原有一维容量上再加一个限制维度，比如物品既有体积也有重量。这时dp数组变成dp[j][k]，表示在容量j和重量k的同时限制下的最大价值，转移多一维即可：

for (int i = 1; i <= n; i++) { for (int j = V; j >= w[i]; j--) { for (int k = W; k >= weight2[i]; k--) { dp[j][k] = max(dp[j][k], dp[j - w[i]][k - weight2[i]] + v[i]); } } }

二维费用背包的循环仍然是倒序，原理和01背包一样，都是为了“每个物品最多选一次”。如果物品可以无限取，就把倒序改成顺序。

4. 背包问题方案输出与方案数统计

4.1 方案数统计模板

有些题目不问最大价值，而问“填满背包的方案总数”。这是背包问题的另一种经典问法。转移方程从max变成累加：

dp[j] = dp[j] + dp[j - w[i]]

初始状态dp[0] = 1，表示容量为0时有一种方案：什么都不装。其余dp[j]初始化为0。枚举物品和容量时，01背包仍然倒序，完全背包仍然正序。下面以01背包为例：

dp[0] = 1; for (int i = 1; i <= n; i++) { for (int j = V; j >= w[i]; j--) { dp[j] = (dp[j] + dp[j - w[i]]) % MOD; } }

为什么是累加而不是取max？因为dp[j]包含了“不选当前物品的方案数”，以及“选当前物品之后，剩余容量j-w[i]对应的方案数”。这两类方案互不重叠，所以直接相加。注意这里dp[j]表示方案数，和前面最大价值的dp[j]含义完全不同，需要重新定义。

4.2 输出具体选择方案

如果题目不仅要最大价值，还要输出具体选了哪些物品，那就不能用一维dp直接回溯了，因为一维状态被覆盖了，无法知道每个容量下的上一轮状态。所以要么保留二维dp数组，要么额外用一个二维数组记录选择。

二维回溯的思路是这样的：先正常跑二维dp，得到dp[n][V]。然后从i=n、j=V开始，判断第i个物品是否被选中。如果dp[i][j] == dp[i-1][j]，说明不选第i个物品也能达到同样的价值，那就把i减1继续；如果dp[i][j] == dp[i-1][j-w[i]] + v[i]，说明选了第i个物品，记录它，并跳转到i-1、j-w[i]。两个条件可能同时成立，根据题目要求选择优先输出一种方案即可。

以下是记录选择的简化伪代码：

vector<int> chosen; int i = n, j = V; while (i >= 1 && j > 0) { if (dp[i][j] == dp[i - 1][j]) { i--; } else { chosen.push_back(i); j -= w[i]; i--; } }

有两点要注意：一是最终答案dp[n][V]可能等于dp[n-1][V]，这套回溯会优先选择不选，得到“不使用当前物品”的方案；二是当出现多种等价方案时，这个流程只能输出一种，若题目要求字典序最小，需要另做处理。

4.3 字典序最小方案处理技巧

字典序最小，意思是选中的物品编号序列，按从小到大排序后，字典序最小。比如{1, 3}小于{2}。

处理技巧是：DP反着做。从第n件物品往第1件做，dp[i][j]表示“从第i件到第n件物品，容量为j时的最大价值”。然后从第1件物品开始正着判断：如果当前容量j能装下第1件物品，并且选了它之后的收益不小于不选它的收益，也就是dp[i][j] == dp[i+1][j-w[i]] + v[i]，那么优先选择它，然后j减去w[i]；否则不选，跳到i+1。因为编号小的物品优先级高，所以能得到字典序最小的方案。

这个技巧在竞赛里不算高频，但在面试手写时可能会突然遇到，知道思路比临时硬推要稳。

5. 模板封装与实操经验

5.1 把多种背包模板封装成通用函数

平时刷题，我建议把背包模板写成函数，而不是每次都重敲循环。因为函数可以把“容量、物品数组、方式类型”作为参数，代码复用性更高。比如C++里可以写一个处理01背包的函数：

int knap01(const vector<int>& w, const vector<int>& v, int V) { vector<int> dp(V + 1, 0); int n = w.size(); for (int i = 1; i <= n; i++) { for (int j = V; j >= w[i - 1]; j--) { dp[j] = max(dp[j], dp[j - w[i - 1]] + v[i - 1]); } } return dp[V]; }

如果你担心下标问题，可以把w和v从下标1开始存，或者直接用这种从0开始的写法，只要下标对齐就行。我自己更习惯下标从1开始，因为状态转移里的i-1语义更清晰。但这个不是强制标准，重要的是每次写完检查一遍数组下标。

封装的意义不只是省代码，而是把“正序/倒序”这个区别隔离在函数内部。如果某道题需要同时处理01背包和完全背包，你可以写两个函数，名字一眼能区分，避免自己在主函数里把循环顺序写混。比赛时要的是稳定输出，不是现场炫技。

5.2 复杂度与数据范围估算

背包题的复杂度分析直接决定了模板能不能用。01背包时间复杂度O(nV)，空间优化后O(V)。当n=1000、V=1000时，是100万次运算，随便跑；当n=10^5、V=10^5时，10^10次运算，基本超时，需要考虑其他做法（比如价值范围较小的背包、单调队列优化等）。

完全背包同样O(nV)。多重背包经过二进制拆分后，物品数量从Σc[i]变成Σlog2(c[i])，再跑01背包，所以复杂度是O(V * Σlog c[i])。例如n=100、V=1000、每个c[i]=1000时，拆分后每个物品约10个组，总复杂度1000*100*10=10^6，非常快。

内存上，一维dp数组只需要O(V)。如果用了二维dp，记得考虑n*V会不会超过内存限制。一般题目给出V=1e4、n=1e3，二维就是1e7个int，约40MB，勉强可行；V=1e5就千万别用二维了。

5.3 用暴力对拍验证模板

模板写好后，怎么确认它是正确的？我自己的方法是写一个暴力程序或递归搜索，然后跑小数据对拍。比如n<=10、V<=20，暴力枚举所有物品组合，把最大价值算出来，和模板结果对比。如果随机生成1000组数据全部一致，那这个模板基本上没问题。

对于方案数问题，也可以用相同方式去验证：枚举所有子集，统计总重量为某个值的方案数，对比dp结果。把对拍脚本放在模板文件旁边，以后改模板时随时跑一遍，心里踏实。这个习惯帮我抓出过好几次递归边界写错的问题。

6. 常见问题与排查技巧实录

6.1 初始化陷阱

这是背包问题出错率最高的地方，没有之一。同样是求最大价值，题目说“不超过容量V”和“恰好装满容量V”，初始化的dp数组完全不一样。我把常见情况整理成一张表：

为什么恰好装满时要用-INF或INF？因为dp[j]要表示“凑到容量j”的合法状态，没凑到就是非法。如果你初始化为0，那么那些凑不出来的容量也会参与转移，导致错误答案。很多题目的样例故意用“恰好装满”当坑，就是考察这一点。

6.2 循环顺序混淆排查

背包问题里“正序/倒序”“外层物品/外层容量”是两大经典易错点。01背包外层物品、内层倒序容量；完全背包外层物品、内层正序容量；分组背包先组、再倒序容量、再物品。如果写反，结果通常不是偏大就是偏小。

排查技巧很简单：输出dp数组，用一个小样例手算验证。比如容量3，一个物品重量2价值5。01背包正确结果dp[3]=5，完全背包正确结果dp[3]=5（因为只能放1个）；再举容量4，物品重量2价值5，01背包dp[4]=5，完全背包dp[4]=10。如果结果不对，立刻能看出来是顺序问题。

6.3 数组越界与状态继承

一维背包写for (int j = V; j >= w[i]; j--)时，不用考虑j<w[i]的情况，因为那些状态会直接继承上一轮的dp[j]，不会发生变化。但如果你写成for (int j = V; j >= 0; j--)然后加if判断，千万别忘记判断，否则访问j-w[i]可能变成负数下标，程序直接崩。

二维背包也有类似问题，转移前要判断j>=w[i] && k>=weight2[i]。使用滚动数组时，还要注意每一轮是否需要把dp数组清零或拷贝，不同写法要求不同。

6.4 方案数溢出与取模

方案数累加时，最坏情况会指数级增长，哪怕n只有几十，方案数也可能超过int范围。通常题目会让答案对1e9+7取模。取模时要小心，加法取模没问题，但如果后面有减法，比如dp[j] = (dp[j] - dp[j-w[i]] + MOD) % MOD，否则可能出现负数。这个+MOD的小细节很多人会漏。

6.5 从TLE到AC的排查清单

如果你提交后超时，按这个顺序检查：

• 多重背包是不是还在用三层循环暴力枚举？如果是，改成二进制拆分。
• 完全背包是不是还在枚举k件物品？如果是，改成正序一维。
• 数组大小是不是开小了导致越界，越界有时会让程序卡死而不是报错。
• 是否能用滚动数组把二维降成一维？如果题目需要完整dp表回溯，就在回溯时用二维，否则用一维。
• 数据范围是否特别大，比如V达到1e9？那样背包dp本身就不适用，要考虑其他算法。

按这个清单，90%以上的背包超时问题都能定位到。

最后再分享一个小习惯：我把01背包和完全背包的模板放在一起，注释里专门写着“正序=无限取，倒序=有限取”，每次写题前扫一眼。尤其是紧张的时候，循环顺序写反的概率比想象中高。背包题万变不离其宗，拿到新题先判断三件事：物品能取几次？容量限制是几维？问的是价值还是方案数？判断完再选模板，基本就不会跑偏。希望这套模板能帮你把背包问题从“会背”变成“会懂”。