题源链接：洛谷 P17012 [GESP202606 六级] 条形蛋糕

---

一、背景

在算法竞赛的动态规划专题中，有一类问题特别贴近生活——它们把抽象的背包问题包装成了日常场景，让人一看就懂，一做就懵。GESP 六级的这道条形蛋糕题，就是这类问题的典型代表。

题目场景很温馨：蛋糕店有一条长度为 $n$ 的长条蛋糕，不同长度的切块有不同的售价。店长想知道怎么切才能卖得最多。这本质上是一个"资源分割"问题：给定一个总资源（蛋糕长度），和若干种分割方式（不同长度的切块），每种方式可以无限使用，求最大总价值。

如果你学过背包问题，可能会一拍大腿：这不就是完全背包吗？没错。但完全背包的"正序遍历"和 $0/1$ 背包的"逆序遍历"到底有什么区别？为什么正序就能实现"无限选取"？本文就从这道蛋糕题出发，聊聊完全背包的核心思想，以及它与 $0/1$ 背包的本质差异。

---

二、核心思想

2.1 从"切蛋糕"到"完全背包"

拿到这道题，很多选手的第一直觉可能是：枚举所有可能的分割方式，然后算总价？但当 $n=1000$ 时，分割方式的数量会爆炸。我们需要一个更聪明的方法。

换个角度思考：把每种长度的蛋糕块看作一种"物品"，长度为 $i$ 的蛋糕块价值为 $p_i$，而"背包容量"就是蛋糕的总长度 $n$。每种物品可以无限选取（你可以切任意多块长度为 $i$ 的蛋糕），目标是装满背包（用完全部长度）且总价值最大。

这正是完全背包的标准模型：

• 物品：长度为 $i$ 的蛋糕块，价值 $p_i$
• 容量：蛋糕总长度 $n$
• 约束：每种物品无限供应
• 目标：总长度恰好为 $n$ 时，总价值最大

完全背包的特征：

• 无限供应：与 $0/1$ 背包的"每种物品只能选一次"不同，完全背包允许重复选取
• 正序遍历：内层循环从小到大遍历容量，使得同一物品可以被多次计入
• 最优子结构：$dp[j]$ 的最优解可以由更小的 $dp[j-i]$ 推导而来

2.2 为什么正序遍历能实现"无限选取"？

这是完全背包最核心的技巧，也是最容易让人困惑的地方。

在 $0/1$ 背包中，我们内层循环逆序遍历容量（$j$ 从 $n$ 到 $i$），目的是防止同一物品被重复选取。因为当处理到 $dp[j]$ 时，$dp[j-i]$ 还是上一轮（未选当前物品）的值。

而在完全背包中，我们内层循环正序遍历容量（$j$ 从 $i$ 到 $n$）。当处理到 $dp[j]$ 时，$dp[j-i]$ 可能已经被当前轮更新过了——也就是说，$dp[j-i]$ 可能已经包含了一块长度为 $i$ 的蛋糕。那么 $dp[j]=dp[j-i]+p_i$ 就相当于在"已经有一块长度为 $i$ 的蛋糕"的基础上，再添加一块。

我们可以把这个过程想象成搭积木：

• $0/1$ 背包：每种积木只有一块，搭完了就不能再用
• 完全背包：每种积木无限供应，搭完一块还可以再拿一块
• 正序遍历就像从左到右铺砖，每铺一块都可以在前面的基础上继续加
• 逆序遍历就像从右到左铺砖，确保每块砖只被用一次

2.3 状态设计的直觉

定义 $dp[j]$ 为总长度为 $j$ 时的最大价格。那么对于每个长度 $j$，我们枚举最后切下的那块蛋糕的长度 $i$（$1\le i\le j$）：

d p [ j ] = max ⁡ 1 ≤ i ≤ j { d p [ j − i ] + p i } dp[j] = \max_{1 \leq i \leq j} \{dp[j-i] + p_i\} dp[j]=1≤i≤jmax​{dp[j−i]+pi​}

