企业官网建设流程全解析

做题的人十有八九绕不开这个名字：开心的金明。别被它带点生活气息的名字骗了，这其实是一道非常硬核的经典动态规划题，来自NOIP2006普及组，在很多OJ上都以"题目1103"的编号出现。题目本身讲的是预算买东西：金明手里有N元，面对m件物品，每件物品有价格和重要度，要在预算内让"价格乘以重要度"的总和最大。"预算约束、每件物品只能买一次、求最大价值"这三个词组合在一起，几乎就是0-1背包模板题的身份证。对刚接触DP的初学者来说，这是绕不开的入门关；对有经验的人来说，它是压箱底的模板，隔段时间翻出来写一遍，反而能想通不少以前含糊的东西。最近搜这道题的时候，热词里总跟着"模板题"和"dfs序模板题"，后面那个说法其实是个挺有迷惑性的误会，这篇文章顺便把它讲清楚。

1. 先把题目读透：这到底在考什么

1.1 题目背景与输入输出构成

金明这个角色最早出现在NOIP2006普及组，题目背景是他家买了新房子，妈妈给了他一张"随便买但不超过N元"的额度，让他自己布置房间。输入第一行是两个正整数N和m，N是总预算，m是他看上的物品件数；接下来m行，每行两个正整数v和p，v表示这件物品的价格，p表示金明对它的重要度，重要度取值范围是1到5。注意这里有个容易看漏的细节：题目要求最大化的是"价格乘以重要度"的总和，不是单纯的价格，也不是重要度，而是两者的乘积。换句话说，一件"贵且重要"的物品，价值会比"便宜但重要"的物品高，这个乘积就是这道题里物品的"价值"。

输出一行，一个整数，表示在不超过N元的前提下能得到的最大总价值。以洛谷P1060的样例为例：预算1000，5件物品，分别是800配重要度2、400配重要度5、300配重要度5、400配重要度3、200配重要度2，最优选择是400×5、300×5、200×2这三件，总花费900，总价值3900。注意这里不是要求刚刚好花完1000元，只要不超过就行，这一点直接决定了DP数组的初始化方式。

数据范围在不同OJ上略有差别，数量级一致：N不超过30000，m不超过25。这个范围很有意思，m很小而N很大，它决定了为什么很多解法都能过，也提醒你读题第一件事永远是看数据范围，而不是闷头写代码。

1.2 为什么说它是"模板题"

这道题被冠以"模板题"三个字，不是因为它简单，而是因为它把0-1背包的要素暴露得干干净净，没有任何干扰项。0-1背包指的是：有若干物品，每个物品只能选一次，选或不选都行，在容量限制下求最大价值。开心的金明里，容量是预算N，物品是m件商品，"选或不选"对应买或不买，唯一需要动点脑筋的地方就是把价值定义成价格乘重要度。除此之外没有分组、没有依赖、没有额外费用、没有必须装满的要求，连物品本身的选择顺序都不影响结果。

正因为模型纯粹，它才配当模板。你在这道题里学到的状态定义、转移方程、滚动数组写法，可以原封不动搬到其他几十道题里。很多教学博客都拿它作为背包专题的第一题，就是这个原因。我也建议初学者不要急着跳过，把这道题的每个细节抠明白，再去啃分组背包和依赖背包，事半功倍。

1.3 澄清一个搜索热词："dfs序模板题"是个误会

如果搜题时看到"dfs序模板题"这个标签，很容易懵：这道题既没有树，也没有图的DFS序，跟"树的深度优先遍历顺序"半毛钱关系都没有。我查了一下，这个说法大概率是两种情况的混合：第一种，有人用DFS（深度优先搜索）加剪枝写过这道题，因为m不超过25，纯暴力枚举所有买法最多也就2的25次方种可能，配合预算剪枝在小数据下真的能过，于是搜索引擎或题库把"DFS"标签挂了上去；第二种，算法题网站自动打标签时，把"搜索"类问题和"动态规划"类问题合并出了这么个词。

我的建议是：别被这个标签带偏。这道题的标准解法是动态规划，DFS暴力枚举只配当对拍验证工具，后面会专门讲怎么用。你如果按"树的DFS序"来理解这个词，那完全是另一个领域的东西，跟金明没有交集。记住这一点，搜题时能省不少困惑。

2. 状态设计与状态转移：0-1背包的骨架

2.1 从暴力枚举到动态规划：思路是怎么一步步逼出来的

很多新手拿到这道题第一反应是穷举：每件物品买或不买，m件物品就是2的m次方种组合，每种算一下总花费和总价值，取合法且价值最大的。m等于25时，2的25次方大概3300万，理论极限下勉强能跑，但时间紧一点就悬；而且一旦m变成30、40，这个方案直接破产。所以必须找更聪明的办法。

