减肥问题反向背包：回溯剪枝与动态规划双解法实战

先说下背景。这道题是我之前在准备某大厂OD机考双机位A卷时遇到的，题面包装成“小明减肥”，本质上是一道非常典型的组合优化问题：有限种食物，每样只能选一次，要在饱腹感达标的前提下让摄入热量尽可能小。当时第一反应就是“这不就是背包问题吗”，但真上手写才发现，它和经典0-1背包的方向正好相反，而且用回溯法也能做，只是数据范围一大就必须换成动态规划。这篇就把我当时的完整思路、两种解法的代码、以及踩过的坑都整理出来。

1. 题目还原与关键约束：这到底是不是背包装

1.1 题面一句话版本

题面大意是这样的：小明要减肥，但又不想饿肚子。现在有N种食物，每种食物有两个属性——热量c[i]（千卡）和饱腹感f[i]（分）。小明希望自己吃到的总饱腹感至少达到目标值X，问在满足这个条件的前提下，总热量最小是多少。每种食物只能选一次，选或不选，不存在“吃一半”或“吃两份”的情况。如果无论如何都凑不够饱腹感，输出-1。

约束范围我没法给出题目原版，但按这类机考的常见套路，N一般会在1到200之间，饱腹感目标X会在1到1000左右，热量和饱腹感的单值也都在千级以内。这个范围其实已经暗示了正解的方向：N到200，暴力枚举2的200次方绝对不现实，必须用动态规划；但如果你在别的场景遇到N只有20或30的同类问题，回溯法反而是最容易写对、最容易解释的方案。所以这道题作为“一题双解”的素材非常合适，它逼着你同时掌握两套思路。

1.2 和0-1背包的关系与反向背包

经典0-1背包长这样：有N个物品，每个物品有重量w[i]和价值v[i]，背包容量为C，问能装下的最大价值是多少。它的状态转移是dp[j] = max(dp[j], dp[j-w[i]] + v[i])，其中j表示当前背包容量，最后取dp数组的最大值。

小明减肥这题看着像背包，仔细一琢磨就会发现方向反了。食材的“热量”在背包里相当于重量，是我们要努力压小的东西；“饱腹感”相当于价值，但它不是“在容量内尽量多装”，而是“必须超过一个下限”。更准确地说，这题是在满足价值下限的前提下，最小化总重量。于是经典的max变成了min，经典的“容量不超过C”变成了“饱腹感不低于X”。

这种反向背包在机考里出现频率不低，比如“凑够x元最少用几张纸币”“达到某个属性值最少消耗多少体力”，都是同一类。如果你只会背正向背包模板，遇到这种题很容易把状态定义写反。

1.3 数据范围为什么决定了解法选择

我做算法题的习惯是读题之后先看数据范围，再看题面，顺序不能反。这道题的数据范围如果只看“组合问题”这几个字，很容易掉进回溯的坑里——毕竟组合、子集、枚举这些词天然让人想到DFS。但N到200的时候，回溯无论如何剪枝都救不回来，最坏情况还是指数级。

反过来，如果N只有15，你却兴冲冲写了个O(N*X)的DP，那也能过，只是有点杀鸡用牛刀。而且DP要求状态维度的值（饱腹感X）必须是可枚举的整数，假如X特别大，比如几百万，DP数组直接爆内存，这时候回溯反而成为备选方案。所以这道题的正确打开方式是：先看约束，再定解法。下面我把两种解法的完整思路都展开讲一遍，各有各的适用场景。

2. 回溯法：组合枚举的直白解法与剪枝优化

2.1 基础DFS框架

回溯法解这道题非常直白：把食物数组看成N个决策节点，每个节点只有选或不选两条路。DFS过程中维护两个值——当前累计热量cur_cal和当前累计饱腹感cur_full，走到终点时判断饱腹感是否达标，如果达标就更新全局最小热量。

我一开始写的版本长这样：

def min_calories_backtrack(foods, X): n = len(foods) # 先按热量升序排列，让较优解尽早出现 foods.sort(key=lambda x: (x[0], -x[1])) best = float('inf') def dfs(idx, cur_cal, cur_full): nonlocal best # 饱腹感达标，记录答案 if cur_full >= X: best = min(best, cur_cal) return # 当前热量已经比已知最优还大，没必要继续 if cur_cal >= best: return if idx == n: return # 选择当前食物 dfs(idx + 1, cur_cal + foods[idx][0], cur_full + foods[idx][1]) # 不选当前食物 dfs(idx + 1, cur_cal, cur_full) dfs(0, 0, 0) return -1 if best == float('inf') else best