这意味着：总长度为 $j$ 的最优方案，等于总长度为 $j-i$ 的最优方案，再加上一块长度为 $i$ 的蛋糕。

这就像俄罗斯套娃：大蛋糕的最优分割，包含了一个稍小蛋糕的最优分割，再加上最外层的一块。

---

三、算法模板

3.1 算法到底在干什么？——直觉解释

我们的算法是一台"最优切蛋糕机"：

1. 从短到长：先解决长度为 $1$ 的蛋糕怎么切最值钱
2. 逐步扩展：利用已知的短蛋糕最优解，推导更长的蛋糕怎么切
3. 枚举最后一块：对于每个长度 $j$，枚举最后切下的那块蛋糕的长度 $i$
4. 取最优：所有可能的"最后一块"中，选择让总价最大的那个

整个过程就像拼图游戏：先把小拼图拼好，再用小拼图拼大拼图，直到拼出完整的长度 $n$。

3.2 万能模板 —— 伪代码 + 实战代码

伪代码：

function 完全背包(价格表 p[1..n], 总长度 n):
    dp[0..n] = 0
    for i = 1 to n:           // 枚举每种蛋糕长度
        for j = i to n:       // 正序枚举容量
            dp[j] = max(dp[j], dp[j-i] + p[i])
    return dp[n]

实战代码（一维优化通用模板）：

#include <bits/stdc++.h>
using namespace std;

const int N = 1005;

int n;
int p[N];
int dp[N];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> p[i];

    // 完全背包：正序遍历容量
    for (int i = 1; i <= n; i++)
        for (int j = i; j <= n; j++)
            dp[j] = max(dp[j], dp[j - i] + p[i]);

    cout << dp[n] << endl;
    return 0;
}

3.3 例题实现 —— 本题完整代码（二维版本）

#include <bits/stdc++.h>
using namespace std;

const int N = 1005;                // 常量：最大蛋糕长度

int n;                             // n: 蛋糕总长度
int p[N];                          // p[i]: 长度为 i 的蛋糕块的价格
int dp[N][N];                      // dp[i][j]: 考虑前 i 种长度，总长度为 j 时的最大价格

int main()
{
    cin >> n;                      // 读入蛋糕总长度

    for (int i = 1; i <= n; i++)  // 读入各长度蛋糕块的价格
        cin >> p[i];

    for (int i = 1; i <= n; i++)  // 枚举考虑的蛋糕长度种类（1到i）
        for (int j = 0; j <= n; j++)  // 枚举当前总长度
        {
            dp[i][j] = dp[i - 1][j];  // 不选长度为 i 的蛋糕块

            if (j >= i)                // 如果当前总长度可以放下长度为 i 的蛋糕块
                dp[i][j] = max(dp[i][j], dp[i][j - i] + p[i]);  // 选一块长度为 i 的蛋糕
        }

    cout << dp[n][n] << endl;      // 输出最大总销售价格

    return 0;
}

3.4 对比实现 —— 完全背包 vs $0/1$ 背包

完全背包和 $0/1$ 背包的核心差异在于遍历顺序：

特征	$0/1$ 背包	完全背包
物品数量	每种 $1$ 个	每种无限个
内层遍历顺序	逆序 $j:n\to i$	正序 $j:i\to n$
状态转移	$dp[j]=\max (dp[j],dp[j-i]+p_i)$	$dp[j]=\max (dp[j],dp[j-i]+p_i)$
$dp[j-i]$ 的含义	上一轮（未选当前物品）	当前轮（可能已选当前物品）
空间复杂度	$O(n)$	$O(n)$
时间复杂度	$O(n^2)$	$O(n^2)$

注意：两者的状态转移方程形式上完全相同，区别仅在于遍历顺序！这个细微的差别决定了是"每种一次"还是"每种无限次"。