有人会想，那贪心行不行？按"价值除以价格"从高到低买？很快就能找出反例。假设预算10元，三件商品：A价格6、重要度5，价值30；B价格5、重要度4，价值20；C价格5、重要度4，价值20。按性价比排序会先买A，花掉6元还剩4元什么都买不了，总价值30；可是最优解明明是买B和C，正好花10元拿40。贪心只盯着局部最划算，却牺牲了组合的全局最优，这就是背包问题为什么必须用动态规划的根本原因。

那动态规划的直觉从哪来？观察这个过程：当我们依次决定第1件、第2件……第i件物品买不买时，真正影响后续决策的，只剩下"还剩多少钱"这一个信息。至于之前具体买了哪几件，不关键；重要的是花了多少钱、拿到了多少价值。这就是"无后效性"：当前状态一旦确定，未来只跟当前状态有关，跟怎么走到这个状态的路径无关。于是我们可以用"处理到第几件物品"和"当前总花费"这两个维度来浓缩所有历史信息，这就是状态设计。

2.2 状态定义与转移方程

正式定义状态：dp[i][j]表示"从前i件物品中选，总花费不超过j元时，能获得的最大价值总和"。注意这里写的是"不超过j元"，不是"恰好j元"，这个措辞直接决定后面初始化怎么做。

对于第i件物品，设它的价格为v[i]，重要度为p[i]，那么它的价值w[i]等于v[i]乘以p[i]。面对它只有两种决策：

• 不买：问题退化成"从前i减1件里选，总花费不超过j元"，即dp[i][j]等于dp[i-1][j]；
• 买：要求j大于等于v[i]，先花掉v[i]元，剩下的j减去v[i]元交给前i-1件物品去安排，总价值是dp[i-1][j-v[i]]加上w[i]。

两者取较大值，就得到转移方程：

dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]] + v[i] * p[i])，前提是j大于等于v[i]。

这就是0-1背包最核心的一行公式。理解它的关键是：买第i件时，前i-1件的决策必须是"已经完成"的最优状态，所以我们永远从dp[i-1]那一行取数据，这正是后面滚动数组要倒序循环的根本原因。我见过不少人把方程背得滚瓜烂熟，但问一句"为什么必须从dp[i-1]取"，就答不上来，那这题等于还没学会。

2.3 边界条件：为什么要全部初始化为0

初始状态是dp[0][j]等于0，意思是一件物品都不选时，无论预算多少，总价值都是0，这很直觉。因为状态定义为"不超过j元"，dp[0][j]天然覆盖了所有j，所以整个数组初始化为0就够了，不用额外处理负数。

这里有一个对比很能说明问题：如果题目改成"必须刚好花完N元"，状态就要定义成"恰好花费j元"，那么初始化就不能全0了，要设dp[0][0]为0，其他dp[0][j]为负无穷，表示不可能恰好凑出那些金额。金明这道题没有这个要求，所以全部初始化为0，最后答案直接取dp[m][N]。很多初学者在别的背包题里照搬"全0初始化"，其实是因为没分清题目是"不超过"还是"恰好"。这个细节我每次讲背包都会强调一遍，因为它决定了你是输出dp[N]还是要遍历所有j取max。

3. 代码实现与细节打磨

3.1 二维DP：先写一版能保证对的

对新手来说，我建议先写二维版本，逻辑直观，不会踩滚动数组的坑。C++代码如下：

#include <cstdio> #include <algorithm> using namespace std; const int MAXM = 30; const int MAXN = 30005; int dp[MAXM][MAXN]; int v[MAXM], p[MAXM]; int main() { int N, m; scanf("%d%d", &N, &m); for (int i = 1; i <= m; i++) { scanf("%d%d", &v[i], &p[i]); } for (int i = 1; i <= m; i++) { for (int j = 0; j <= N; j++) { dp[i][j] = dp[i - 1][j]; if (j >= v[i]) { dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + v[i] * p[i]); } } } printf("%d\n", dp[m][N]); return 0; }

这里先把dp[i][j]默认成不买第i件时的值，再检查能不能买、买了是否更优。j从0扫到N，每一件物品都完整地更新所有预算区间。二维数组大小是25乘30000，不到100万个int，内存完全没问题。这样写虽然比滚动数组多开一点空间，但每个状态的含义一目了然，调试的时候很好用。如果你在学DP的早期阶段，这版代码值得背下来，但要在理解的基礎上背。

3.2 一维滚动数组：模板的标准形态

当N变大，比如一下子到10万，二维数组就会膨胀。更关键的是，观察转移方程会发现dp[i]这一行只由dp[i-1]推来，再往前的数据没用，所以完全可以用一维数组反复覆盖。标准写法：

int dp[MAXN]; for (int i = 1; i <= m; i++) { for (int j = N; j >= v[i]; j--) { dp[j] = max(dp[j], dp[j - v[i]] + v[i] * p[i]); } } printf("%d\n", dp[N]);

