有些优化问题更容易表述为是非问题。与其猜测最优容量,不如询问某个给定容量能否处理输入;然后在有序的容量上进行搜索。二分搜索的正确性完全取决于其下的两个事实:可行性必须是单调的,并且检验本身必须正确。
1. 优化问题
一个由 个作业构成的非空序列,其大小为非负整数 。按原有顺序将其划分为至多 个非空连续批次。一个批次的负载是其中各作业大小之和。求最小的整数 ,使得每个批次的负载都不超过 。
连续性条件很重要:作业不能重新排序,也不能拆分。令 ,。每个可行的 都至少为 ,因为最大的作业必须放得下。容量 用一个批次即可行,即使某些大小为零也是如此。因此答案存在于 中。若 ,“至多 个”并不要求出现空批次;划分为 个单元素批次是允许的。
定义 15.1.1
(可行容量)
对大小 及限制 ,若序列可按原有顺序切成至多 个非空连续批次,且各批次的负载都不超过 ,则整数 称为可行。本问题的答案是最小的可行整数。
命题 15.1.2
(可行性向上封闭)
若 可行且 ,则 可行。因此可行整数的集合是区间 ,其最小元 就是答案。
证明
(同一划分仍然适用)
一个划分为至多 个非空连续批次、各负载都不超过 的划分,其各负载也都不超过 。所以同一划分证明 可行。一个在“取更大整数”下封闭、且含有可行的 的整数集合,必有最小元,而且恰是由该最小元向上的所有整数。∎
这是一个向上封闭的谓词,因此所求答案就是使其为真的第一个整数。二分搜索正是依赖这一点。
2. 贪心可行性检验
对于给定的非负容量,从左到右扫描。当且仅当加入下一个作业会超过 时,开启一个新批次:
feasible(a, k, C):
batches = 1
load = 0
for x in a:
if x > C: return false
if load + x > C:
batches += 1
load = x
else:
load += x
return batches <= k
输入非空,因此第一个批次包含一个作业:由于 且 ,最初的 load + x > C 检验不会开启一个空批次。大小为零的作业可以加入已满的批次。构造出的每个批次负载都不超过 。当且仅当贪心批次数不超过 时,结果为真。
命题 15.1.3
(贪心检验能判定可行性)
设 ,,整数 。过程 feasible(a, k, C) 返回真,当且仅当 可行。
证明
(贪心始终不比其他划分靠左)
若检验返回真。 过程构造的每个批次都非空,因为只有在已放入一个 的作业时才会开启新批次。每个负载都不超过 ,批次至多 个,所以 可行。
若 可行。 取一个划分为 个非空连续批次、各负载不超过 的划分。若某个作业超过 ,因大小非负,其所在批次的负载至少等于该作业,与可行矛盾;所以每个 ,检验不会在循环内返回假。设 为此划分前 个批次覆盖的作业数,,;设 为贪心前 个批次覆盖的作业数,,并以 为上限。我们证明对 都有 。
时两者都是 。假设 。若 ,则无须再证。否则 ,作业 是另一划分第 个批次的后缀。大小非负,所以它们的和不超过该批次的负载,因而不超过 。在一段非负作业中,负载不会减少,所以贪心的第 个批次在第一个会使负载溢出的作业前停止,覆盖从作业 起、负载不超过 的最长一段。这一段包含作业 ,所以 。
取 得 ,所以贪心在 个批次内完成并返回真。∎
证明透视
贪心证明在哪里用到非负性与批次限制
不显而易见的一步是比较 :我们并没有证明贪心与最优划分逐个批次相同,只证明每个批次之后它都不比对方靠左。这个陈述比最后的批次数更强,归纳法才能闭合。
非负性在两处用到,作用不同。第一,它使一段作业中的负载不会减少,所以在第一次溢出之前切开就得到最长的一段,贪心批次不会过早停止。第二,它使批次的后缀不重于整个批次,所以从 到 的一段放得下。限制 只在最后用来比较批次数 与 ;容量 在整个证明中固定,对 的单调性在此并未用到。需要上一个命题的是二分搜索,而不是贪心检验。
下一个区块说明为何不能丢掉非负性。
反例模式
大小可为负时贪心会失败
断言:对任何符号的整数大小,贪心检验都正确。取 ,,。单一批次 的负载为 ,所以 可行。过程令 ,遇到 时 ,于是开启第二个批次,最终报告两个批次,超过 ,返回假,但此容量其实可行。最长一段的论证失效,是因为批次的前缀 负载为 ,而整个批次却放得下。大小非负时,批次的任何前缀都不会比批次本身重,证明用到的正是这个性质。
3. 寻找第一个可行整数
利用上下界,并保持答案位于 中这一不变量:
lo = max(a); hi = sum(a)
while lo < hi:
mid = lo + (hi - lo) // 2
if feasible(a, k, mid): hi = mid
else: lo = mid + 1
return lo
当 mid 可行时,答案至多为 mid;否则,由单调性可知答案严格更大。区间收缩为单个可行的答案。至多需要 次可行性调用;若 ,则无需调用。读取数组并求出其上下界仍需 ,因此总代价为 次算术运算,以及保存数组所需的 存储空间。对于任意精度整数,算术运算的位代价需另行计算。
例题
例题 15.1.4
(最优值两侧的两个容量)
设 ,。此处 ,。
- 当 时,贪心得到 、、、:共四个批次,因此不可行。
- 当 时,贪心得到 、、:共三个批次,因此可行。
由于 6 不可行而 7 可行,单调性证明了最优值为 7。仅列出一种可行安排并不能排除容量 6。
例题 15.1.5
(同一输入上的完整二分搜索)
仍取 ,,所以 ,。第一个中点是 。 时贪心得到负载为 的 ,再得到负载为 的 :两个批次,可行,所以 。接着 ,由上一例可行,所以 。然后 ,不可行,所以 。此时 ,答案是 ,共做三次可行性检验,没有超过上界 。
例题 15.1.6
(大小为零与宽松的限制)
先取 及 。此时 ,所以 ,完全不需要可行性检验:答案是 ,一个批次即可(或三个单元素批次;不需要空批次)。再取 及 ,所以 ,。 时,贪心放入 ,再放入 (负载 ),再放 会得 ,于是结束于 、:两个批次,可行,所以 。 时零作业加入已满的批次,因为 ,贪心同样得到 、:可行,所以 。答案是 。
4. 算术问题与答案的含义
表达式 lo + (hi - lo) // 2 避免了将两个可能很大的非负端点相加,但它并不能自动保证输入之和是安全的。应选择能够表示 以及诸如 load + x 的每次加法结果的类型;在运算之前先进行类型提升。上述循环假定整个搜索过程中采用精确的整数算术,且输入保持不变。
常见错误
(负载一达到容量就结束批次)
若把检验写成 load + x >= C,作业刚好放得下时也会开启新批次。对 ,,:负载先是 ,再得 ,于是开启第二个批次,检验返回假。可是 本来就是一个负载为 的批次,所以 可行。批次可以恰好填满到容量;只有严格溢出才必须切开。
常见错误
(用太小的类型求和)
负载和上界 都是总和,而不是单个大小。若有 个大小为 的作业,则 ,超过有符号 32 位整数的最大值 。用 32 位类型计算 sum(a) 或 load + x 会溢出回绕,使搜索从错误的 hi 开始。在做任何加法之前,先选用能容纳 的类型。
检查清单。 说明非负性、顺序、连续性,以及限制是“至多”还是“恰好” 个。证明贪心谓词的正确性,给出一个确实可行的上界,论证单调性和上下界,并考虑和的数量级。不同的目标函数或负的输入需要新的证明。
快速检查
快速检查
(为何搜索可以从 开始,而不必从 开始?)
解答 · 答案
最大的作业必在某个批次之内,而大小非负,所以该批次的负载至少是 。因此任何可行容量都至少是 ,小于 的容量不可能是答案。
快速检查
(对 及 , 是否可行?答案是多少?)
解答 · 答案
时贪心得到 、、:三个批次,所以 不可行。 时得到 和 :两个批次,可行。由单调性,答案是 。
快速检查
(若 ,答案是什么?为什么?)
解答 · 答案
答案是 。容量 可行,因为允许 个单元素批次,每个负载都不超过 ;而小于 的容量都不可行。