有些最優化問題,改用「是或否」的方式來問會較容易處理。與其直接猜測最佳容量,不如問:某個給定的容量能否處理整個輸入?然後在有序的容量值中搜尋。二分搜尋是否有效,取決於其下的兩項事實:可行性必須是單調的,而且測試本身必須正確。
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;否則由單調性可知答案嚴格大於 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 開始。在作任何加法之前,先選用能容納 的類型。
檢查清單。 列明非負性、次序、連續性,以及限制是「最多」還是「恰好」 個。證明貪心謂詞的正確性,確立一個實際可行的上界,論證單調性及上下界,並考慮總和的數值大小。若目標函數不同或輸入含負數,則需要新的證明。
快速檢查
快速檢查
(為何搜尋可以由 開始,而不必由 開始?)
解答 · 答案
最大的工作必在某個批次之內,而大小非負,所以該批次的負載至少是 。因此任何可行容量都至少是 ,小於 的容量不可能是答案。
快速檢查
(對 及 , 是否可行?答案是多少?)
解答 · 答案
時貪心法得出 、、:三個批次,所以 不可行。 時得出 和 :兩個批次,可行。由單調性,答案是 。
快速檢查
(若 ,答案是甚麼?為甚麼?)
解答 · 答案
答案是 。容量 可行,因為容許 個單一元素批次,每個負載都不超過 ;而小於 的容量都不可行。