这个版本能跑，但效率很一般。因为DFS会先把所有选或不选的组合都走一遍，即使已经发现当前热量超过已知最优解了，也只是剪掉一小部分分支。食物一多，这种纯枚举还是不现实。

2.2 两个常用剪枝：热量上界与饱腹下界

回溯真正好用的关键在于剪枝，而这道题恰好有两个天然剪枝条件。

第一个剪枝是热量上界。如果当前累计热量cur_cal加上剩下所有食物的热量之和，仍然大于等于已知最优解best，那这条路就算走到黑也不可能更优，直接剪掉。因为继续选只会让热量增加，不可能减少。

第二个剪枝是饱腹下界。如果当前累计饱腹感cur_full加上剩下所有食物的饱腹感之和，仍然达不到目标X，那说明无论怎么选都不可能达标，整个子树直接放弃。

要实现这两个剪枝，需要先预处理后缀和：

def min_calories_backtrack_optimized(foods, X): n = len(foods) foods.sort(key=lambda x: (x[0], -x[1])) # 后缀热量和、后缀饱腹感和 suf_cal = [0] * (n + 1) suf_full = [0] * (n + 1) for i in range(n - 1, -1, -1): suf_cal[i] = suf_cal[i + 1] + foods[i][0] suf_full[i] = suf_full[i + 1] + foods[i][1] best = float('inf') def dfs(idx, cur_cal, cur_full): nonlocal best if cur_full >= X: best = min(best, cur_cal) return if idx == n: return # 剪枝1：即使加上剩下全部热量也无法优于当前最优 if cur_cal + suf_cal[idx] >= best: return # 剪枝2：即使加上剩下全部饱腹感也达不到目标 if cur_full + suf_full[idx] < X: return # 分支1：选当前食物 dfs(idx + 1, cur_cal + foods[idx][0], cur_full + foods[idx][1]) # 分支2：不选当前食物 dfs(idx + 1, cur_cal, cur_full) dfs(0, 0, 0) return -1 if best == float('inf') else best

这两个剪枝合在一起，效果非常明显。我实测过N=20的随机数据，一开始无剪枝跑了大概几十万次递归，加上剪枝之后只剩几千次。原因很简单：热量下界和饱腹上界同时作用，把大量不可能的分支在很浅的层级就堵死了。

2.3 回溯法的适用边界：什么时候指数级也能过

别一听指数级就觉得不能碰。回溯法在这题里有明确的适用窗口：N在20以内时，即使不剪枝都能轻松跑完；N到30左右，配合上面两个剪枝通常也没问题；但N一旦到40以上，剪枝也撑不住，除非数据特别温和能提前找到全局最优。

我判断回溯法“能不能过”的经验公式是这样的：优先看X和热量分布。如果食物热量差异很大，剪枝1会在很早期就把差解淘汰；如果饱腹感数值普遍较小，大家都很难单独达标，剪枝2也会疯狂生效。换句话说，回溯法在**“答案藏在少数几个物品的组合里”**这种数据下表现得特别好，因为最优解一旦出现，best会迅速变小，热量上界剪枝立刻开始大面积生效。

另外，回溯法还有一个额外优势：它天然能输出具体选了哪些食物。DP虽然也能通过记录转移路径来回溯方案，但要额外维护choice[i][j]数组，代码复杂度上升不少。如果题目最后问“请给出一种具体方案”，回溯法的修改成本低很多。这个点我在后面第4节会展开对比。

3. 动态规划：以饱腹感为维度的最小热量状态机

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

动态规划的解法才是这道题的正主。状态定义我想了很久，最后确定成：dp[j]表示“吃到饱腹感至少为j时，消耗的最小热量”，其中j从0到X。初始化时dp[0]=0，其余全部设为无穷大。

为什么要定义成“至少”？因为题目要求是“总饱腹感不低于X”，而不是“恰好等于X”。如果定义为恰好，那么组合出的饱腹感一旦超过X，就得额外处理；定义为至少，再把超过X的所有情况全部截断到X，状态空间就干净了。这个设计是整道题DP解法的核心，新手第一次写很容易在这个地方绕晕。