注意内层循环必须从N倒着走到v[i]，这是0-1背包最容易出错的地方。原因很简单：一维数组dp[j]更新之后，同一轮循环里如果继续往后遍历，dp[j-v[i]]可能已经是本轮刚更新过的值，它代表的是"已经买了第i件物品"的状态，你再在此基础上买第i件，等于同一件商品被买了两次，这就不叫0-1背包了，变成完全背包了。倒序遍历保证dp[j-v[i]]用的还是上一轮、即没考虑第i件时的旧值。用生活化的话说：正序就是同一件衣服反复试穿然后买走好几件，倒序才是每件只看一次。

3.3 数据范围与输入输出的细节提醒

这道题所有数据用int就够。价格v最多到10000，重要度p最多5，单件价值上限5万，25件全买也就125万，离int上限差得远。不过写习惯了也不吃亏，把dp和w声明成int完全没问题，只有在需要装更大结果的题目里才考虑long long。

另外一个小技巧：可以在读入时顺手把w[i]等于v[i]乘以p[i]算好存起来，后面状态转移里直接写w[i]，既减少重复乘法，也让代码更干净。我自己的习惯是变量名用v和w，一个表示花费，一个表示价值，这样后面套别的背包模板时思路能直接迁移。还有一个小经验：生产环境或者比赛里scanf和printf比cin和cout稳，尤其是数据量大的时候，虽然这题量不大，但早点养成习惯没坏处。

4. 常见错误、排查与实测心得

4.1 常见错误速查表

平时带新人时我发现，下面这几个错误几乎人人都踩过至少一个，整理成表格方便自查：

其中"价值写错"这个坑最隐蔽。很多新手以为重要度就是价值，结果样例输出对不上，排查半天才发现忘了乘价格。我建议在草稿纸上先把样例手算一遍，比如800乘2等于1600、400乘5等于2000，心里有数之后写代码就不容易跑偏。而"正序循环"这个错，往往是样例恰好能过，等交上去才WA，最气人也最锻炼人。

4.2 用DFS对拍：模板题也值得写暴力验证

前面说"dfs序"是个误会，但DFS本身在调试这道题时有大用处。我的习惯是，任何模板题写完DP后都用暴力DFS对拍一遍，确认模板没写歪。暴力思路特别简单：从第1件物品开始，递归地决定买或不买，走到第m件之后记录合法方案的最大价值。

int ans = 0; void dfs(int idx, int cost, int value) { if (idx > m) { if (cost <= N) ans = max(ans, value); return; } dfs(idx + 1, cost, value); // 不买第idx件 if (cost + v[idx] <= N) { // 买了不超预算再进入分支 dfs(idx + 1, cost + v[idx], value + v[idx] * p[idx]); } }

对拍流程是：写一个随机数据生成器，N取1到50，m取1到8，价格1到20，重要度1到5，然后让暴力DFS和DP各跑一遍，比较输出是否一致。m这么小，DFS瞬间跑完，生成几千组数据也不会有压力。只要有一次不一致，就说明DP状态转移或者循环方向有bug，这时候把那一组小数据单独拎出来手动模拟，很快能定位。

这个习惯我从一开始写题保持到现在，别觉得模板题就不用验证，恰恰是模板题最该验证，因为它将来要被你套用到几十道题上，地基歪了，上面的楼全是歪的。

4.3 从这道模板题能延伸出多少变式

"模板题"的另一个意义是它的可扩展性。以开心的金明为起点，简单改几个条件就是新题：

• 恰好装满：把状态定义成"恰好花费j元"，初始化时dp[0][0]为0、其余为负无穷。
• 分组背包：每类物品只能选一个，多一层小组循环。
• 依赖背包：金明的预算方案那题，主件没买就不能买附件，需要对附件做小背包后合并。
• 多重背包：每件物品有数量限制，用二进制拆分转成0-1背包。
• 求方案数：把max改成求和，理解"计数背包"的套路。
• 超大容量：N大到10亿没法开数组时，反转状态，用价值做下标、存最小花费。

这些变式在各大OJ上都能找到对应题目，而它们的核心骨架，都是这道题里写的dp[j]等于max(dp[j], dp[j-v[i]]加w[i])。模板题的价值不在背代码，而在于让你以后遇到"每个东西选或不选、容量有限、求最优"这类问题时，能在第一时间把它归约到背包模型上。

最后分享点个人体会。这道题我前前后后写过不下十遍，每次重写都有新收获：第一次学会了二维DP，第二次搞懂了滚动数组为什么必须倒序，第三次开始拿它当对拍模板，后来带新人时又拿它讲递归和递推的区别。踩过最大的坑就是正序循环，当年样例数据过了但交上去WA，对着代码看了一晚上才反应过来。所以别嫌模板题简单，把每一个"为什么"都抠明白，比刷十道新题都值。如果你也是刚开始学动态规划，建议把这道题当成第一个必须做到烂熟于心的模板，之后的路会顺很多。