動機
看起來最划算的當前選擇,可能留下難以處理的餘數。用面值一、三、四的硬幣湊六,每次取不超過餘數的最大面值,會得到四、一、一;但兩個三僅需兩枚硬幣。貪心結果可行,卻不因此最優。
動態規劃把一次選擇變成一族定義精確的子問題。我們列出所有備選情況,證明它們涵蓋每個解,再按依賴已知的次序填表。表格不只能給出數值:保留合適的選擇,還可以恢復一個實際解。
有限 0–1 選擇問題
有 個按下標區分的物品。第 個物品有正整數重量 和整數價值 ,至多選一次。非負整數容量 限制總重量。允許空集,目標是在總重量至多為 時最大化總價值。價值可以為負;空集保證最優值至少為零。即使兩個物品重量或價值相同,也按下標區分。
定義 3.6.1
(前綴—容量狀態 )
對 、, 是只用前 個物品、容量至多為 時可獲得的最大價值。不同前綴和容量對應不同狀態。特別地,對每個 有 ;由於重量為正,還有 。
定理 3.6.2
(0–1 遞推)
對 ,若 ,則 。否則
按物品順序遞增填表,便得到最優值 。即使有多個並列最優子集,完整表格也支持恢復其中一個。
如何得到狀態轉移
證明
(按最後一個物品分類,再對行數歸納)
前 個物品的每個可行子集,或者不含第 個物品,或者含它。第一種情況下價值不超過 ,並且某個舊狀態最優子集能達到此界。第二種只有 時才可能;刪除第 個物品後,餘下的是前 個物品中容量至多為 的子集,其價值因而不超過第二個候選。反過來,把第 個物品加到實現該候選的最優子集上,不會重複使用任何物品。兩個候選中的較大者既可達到,又不小於任何可行子集的價值。
基礎行只允許空集。歸納地,只要前一行正確,當前行也正確。如果完整前一行保持不變,一行內部的容量可以按任意順序訪問。狀態中的容量含義是至多,不要求恰好填滿。若把基礎行除零容量之外都設為不可能,就改變成了另一種恰好重量問題。
恢復解時從 出發。若當前項等於正上方的項,略過該物品並移到前一行;否則該物品必定裝得下,且第二候選取到最大值:選入它,從容量減去其重量,再移到前一行。並列時略過是有效選擇。行號每步遞減,所以至多 步得到互不重複的物品,其總價值就是最終表項。僅保留最優數值,沒有選擇或舊行,本身並不是重建方法。
證明透視
背包證明中每個假設在哪裏用到
唯一的關鍵是按最後一個物品劃分:「不選第 個物品」與「選第 個物品」覆蓋所有可行子集且互不重疊,所以兩種情況各自的最大值中較大者,就是全部子集的最大值。每種情況都由兩個不等式完成:該情況中每個子集的上界,以及由較小狀態的最優解構造出的可達子集。第二候選讀取的是第 行而非第 行;正是這個下標使加入後的子集只用第 個物品一次。若改讀 ,便容許第二個副本,證明的就是另一個可無限複製問題的遞推。
重量為正用了兩次:它給出 ,並使 嚴格較小,後面的壓縮掃描需要這一點。歸納是對行號進行的,所以計算次序只需在第 行之前完成第 行。重建能夠結束也出於同一結構:每一步都移到第 行;並列時,上方的項本身由前 個物品的某個子集達到,所以略過絕不損失價值。
壓縮表格時如何避免重複選取
一維陣列在每個容量處初始為零。對每個物品,從 向下遍歷到 ,把當前項更新為自身與容量 的項加 二者的最大值。由於 ,較小容量在本物品的下降掃描中尚未訪問,仍保存前一行的值。因此更新恰好實現上述遞推。若 ,該物品沒有更新。
若反過來遞增掃描,較小容量可能已包含同一物品,讀取時陣列存放的就不再是第 行。一行用 個存儲項可計算最優值,但要直接使用前述方法恢復解,還需舊行或其他經過證明的附加資訊。
反例模式
遞推正確,更新次序仍可能錯誤
斷言:原地掃描可以按任一方向訪問容量。取一個重量二、價值三的物品,容量四,陣列按容量 為 。遞增掃描把容量二設為 ,容量三設為 。到容量四時,它讀取已被改寫的容量二,存入 。可行子集只有空集與該物品本身,價值分別為零和三,所以真實最優值是三:掃描把物品用了兩次。下降掃描先計算容量四,所讀容量二仍是未改動的零,結果為三。修正後的敘述:對 0–1 問題,掃描必須由 向下到 ;遞增掃描是可無限複製問題的遞推。
另一種狀態:恰好湊數的最少硬幣
現在設面值 均為正整數,每種可無限使用,目標數額為 。我們要求總和恰好為 的最少硬幣數;目標也可能無法湊出。
定義 3.6.3
(精確最少硬幣狀態 )
對 , 是總和恰好為 的最少硬幣數;無法表示時記 。基礎值為 。
定理 3.6.4
(精確最少硬幣遞推)
對 ,
其中空集合的最小值為 ,且 。按 的次序計算後, 就是最少數或正確的不可能報告。
證明
(移除最後一枚硬幣)
湊出正數 的每種表示都有最後一枚硬幣,設面值為 。移除它得到 的表示,所以原硬幣數至少為相應候選。反過來,只要較小狀態有限,加入所選硬幣就達到該狀態計數加一。若沒有任何較小狀態有限,就不存在表示。兩方向不等式與對 的歸納證明了遞推。面值為正至關重要:每個依賴都嚴格更小,恢復解也不會停在同一數額。
在每個正且可達的數額處,保存一個達到有限最小值的面值。從 開始,反覆輸出所存硬幣並減去其面值。剩餘數額嚴格下降,最終到達零;沿記錄的前驅,計數每次減少一。所得列表恰有 枚硬幣。當 時返回空列表;若 ,應報告無法表示,而不是嘗試回溯。
硬幣順序不影響最少枚數,所以把某枚稱為「最後一枚」只是證明工具。如果問題改為計數,區分有序序列與無序多重集就需要不同狀態或循環約定;僅憑最少數遞推不能決定那個計數問題。
概念視角結構
兩個表格都是無圈圖中的路徑
在每個數額 放一個頂點;只要 ,就從 到 連一條長度為一的邊。總和為 的硬幣序列,恰好是一條由 到 的有向路徑,其長度就是硬幣數。因此 是由 到 的最短路徑距離, 表示到不了 。每條邊都使數額減少,所以圖中沒有圈,而次序 把每個頂點排在它所指向的全部頂點之後。
背包表格有同樣的形狀。由 連一條權為零的邊到 ;當 時,再連一條權為 的邊到 。由 到第零行的路徑,每個物品至多選一次,所用重量至多為 ;每個可行子集也給出這樣一條路徑。因此 是到第零行的最大路徑權,而重建就是找回一條最優路徑。
成本與輸入含義
命題 3.6.5
(表格大小與運算次數)
完整背包表有 項,用 次精確操作構造;由它重建至多需 步。下降的一行數值算法使用 個存儲項。找零表格需要 次精確操作及 個存儲項,包括每個數額保存一個前驅。
每個背包表項用常數次比較及加法計算,每個找零表項至多比較 個候選;連同初始化便得到上述次數。輸出硬幣列表還需與其長度成比例的時間。
這些界是偽多項式的:它們依賴容量或目標的數值,而該數值可能比其二進制編碼長度指數地大。若整數物品價值的絕對值至多為 ,每個有限背包表項的絕對值至多為 ,所以算術位長為 。每個有限找零計數至多為 ,因為面值至少為一。無窮大用獨立標誌表示。比較、加法、索引和輸入存儲都須按表示方式計費;表項數量本身不能保證無界整數運算為常數時間。
為甚麼不依靠貪心也能保證最優值存在
0–1 問題只有有限多個子集,所以即使有負價值,最大值也存在。找零中每個面值至少為一,任何湊出 的表示至多含 枚硬幣;如此有界長度的可能序列只有有限多個。只要存在表示,最少數就能取到。遞推依賴的是這些極值和完整分類,而不是「局部最佳的第一步一定能擴展為全局最優」的斷言。
例題
例題 3.6.6
(0–1 最優值及其見證)
取重量 、價值 、容量六。物品一和三恰好裝滿,總價值十一;物品一和二價值九,二與三超重,三個物品也超重。任何單件都不更好,所以最優值是十一。沿完整表回溯可返回下標一和三。
例題 3.6.7
(先取最大硬幣可能失敗)
面值為一、三、四,目標為六。最大面值規則取四、一、一,共三枚。表中有 ,因此用兩個三得到 。面值中沒有六,不可能只用一枚,故 。這個反例並不聲稱貪心對所有面值系統都失敗。
例題 3.6.8
(能整除仍可能無法湊出)
面值四和六的最大公因數為二,但不能用它們的非負個副本湊出目標二。表中 、。目標被最大公因數整除是可表示的必要條件,卻不足以保證某個較小的非負目標可表示。
常見錯誤與範圍
常見錯誤
(「至多」容量不是精確目標)
容許容量有剩餘。一個重量二、價值五的物品,容量三時 。若把基礎行除零容量外都設為不可能,表格問的便是重量恰好為三,而這個物品做不到。基礎行必須配合所要解的問題。
常見錯誤
(哨兵值不是硬幣數)
用一個很大的有限數 表示不可能,會把 變成 ;它可能參與比較、溢出,或被當成計數輸出。加一之前先檢查是否不可能,把無窮大保留為獨立標誌,並報告無法表示,而不是從它回溯。
常見錯誤
(最優值不是見證)
數值 並沒有指出哪個子集,而且可能有多個子集並列。恢復的答案必須列出所選物品或硬幣,並核對其總和等於表項;只保留一行壓縮表時,這需要另外保存選擇。
本節證明的是兩種明確模型的精確離散優化,不由此得到一般貪心定理、以二進制輸入長度衡量的多項式界、浮點誤差保證或最優解個數公式。零或負面值及零重量物品需要另行指定模型,這裏不包含。
小結
動態規劃首先明確狀態及全部相關限制,再用完整分類得到遞推;歸納與尊重依賴的計算次序證明表格正確。保存前驅資訊後,最優值可以轉化為可核驗的物品選擇或硬幣列表;數值範圍則解釋了偽多項式成本。
練習
快速檢查
(物品重量為 ,價值為 。容量為五時,求最優值及一個達到它的子集。為何容量為零時價值為零?)
解答 · 答案
物品一和二總重量五、總價值九。單選物品三價值七,其餘配對和三件一起都超重。因此九是最優值,由下標一和二見證。容量零排除所有正重量物品,空集給出價值零。
快速檢查
(只有一個 0–1 物品,重量二、價值三。容量為四時,向下和向上原地掃描分別返回甚麼?哪一個符合所述模型?)
解答 · 答案
下降掃描返回三:計算容量四時,容量二仍是舊值零。上升掃描先在容量二寫入三,又錯誤地重複利用它,在容量四得到六。三才是正確的 0–1 最優值;六使用了兩次同一個物品。
快速檢查
(使用面值四和六。求 、 和 ,若能表示則恢復一個最少硬幣表示。)
解答 · 答案
空列表給出 。兩種面值都超過二,所以 。兩個四可以湊八,而一枚硬幣不行,因此 ,見證是四加四。
快速檢查
(若容量為 ,為何每個容量存一項的表不意味著關於位長 的多項式界?完整表回溯使用甚麼額外數據?)
解答 · 答案
容量只需 個二進制數字,表中卻有 個容量位置。表長對 為指數級,因此此界不是關於二進制輸入長度的多項式界。完整表回溯將當前項與前一行比較,必要時記錄選入,並移到前一行的較小容量狀態。