转移方程也顺理成章：对于每个食物，我尝试把它加到已有的饱腹感上，并更新新状态的最小热量。

对每个食物 (cal, full)： 对 j 从 X 到 0 倒序遍历： 如果 dp[j] 不是无穷大： nf = min(X, j + full) dp[nf] = min(dp[nf], dp[j] + cal)

最终答案就是dp[X]，如果仍然是无穷大则返回-1。这里的min(X, j + full)就是在做“超过目标就截断”的归一化操作，非常关键。

3.2 一维滚动数组的循环顺序坑

用一维数组做DP时，内层循环必须倒序遍历。原因和经典0-1背包完全一样：正序遍历会让同一个食物在本次迭代里被重复使用多次。

我举个例子你就明白了。假设只有一个食物，热量7、饱腹感5，目标X=10，用正序遍历：j从0到10，一开始dp[0]=0，更新dp[5]=7；然后等j走到5，读到dp[5]=7，又更新dp[10]=14。这就等于同一个食物吃了一遍又一遍，最后算出热量14，但实际上只能选一次，正解应该是无法达到10、输出-1。这就是把0-1背包写成完全背包的典型错误。

倒序遍历则从后往前更新，dp[j]一定是上一轮食物处理完之后留下的旧值，当前食物的更新只会写入比j更大的下标，而后续的下标变小的循环永远不会再回头读取它，所以天然规避了重复使用问题。

def min_calories_dp(foods, X): INF = float('inf') dp = [INF] * (X + 1) dp[0] = 0 for cal, full in foods: # 倒序，保证每个食物只被使用一次 for j in range(X, -1, -1): if dp[j] == INF: continue nf = j + full if nf > X: nf = X if dp[j] + cal < dp[nf]: dp[nf] = dp[j] + cal return -1 if dp[X] == INF else dp[X]

这段代码跑在N=200、X=1000的数据上，复杂度是O(N*X)，也就是20万次操作，对任何机器来说都是瞬间完成。你可以把dp数组打印出来看看，每一轮更新后，dp[j]的含义就是“前若干个食物能凑出的最小热量”，下标越靠近X，代表饱腹感越接近目标。

3.3 处理“超过目标”的截断策略

关于截断我这里再单独强调一下，因为它决定了dp数组的边界与答案的语义正确性。

想象一个食物单独就能提供1000饱腹感，目标X只有10。如果不做截断，j+full=1000，你得把dp数组开到至少1000，浪费空间不说，还容易越界。截断之后，这个食物只会去更新dp[X]，语义是“一个食物就能达到目标”，完全合理。

但要注意一个隐含问题：截断之后，dp[X]可能同时代表“刚好X”和“超过X”两种情况，这没问题，因为题目问的是至少达到X时的最小热量，只要热量低、饱腹感达标就符合要求。如果题目变体要求“恰好等于X”，那截断策略就不能用了，必须把dp数组开大，最后在所有j>=X里取最小值。这个区分在面试讲思路时是加分项，在机考里则能帮你快速识别变体题的小陷阱。

4. 两种解法对比与实战选型判断

4.1 边界数据实测对比

纸上谈兵没意思，我构造了几组数据实际跑了一遍，结论很清楚。

第一组：N=20，X=150，食物热量在1到100之间随机，饱腹感在10到30之间随机。回溯法剪枝后跑了约1毫秒，DP跑了约0.5毫秒，几乎没差别，两种都能过。

第二组：N=40，X=1000，食物热量范围不变，饱腹感范围缩小到1到5。回溯法最坏还是得枚举大量组合，即便有剪枝，runtime到了几十毫秒，DP依旧1毫秒级别。但N=40其实还能接受。

第三组：N=200，X=1000，回溯法直接跑不动，DP依然秒出。这一组数据基本就宣告了：只要N超过50，回溯法只能当保底思路，不能当正解写在卷面上。

反过来说，如果题目改一下，X变成10的7次方，dp数组要开一千万个int，内存直接爆掉，这时候回溯法的“不依赖目标值大小”特性就变成优势了。所以这两种解法不是谁完全替代谁，而是互补关系。

4.2 需要输出具体方案的场景

如果题面多问一句“并给出选择哪些食物”，DP也能做，但要多开一个二维数组记录转移路径。具体做法是在每次dp[nf]被更新时，记下choice[j] = 当前食物，最后从dp[X]往回倒推时，用饱腹感差值找上一步的状态。代码量至少多出一倍，而且边界条件更容易写错。