另一个值得注意的对比是多重背包（每种物品有限个 $k$ 个）：可以通过二进制拆分转化为 $0/1$ 背包，或者用单调队列优化到 $O(nm)$。

3.5 变体清单 —— 常见变形

变体类型	题目描述	关键变化	解法调整
$0/1$ 背包	每种蛋糕块只能切一块	物品数量有限	内层逆序遍历
多重背包	每种蛋糕块最多切 $k$ 块	物品数量有限	二进制拆分或单调队列优化
分组背包	蛋糕块分若干组，每组最多选一块	增加组约束	每组内部做 $0/1$ 背包
恰好装满	必须恰好用完长度 $n$	目标变化	初始化 $dp[0]=0$，其余为 $-INF$
不要求装满	总长度不超过 $n$	目标变化	初始化全 $0$，最后取 $\max (dp[\mathrm{0..}n])$
二维费用	蛋糕有长度和宽度两个维度	增加费用维度	二维 DP：$dp[j][k]$
输出具体方案	要求输出具体切割方案	需要记录决策	增加 $pre$ 数组记录转移路径

3.6 什么时候不能用？——边界条件和反例

完全背包虽然强大，但也有需要注意的边界：

• 负权物品：如果 $p_i$ 可以为负数，正序遍历会导致无限选取负权物品使总价值越来越小（如果求最大）或越来越大（如果求最小）。需要特殊处理或改用其他算法。
• 容量不是整数：如果蛋糕长度可以是实数，DP 的离散化方法失效，需要用其他方法（如贪心或数学分析）。
• 初始化错误：如果要求"恰好装满"，$dp[0]=0$ 而其余 $dp[j]=-INF$；如果不要求装满，全部初始化为 $0$。本题是后者。
• 一维 vs 二维：二维版本 $dp[i][j]$ 更直观但空间更大；一维版本空间优化但理解上稍难。两者等价，可以互相转化。

---

四、底层逻辑

4.1 为什么完全背包的状态转移是对的？

这是基于最优子结构的证明。

设 $dp[j]$ 是总长度为 $j$ 时的最大价格。考虑总长度为 $j$ 的某个最优分割方案，设其中最后一块蛋糕的长度为 $i$（$1\le i\le j$）。那么剩下的部分长度为 $j-i$，其价格必然也是长度为 $j-i$ 时的最大价格（否则我们可以用更优的分割替换它，得到更优的总方案，矛盾）。

因此：

d p [ j ] = max ⁡ 1 ≤ i ≤ j { d p [ j − i ] + p i } dp[j] = \max_{1 \leq i \leq j} \{dp[j-i] + p_i\} dp[j]=1≤i≤jmax​{dp[j−i]+pi​}

这个递推式的正确性依赖于无后效性：$dp[j]$ 只依赖于更小的 $dp$ 值，而与如何达到 $dp[j-i]$ 无关。

4.2 与经典问题的对比

这道题和经典的背包问题家族有密切联系：

问题	物品数量	遍历顺序	核心公式
本题：完全背包	无限	正序 $j:i\to n$	$dp[j]=\max (dp[j],dp[j-i]+p_i)$
$0/1$ 背包	$1$ 个	逆序 $j:n\to i$	$dp[j]=\max (dp[j],dp[j-i]+p_i)$
多重背包	$k$ 个	二进制拆分后逆序	转化为 $0/1$ 背包
分组背包	每组 $1$ 个	组内 $0/1$ + 组间完全	嵌套循环
树形依赖背包	有依赖关系	子树合并	DFS + 背包

可以看到，遍历顺序是区分不同背包类型的关键。正序 = 无限，逆序 = 有限，这是背包问题中最核心的记忆点。

4.3 隐含约束的分析

题目中有几个容易被忽略但至关重要的细节：

