从今年整理这份“算法修炼之路”系列开始我就一直想把贪心、二分、正难则反这三个思维工具和背包问题里的两个经典模型放在一起聊。原因很简单它们表面上各自独立但在实际做题和面试手撕代码时经常是你中有我、我中有你。比如二分答案的 check 函数里跑个背包贪心策略需要证明才能放心用而“正难则反”很多时候就是救命的退路。这篇我就把这几个点结合在一起做一次比较硬核的精练总结配合完整代码和复盘记录给同样在刷题路上走着的朋友一份可以照着练的参考。先说清楚这篇文章适合谁。如果你正在准备算法工程师面试或者要打蓝桥杯、ACM 这类竞赛再或者只是觉得自己写代码总差点“套路感”这几块内容都值得下功夫。贪心考的是眼光和证明能力二分考的是边界和不变式意识背包考的是状态设计和对循环方向的理解。把这些搞明白性价比非常高。1. 贪心算法真正难的不是“想出来”而是“敢用”1.1 先聊聊我对贪心的理解贪心算法的核心其实一句话就能讲完每一步都选择当前看起来最优的决策最终希望整体也最优。但这句话里藏了个大坑——“希望”不等于“保证”。我在刚学贪心的时候最常犯的毛病就是看到一个题觉得“这不就每次取最大/最小嘛”结果提交上去 WA 到怀疑人生。贪心能成立的底层条件有两个一个是贪心选择性质另一个是最优子结构。前者指局部最优能导向全局最优后者指整体最优解包含子问题的最优解。这两个性质很多时候不是一眼能看出来的所以要学会“先猜后证”。我自己的习惯是先用简单的贪心策略手跑几个样例如果都对再尝试用交换论证法或反证法去证明。交换论证法尤其实用思路就是比较任意两个相邻选择如果可以交换它们的顺序而不让解变差那这个贪心策略大概率是对的。1.2 区间调度问题最经典的贪心入门案例说一个几乎所有教材都会讲、但值得反复咀嚼的例子区间调度。有若干个活动每个活动有开始时间和结束时间同一时间只能参加一个求最多能参加多少场。我第一次做这个题的时候直觉是选时长最短的或者选开始最早的。后来发现都不对。正确做法是按结束时间从小到大排序然后依次选择与前一个不冲突的活动。为什么“结束早”是对的因为结束早意味着给后面的活动留出了更多剩余时间这是一种典型的局部最优引导全局最优的场景。用交换论证法说假设最优解里第一个选的活动不是结束最早的那么用结束最早的那个去替换它不会减少可选后续活动的数量所以结束最早一定是安全的。这个“替换不减优”的思路值得记下来很多贪心题的证明都能套。经验提示遇到区间类问题先想一想应该按左端点排还是右端点排还是两者结合。排序键选错了后面全白搭。1.3 找零钱别急着贪一个经典反例贪心不是万能钥匙。看这个例子假设有面额为 1、3、4 的硬币要凑出 6 元每次尽量选大面额会选 4 1 1一共 3 枚但最优解是 3 3只要 2 枚。这就是贪心失败的经典反例。所以我在实际做题时如果发现贪心策略无法用一个清晰的理由证明会立即转向动态规划。很多人把贪心和 DP 看成完全不同的东西其实它们经常指向同一个问题的不同解法路径。贪心快但需要“底气”DP 慢但更通用。能把“什么时候该贪心、什么时候该 DP”判断清楚是刷题能力提升的一个重要标志。2. 二分算法查找只是冰山一角二分答案才是真正的杀器2.1 别再死记模板了先搞清楚边界为什么这么写二分查找本身并不难难的是边界处理。网上各种模板纷繁复杂什么左闭右闭、左开右闭还有那个经典的while (l r)配mid (l r) 1。我见过很多朋友死背模板但换个题目条件就懵了。我自己的经验是理解二分的关键在于“不变式”。以最常见的在升序数组中查找目标值从 0 到 n-1 的闭区间为例保持不变式目标值若存在一定在区间[l, r]内。当nums[mid] target时说明目标值在 mid 右边令l mid 1否则令r mid。这个写法下l最终指向第一个大于等于 target 的位置也就是 C 中lower_bound的结果。写二分的血泪教训就一条统一一套自己习惯的区间写法不要频繁切换。不然在考场上很容易出现“明明思路对但就是死循环或者漏元素”的情况。这里给出我常用的两套模板按需取用// 模板一在升序数组中查找第一个 target 的位置下界 int lowerBound(vectorint nums, int target) { int l 0, r nums.size(); // [l, r) 左闭右开 while (l r) { int mid l (r - l) / 2; if (nums[mid] target) r mid; else l mid 1; } return l; }// 模板二在升序数组中查找最后一个 target 的位置上界 int upperBound(vectorint nums, int target) { int l -1, r nums.size() - 1; // (l, r] 左开右闭 while (l r) { int mid l (r - l 1) / 2; if (nums[mid] target) l mid; else r mid - 1; } return l; }注意到第二个模板里mid的计算是l (r - l 1) / 2取了上中位数。在l mid这种更新方式下如果取(lr)/2的整数除法偏向下取整当l和r相邻时mid会等于l更新后l不变就死循环了。这个问题就是二分写错最常见的来源。2.2 二分答案怎么用把“求最优”变成“判可行性”二分查找只是最基础的形态真正体现二分威力的场景是“二分答案”。它的适用条件也很明确某个可行解的取值有单调性也就是当某个值 x 可行时比 x 更“容易”的值也可行那么就可以二分这个 x找到“可行与不可行”的分界点。举一个贴近实战的例子。有 n 根木头长度分别是 10、24、15现在要切成若干等长的段段长必须是整数至少得到 k 7 段问每段最长能切多长。这个题我第一次看的时候愣是没想出来怎么直接求最优解。但换个角度如果我问“长度 s 是否可行”那就简单了把每根木头能切出的段数加起来看看总数是否不少于 k。这个判断是 O(n) 的。然后因为 s 越大越难满足s 越小越容易满足所以可以二分 s。bool check(int s, vectorint woods, int k) { long long cnt 0; for (int len : woods) cnt len / s; return cnt k; } int solve(vectorint woods, int k) { int maxLen *max_element(woods.begin(), woods.end()); int l 1, r maxLen, ans 0; while (l r) { int mid l (r - l) / 2; if (check(mid, woods, k)) { ans mid; l mid 1; // 尝试更长的段 } else { r mid - 1; } } return ans; }注意边界上要特别小心 s 为 0 的情况除数不能为 0。一般从 1 开始枚举如果 1 都不可行说明根本切不了 k 段需要提前判断。这样的“最优转判定”思路在很多题目里都适用。比如“装东西的容器最小容量”“最短用时”“最大最小值的最小化”等问题很多都能用二分答案来解。算法导论里关于贪心和二分的内容之所以被反复读就是因为它们确实是算法思维的地基。3. 多重背包与完全背包从状态推演到代码落地3.1 完全背包为什么不能照抄 0/1 背包的逆序循环背包问题家族里0/1 背包是基础。每个物品最多拿一次状态转移为dp[j] max(dp[j], dp[j - w[i]] v[i])滚动数组要倒序遍历容量防止同一件物品被重复使用。完全背包就不同每个物品有无限件可用。一个直接的做法是再加一层枚举数量 k状态转移写成dp[j] max(dp[j], dp[j - k * w[i]] k * v[i])k 从 0 到 j/w[i]。但这样复杂度很高完全背包有更优雅的解法正序遍历容量。为什么正序就能表示“任意件都可以取”我自己的理解是这样正序遍历时dp[j - w[i]]在当前物品 i 的这一轮里已经被更新过它本身就包含了“我已经再放了一件物品 i”的情况所以当用它去更新dp[j]时就相当于允许无限续杯。这个逻辑如果只是记结论会很不放心建议亲手把一个小数据跑一遍递推过程把二维表列出来看就彻底懂了。// 完全背包核心代码 vectorint dp(cap 1, 0); for (int i 1; i n; i) { for (int j w[i]; j cap; j) { dp[j] max(dp[j], dp[j - w[i]] v[i]); } }3.2 多重背包的二进制优化把二百件物品拆成十几个多重背包的描述很直接每种物品有 c[i] 件可以拿 0 到 c[i] 件。最朴素的做法是把它当作 0/1 背包每件物品都拆成一件独立物品但 c[i] 很大时就会爆炸。二进制拆分法是这样做的对数量 c拆成 1、2、4、8... 的幂次组合直到剩余部分不足下一个 2 的幂。比如 c 13拆成 1 2 4 6注意最后一个是 6不是 8因为 1248 15 13要保证这些数字加起来不超过 c而且能组合出 0..13 之间的任意数量。证明也很简单任何整数都能表示成这些被拆分组的分组和加上余数部分的组合相当于把原来“选 k 件”拆成“对若干个物品做 01 选择”。最后每组物品的价值和体积乘以对应的件数扔进 0/1 背包模板即可。代码大概长这样vectorpairint,int goods; // {重量, 价值} for (int i 1; i n; i) { int w, v, c; cin w v c; int k 1; while (k c) { goods.push_back({k * w, k * v}); c - k; k 1; } if (c 0) goods.push_back({c * w, c * v}); } // 之后对 goods 做 0/1 背包即可这里的正确性关键在于二进制拆分能把 [0, c] 全覆盖。比如 c10拆成 1、2、4、3。三个二进制项 1,2,4 可以组成 0..7加上 3又能从 3 到 10 全覆盖正好补足了 7 到 10 的区间。这个“以少量物品覆盖所有选择数量”的思路以后遇到很多“可重复取但有限制次数”的问题都能用。我个人实测一个新坑拆完后的物品数量不是 log(c) 这么简单最后一个余数也要小心处理。经常出现少拆了最后一个余数导致答案偏小或者多加了一个重复包裹导致组合溢出。最好的排查办法是拆完后写个临时脚本验证 [0, c] 里每个数量都能被组合出来。3.3 正难则反遇到正面推导走不通就换个方向“正难则反”这句话听起来有点玄但它在算法题里真的是高频思路。最常见的场景就是计数类问题。比如计算满足某些条件的排列、方案数时正面分类容易漏反面用总数减去不合法的就非常清晰。背包问题里也有用到这种思想的地方。比如某些题要求“容量至少为多少”而非“恰好为多少”或者要求“超过阈值的数量”直接做状态设计会比较别扭。这时候可以把问题反过来设计状态或者用补集法减去不满足条件的方案。再举个更贴近贪心和二分的例子二分答案的 check 本身就是一种“正难则反”。你想直接求最优解很难但反过来让我验证一个答案可不可行就很简单。很多问题把视角从“求值”切换到“判定”难度立刻下降一个级别。我自己写题的时候有一个习惯如果一道题在正方向上卡了 20 分钟以上就主动停下来问自己一句——“反过来呢”。这个小小的思维习惯帮我解出过不少原本打算放弃的题。4. 实战复盘一道综合题拆开揉碎4.1 题目背景为了把前面几个知识点串起来我特意从刷题平台上找了一道综合性比较强的题目做样例。题目大意有一批货物每件有重量、价值以及最多可选的数量有些是无限件现在有一辆货车载重上限为 W。要求选货物的总重量不超过 W求最大总价值。这道题里一部分物品数量无限一部分数量有限还要求不能超过载重其实就是“完全背包 多重背包 0/1 背包”的混合体。如果只是背模板看到这种题容易乱。但如果理解了每一类背包的核心逻辑混合题反而很稳就是把无限件和有限件分开处理有限件先二进制拆分最后统一跑 0/1 背包。4.2 我的完整实现过程我先把所有物品分成两类一类是无限件完全背包另一类是有限件多重背包二进制优化拆分。然后把拆完的有限物品和无限物品统一处理。但这里有个小坑无限物品和有限物品不能直接丢到同一个循环里就跑因为完全背包要正序0/1 背包要逆序。我的做法是先处理有限件拆完就是 0/1 背包再处理无限件完全背包分两个循环跑。#include bits/stdc.h using namespace std; int main() { int n, W; cin n W; vectorint weight, value; for (int i 0; i n; i) { int w, v, c; cin w v c; // c 为 -1 表示无限件否则表示有限件数 if (c -1) { // 先存起来后续再统一做完全背包 // 这里简化处理直接调用完全背包部分 } else { int k 1; while (k c) { weight.push_back(k * w); value.push_back(k * v); c - k; k 1; } if (c 0) { weight.push_back(c * w); value.push_back(c * v); } } } // dp 数组 vectorlong long dp(W 1, 0); // 1) 0/1 背包处理二进制拆分后的有限物品 for (size_t i 0; i weight.size(); i) { for (int j W; j weight[i]; j--) { dp[j] max(dp[j], dp[j - weight[i]] value[i]); } } // 2) 完全背包处理无限物品这里需要再存一份无限物品的 w 和 v vectorint infW /* 所有 c-1 的物品重量 */; vectorint infV /* 所有 c-1 的物品价值 */; for (size_t i 0; i infW.size(); i) { for (int j infW[i]; j W; j) { dp[j] max(dp[j], dp[j - infW[i]] infV[i]); } } cout dp[W] endl; return 0; }上面的代码逻辑上用到了两个阶段处理实际写的时候建议把完全背包那部分单独封装成一个函数代码更清晰。我这里为了展示思想结构写得很直白。4.3 手把手验证一个样例假设货车载重 W 10。有两种物品物品 A重量 3价值 4数量无限物品 B重量 2价值 3数量限制 3 件。先处理有限物品 Bc 3拆成 k1 和剩余 c2再拆 k2剩余 c0。拆完得到两件独立的 0/1 物品一件 (2, 3)一件 (4, 6)。跑 0/1 背包后的 dp 容量从 0 到 10更新过程只列几个关键点j2 时dp[2] 3j4 时dp[4] max(0, dp[2]3)6 或 dp[4] dp[4-2]3 6取 6j6 时dp[6] 639等等。再处理无限物品 A正序遍历j3 时dp[3] max(0, dp[0]4)4j6 时dp[6] max(9, dp[3]4)9j9 时dp[9] dp[6]4 13。最终 dp[10] 会是 13。这个答案的组成可以是两个 B4,6加一个 A3,4总重 7再加一个 B 超了。更细的组合笔试时可以自己列表这里主要是说明整个混合背包的流程走通了。实际刷题时我建议每次写完这种综合题都自己手动构造一个小样例把二维 DP 表或者是滚动数组的更新过程跟一遍。这个过程看起来慢但能一次性把状态设计理解到位比刷十道重复题都管用。5. 常见问题排查与避坑手册5.1 二分边界问题的快速自查表二分写错是高频事故。我整理了一份自查思路遇到死循环或答案偏移时按这个顺序过一遍症状可能原因解决办法二分死循环mid 取了下取整但更新路径是 l mid把 mid 改成上取整即(l r 1) / 2最终答案偏小/偏大区间初始范围没覆盖到边界值检查 l 和 r 的初始取值务必让正确答案落在区间内查找目标值返回了插入位置而不是存在性混淆了“首个 target”和“是否等于 target”用 lowerBound 后判断返回位置的值是否等于 target浮点二分没到期望精度直接比较等于导致死循环改用迭代固定次数或while (r - l eps)尤其是最后一个浮点数二分的问题我踩过不少坑。浮点数的等值判断在二分里基本不可靠最稳的方式是固定迭代次数比如 60 次每次都把区间一分为二最终取 mid精度必然足够。5.2 背包问题初始化的陷阱很多题会问“恰好装满背包的最大价值”这和“不超过容量”的初始化方式完全不同。如果是不超过容量dp 数组全初始化为 0 即可表示空背包价值为 0但如果是“恰好装满”除了 dp[0] 0其他容量位置应该初始化成负无穷或者说极小值这样转移时只有能精确组合出的容量才会被更新到。我当时第一次做“恰好装满”的题目没有把 dp 初始化为负无穷结果跑出来一个看起来很大但根本达不到的答案。后来学会了一个口诀求最大价值、不要求装满初始化 0求方案数、不要求装满初始化 0如果要求恰好装满除 dp[0] 外全部负无穷。这个细节笔试面试里都出现过值得多留意几遍。5.3 多重背包二进制拆分后的验证方法二进制拆分是多重背包的常用优化手段但拆分完到底能不能覆盖 [0, c] 的所有可能数量我写过一个小脚本做过验证。原理很简单拆出来的每组数做一个子集和看看能不能凑出 0 到 c 的所有值。真实做题时如果心里没底我会用 10、13、15、17 这些数手算一遍很快就能建立信心。其实这个验证思路本身就是“正难则反”的一个例子不从“选 k 件”去看而从“拆出来的这些组能不能表示任意 k”去看问题的角度一转正确性就很好理解了。也顺便说一句如果你在竞赛里遇到多重背包数量超级大的题二进制优化可能不够还要上单调队列优化那就属于另一个专题了。6. 复盘一些我觉得值得继续深挖的点写到这里回头看看整篇内容表面上讲了贪心、二分、背包、正难则反但它们其实共用一套底层能力把“求最优解”转成“判定问题”以及掌握每一类问题背后的单调性或者结构性特征。贪心依赖局部最优到全局最优的传递二分依赖可行域的单调性背包的状态转移依赖选择空间的结构划分。看透这层关联比单纯记住某个模板要重要得多。我个人实际刷题过程中的体会是这几类思想的核心价值在于训练“抽象能力”。比如看到一个题先判断它的决策空间是什么样的是线性连续的一段二分适合还是一系列离散选择背包适合还是每一步都可以贪心贪心适合这个过程做多了就会形成一种条件反射看到相似题会自动往这几个框架上套。再分享一个小技巧。我备赛和准备面试时会坚持维护一份“思维触发笔记”把每道题对应的第一反应模型记录下来。比如某题虽然长得像是背包其实可以通过二分答案处理掉某题表面上是贪心但限制条件里藏着必须用 DP 的细节。这类“题型迷惑性”记录比单纯刷题更有用。接下来如果想继续往深处走我建议把四边形不等式、带权二分这类优化手段放到下一个阶段研究。它们和今天讲的二分、DP 是天然的交叉地带尤其带权二分某种程度上就是“二分答案 DP”的高级形态后面我会专门写一篇展开。算法修炼是一条长路第九站到这里算是一个小小的里程碑。希望你照着这篇里的思路亲手推一遍状态转移方程亲手调一遍二分边界亲手把二进制拆分的样例走一遍。这些动作看起来琐碎但恰恰是它们能把“看懂了”变成“真会了”。