15.2.6 背包问题（贪心法）

贪心法的特点是每一步只看当前局部最优选择，不回头重做整体规划。它能不能得到最优解，取决于问题是否具有“贪心选择性质”。在背包相关题目中，部分背包可以用单位价值贪心保证最优；0-1 背包通常不能。

部分背包：单位价值贪心为什么成立

部分背包允许物品被切割。设第 $i$ 个物品的单位价值为：

$$r_i=\frac{v_i}{w_i}$$

做法是按 $r_i$ 从高到低排序，依次装入背包。若当前物品完整放不下，就取能放下的那一部分。

步骤	操作	原因
1	计算每件物品单位价值 $v_i/w_i$	衡量每单位容量带来的价值
2	按单位价值从高到低排序	先让容量产生最大收益
3	能完整放入就完整放入	不损失任何高单位价值物品
4	最后一件放不下就切割	剩余容量仍能被高单位价值填满

因为物品可拆分，剩余容量不会被“卡死”。这正是部分背包和 0-1 背包的根本区别。

0-1 背包中的“贪心策略”只是启发

课程在概述中列举了几种 0-1 背包的放置策略：

策略	局部规则	可能问题
优先放重量/体积大的物品	先占满容量	可能放入低价值物品
优先放总价值最大的物品	先拿最贵物品	可能剩余容量无法组合出更高价值
优先放单位价值最大的物品	每单位容量价值最高	仍可能错过组合最优
全部尝试再比较	枚举可行解	可靠但成本高，可用回溯剪枝

这些“优先”规则都体现贪心思想：只按当前某个指标作出选择。它们可以帮助快速找到一个满意解或辅助枚举，但不能作为 0-1 背包最优性的充分保证。

真题场景：集装箱装货也是贪心

字幕中的贪心真题不是传统“最大价值背包”，而是装箱问题：有 $n$ 个货物，体积为 $s_1,s_2,\dots ,s_n$，每个集装箱容量为 $C$，希望使用尽可能少的集装箱。题目给出两种策略。

最先适宜策略 First Fit

按货物给定顺序处理，每个货物放入第一个能够容纳它的集装箱。若前面箱子都放不下，就打开新箱子。

flowchart LR
  A["取下一个货物"] --> B["从 1 号箱开始检查"]
  B --> C{"当前箱能放下?"}
  C -- 是 --> D["放入该箱"]
  C -- 否 --> E["检查下一个箱"]
  E --> C
  D --> A

它是贪心法，因为每次只满足“当前货物尽早放入一个可行箱子”，不重新调整前面货物。

最佳适宜策略 Best Fit

仍按货物顺序处理，但不放入第一个能容纳的箱子，而是在所有能容纳它的箱子中，选择放入后剩余空间最小的箱子。

策略	当前选择规则	是否全局最优
最先适宜	找第一个能放的箱子	不保证
最佳适宜	找放入后剩余空间最小的箱子	不保证

注意“最佳适宜”里有“最佳”两个字，但它仍然是局部最佳，不是动态规划。考试常用这个词迷惑你：判断策略不能只看名字，要看代码是否保存中间状态、是否递推求全局最优。

复杂度怎么从代码看

这类装箱贪心代码通常有两层循环：

• 外层：遍历 $n$ 个货物。
• 内层：对每个货物扫描已有或可能的箱子，最坏可到 $n$ 个。

因此时间复杂度为：

$$O(n^2)$$

如果代码前面还有一个初始化数组的单层循环 $O(n)$，与双层循环相比是低阶项，最终仍写 $O(n^2)$。

实例模拟方法

模拟最先适宜或最佳适宜时，不要凭感觉“重新整理箱子”。题干说按给定次序处理，就必须按次序来。

模拟步骤	最先适宜	最佳适宜
处理顺序	按货物原顺序	按货物原顺序
找箱子方式	从前往后找第一个能放的	在所有能放的箱子里找剩余最小的
是否重排已放货物	不重排	不重排
结果	可能不是最少箱数	也可能不是最少箱数

代码填空提示

贪心装箱题常考：

• 某个箱子的剩余容量是否大于等于当前货物体积：b[j] >= s[i]。
• 找到箱子后更新剩余容量：b[j] -= s[i]。
• 最佳适宜中记录当前最小剩余空间或对应箱子编号。
• 外层货物循环与内层箱子循环的边界。

技术取舍

方法	优点	缺点	为什么不会直接替代所有方法
贪心装箱	实现简单，速度快，适合快速安排	不保证全局最优	若必须证明最优，需要更复杂的搜索/规划
回溯搜索	可找到最优解	最坏复杂度高	大规模时可能不可接受
动态规划	对特定容量整数问题可求最优	状态空间依赖容量和规模	容量很大时表格成本高

单选

“最佳适宜”装箱策略每次把当前货物放入能够容纳它且剩余空间最小的集装箱。该策略属于哪类算法思想？

A分治法B动态规划法C贪心法D回溯法

本节小结

贪心法要看“当前选择规则”。部分背包按单位价值贪心能得到最优；装箱问题中的最先适宜和最佳适宜也是贪心，但通常只能保证按规则得到一个可行/满意方案，不保证全局最优。