• $p_i$ 为正整数：价格都是正的，这意味着"切得越多不一定越贵"——比如长度为 $4$ 的蛋糕，不切卖 $9$，切成两块长度为 $2$ 的卖 $5+5=10$。DP 会自动找到最优的分割方式。
• 长度必须为整数：这是 DP 能工作的前提。如果允许实数长度，问题会变成连续优化问题。
• $n\le 1000$：数据范围小，$O(n^2)$ 的 DP 完全够用。如果 $n$ 达到 $10^5$，可能需要更高级的优化。
• 二维版本的理解：$dp[i][j]$ 中 $i$ 表示"考虑了前 $i$ 种长度"，$dp[i][j]=dp[i][j-i]+p_i]$ 中的 $dp[i][j-i]$ 表示"已经考虑了前 $i$ 种长度，且可能选了第 $i$ 种"，这正是"无限选取"的语义。

---

五、决策表

面对"资源分割/背包"类问题，如何根据约束条件快速选型？

场景特征	推荐方案	时间复杂度	备注
每种物品无限，最大化价值	完全背包（正序）	$O(nm)$	本题场景
每种物品 $1$ 个，最大化价值	$0/1$ 背包（逆序）	$O(nm)$	经典背包
每种物品 $k$ 个	多重背包（二进制拆分）	$O(nm\log k)$	拆成 $\log k$ 个 $0/1$ 物品
物品分若干组，每组最多 $1$ 个	分组背包	$O(nm)$	每组内部做 $0/1$
物品有依赖关系	树形依赖背包	$O(nm)$	DFS 序 + 背包合并
需要输出具体方案	记录决策路径	$O(nm)$	增加 $pre$ 数组
容量极大（$10^9$）	贪心或数学分析	视情况而定	DP 空间不够

一句话总结：无限正序，有限逆序，多重拆分，分组嵌套。

---

六、工程视角

完全背包和动态规划的思想在实际工程中有着广泛的应用：

1. 资源分配与预算优化：在项目管理和企业运营中，经常需要在有限预算（容量）下分配资源（物品），每种资源可以采购多份（完全背包）。例如，一个 $100$ 万的预算，可以投广告、买设备、招人，每种投入有不同的回报率，求最大总回报。

2. 硬币找零问题：给定若干面额的硬币（无限供应），求凑出金额 $n$ 的最少硬币数或最多硬币数。这是完全背包的直接应用，在金融系统和自动售货机中有实际意义。

3. 字符串编辑距离：虽然编辑距离通常用二维 DP，但其本质也是"在约束下选择操作序列"。完全背包的思想可以推广到更复杂的序列决策问题。

4. 网络流量分配：在计算机网络中，需要将总带宽（容量）分配给多个数据流（物品），每种数据流可以占用任意多带宽（完全背包），目标是最大化吞吐量或最小化延迟。

---

七、小结

本文从一道 GESP 六级真题出发，探讨了完全背包与无限分割的最优策略问题。

核心认知可以总结为：

当每种资源可以无限使用，且需要在总量限制下最大化价值时，完全背包的正序遍历是最优雅的解法；正序与逆序的区别，本质上是有没有"重复利用同一物品"的权利。

用公式化的语言概括：

d p [ j ] = max ⁡ 1 ≤ i ≤ j { d p [ j − i ] + p i } , d p [ 0 ] = 0 dp[j] = \max_{1 \leq i \leq j} \{dp[j-i] + p_i\}, \quad dp[0] = 0 dp[j]=1≤i≤jmax​{dp[j−i]+pi​},dp[0]=0

答案为 $dp[n]$，其中内层循环正序遍历 $j:i\to n$。

这道题教会我们的，不仅是如何写双重循环和状态转移，更是一种**“从小问题构建大问题”**的思维方式：在算法竞赛中，很多看似复杂的优化问题，都可以通过动态规划层层递推解决。完全背包的精妙之处在于，仅仅改变一个遍历顺序，就从"每种一次"变成了"每种无限次"。这种"细节决定算法"的体验，是动态规划最迷人的地方。

---

如果这篇文章对你有帮助，欢迎点赞收藏！有任何问题欢迎在评论区留言交流。