回溯法这边就简单很多。DFS走到cur_full >= X且cur_cal == best时，直接把当前路径上选过的食物记下来就行。因为递归栈本身就记录了选择序列，你只需要额外维护一个selected列表，选食物时追加，回溯时弹出。

def dfs(idx, cur_cal, cur_full, selected): nonlocal best, best_path if cur_full >= X: if cur_cal < best: best = cur_cal best_path = selected[:] return # ... 剪枝逻辑略 selected.append(idx) dfs(idx + 1, cur_cal + foods[idx][0], cur_full + foods[idx][1], selected) selected.pop() dfs(idx + 1, cur_cal, cur_full, selected)

如果你在机考时遇到“只需要最小热量”这种最简版本，DP是首选；如果题目要求输出方案，你自己对DP路径记录不够熟，那N又不大时，直接用回溯法反而更稳。这是我个人在做题优先级上的判断：正确性优先，性能在满足数据范围的前提下往后排。

4.3 从这道题延伸的常见变体

小明减肥题本身不难，但它是一组常见变体的“母题”。我整理了几个高频改法，方便你举一反三：

这里特别提醒一句：变体改成“恰好等于X”时，截断策略必须删掉。否则饱腹感超过目标会被误算成等于目标，答案就会偏小。我遇到过类似题目，刚开始没注意，连续错了好几个用例才反应过来。

5. 机考环境下的细节与避坑清单

5.1 读题阶段最容易出的错

双机位机考环境比平时刷题更要小心，因为没法频繁切出去查资料，也没有IDE的智能补全和自动报错。读题时我会格外注意三件事：

第一，确认“每种食物只能选一次”还是“可以重复选”。题面经常会把这种关键约束藏在例子或一句不起眼的说明里。只看“小明想吃几份”这种表述很容易误判，一旦把0-1写成完全背包，样例可能过，但大数据量用例必挂。

第二，确认输出什么。这题问的是“最小总热量”，有些变体问的是“最多能吃到多少饱腹感且不超过某热量”，那状态定义就得反过来，变成dp[j]=最大饱腹感。目标变量一变，转移方向全变。

第三，确认无法达到目标时输出什么。通常会是-1，但偶尔会是0或空行。不仔细看输出格式，在判题器上会直接得0分。

5.2 手写代码时的边界测试要点

写完之后别急着交，心里过一遍这几个边界用例：

• N=1且该食物饱腹感恰好等于X，答案应该是该食物的热量；
• X=0，答案应该是0。有人会问，小明不吃东西饱腹感0，热量0，也是合法的，这个边界很容易被忽略；
• 所有食物饱腹感加起来都小于X，输出-1；
• 热量很大但饱腹感很小的极端数据，验证DP不会越界；
• 数据里有多个食物的热量饱腹感完全一样，验证程序不会因组合顺序不同而算出不同答案。

这些用例都在O(N)或O(N+X)时间内能跑完，机考时花30秒自测，能省下后面大量调试时间。我在练这道题时，第一次DP版本就在X=0的用例上漏了，幸好自测发现，不然查错半小时起步。

5.3 类似题目的快速识别方法

最后分享一个比较个人的经验。看到“组合”两个字，我脑子里会立刻出现一张决策图：如果N小于等于20，优先想回溯；如果N在100以上且约束值（比如这里的X）在万级以下，优先想DP；如果N又大、约束值又大到没法建表，那一半是数学题，要找公式或者贪心性质。

至于要不要写两种解法，我的建议是：机考时间允许的话，先用回溯法把样例跑通理解题意，再换成DP写最终答案。因为回溯法代码短、逻辑直观，写完后你对自己理解题意的信心会强很多，然后再写DP，错误率会明显下降。我后来做类似题目都是这个流程：回溯用于验证、DP用于提交。

这道题给我最大的收获倒不是那两个模板，而是“把目标约束变成状态维度”的思路。热量是最小化对象，饱腹感是硬指标，于是把饱腹感做成dp下标，把热量做成dp值。以后遇到“成本最小化+某个指标必须达标”的问题，我都会先问自己一句：能不能把那个硬指标变成数组下标？如果能，这题基本就是背包变体，闭着眼写DP就行。要是硬指标大到没法当下标，再回头考虑搜索和剪枝。