物件可以分割時:密度與交換
定義 2.9.1
(分數背包與價值密度)
背包容量有限,物件有大小和價值。物件是否允許分割,會改變可以證明正確的算法。先設有有限個物件,大小 、價值 ;選取比例 ,所得價值是 ,所佔容量是 。給定 ,目標是在 下最大化 。定義價值密度 。
算法按密度由大至小排序,依次完整放入物件;遇到第一件不能完整放入的物件,就取恰好填滿剩餘容量的比例並停止。若所有物件都能放下,就全部取用;若 ,甚麼都不取。密度相同的物件可以任意排序。
定理 2.9.2
(分數背包的貪心規則)
對上述有限物件、正大小及非負價值,密度排序算法給出最優解。假設精確算術與比較均為常數時間,排序需要 次比較,其後掃描需要 次算術操作。
證明
(把大小轉向密度較大的物件)
為甚麼局部排序足夠?可行域是緊緻集,故最優解存在。固定排序,設貪心解為 。如果一個最優解首次在位置 與 不同,它在這裏只能取得較少:此前相同,而 不是已等於一,就是用盡了剩餘容量。如果某個後續物件 仍取了正比例,可把少量大小 從 轉移到 ;選擇足夠小的 ,使兩個比例仍在零到一之間。總大小不變,價值變化是 。每次盡量轉移,便可逐步消除後續分配或補足第 項。如果後續沒有取任何東西,直接補足第 項仍然可行且價值不減。這樣把一個最優解改成與貪心解多一致一項;對有限個位置歸納,貪心解也最優。密度相同時交換不改變價值,故不必假設密度互異。
例題 2.9.3
(允許分割與不允許分割)
容量為 ,三件物件的(大小,價值)為 、、,密度依次是 、、。分數算法完整取第一件,再取任一件大小為五的物件的 ,價值為 。若物件不可分割,後一步不合法;這時取後兩件可得價值 ,優於只取第一件所得的 。
交換證明依賴於從後面物件切出恰當大小,再以相同大小的前面物件替換。整件物件無法保證這一步可行。下面保留多種選擇,而不把分數規則直接用於零一背包。
零一狀態:記住所用物件和容量
定義 2.9.4
(零一背包問題)
現有 件帶編號的物件,第 件大小為整數 、價值為整數 ,容量 也是整數。每件最多選一次;即使兩件的大小與價值相同,也分別計作不同物件。目標是在總大小不超過容量的子集中取得最大總價值;空集始終可行。以下操作數假設精確算術和比較是常數時間;大整數的位元運算成本需另計。
定義 2.9.5
(前綴與容量狀態)
對 、,定義 為只使用前 件物件、總大小至多為 時可取得的最大價值。這是「至多」容量:允許有剩餘空間。沒有物件時 。
只記錄容量不能說明哪些物件已被使用;前綴 則把允許使用的物件說清楚。若 ,令 ;否則令
初始化第零行為零,按 依次計算每行的全部容量 ,返回 。為還原物件,對每個狀態保存一個選擇位元:僅當第二項嚴格大於第一項時標記「取」,否則標記「跳過」,包括相等或物件放不下的情況。從 開始;遇到「取」就輸出 並把 減去 ,每一步都把 減一,到零時停止。
常見錯誤
(把容量為零的一列初始化為零)
掃描不能漏掉容量零:零大小、正價值的物件可以選一次。因此只有在大小均為正等附加條件下,才可統一寫 。對只有一件 、容量為 的情形,正確的值是 ,而把該列初始化為零會得到 。
概念視角結構
把表看作分層圖上的最長路徑
為每個狀態 畫一個頂點。對 ,畫一條從 到 、長度為 的邊(跳過),並在 時畫一條從 到 、長度為 的邊(取)。從 下降到第零行的每條路徑,對每件物件恰好決定一次取或不取,並始終保持在容量之內,路徑長度就是所取物件的總價值,所以 是從 到第零行的最長路徑。遞推式就是每件物件一層的分層圖上的最長路徑遞推式。這解釋了為何每件至多使用一次(每條邊都下降一層),也說明還原只是讀出這條路徑。
定理 2.9.6
(正確性與資源)
上述算法返回最優價值以及達到該價值的可行子集。表格和選擇位元佔 空間,填表用同階單位成本操作,還原用 時間。只求價值時可用 空間。
證明
(按最後一件物件劃分子集)
任意最優子集要麼不含第 件,價值至多為 ;要麼含第 件,因而 ,移除它後得到容量至多 的前 件子集,價值至多為 。這給出兩個上界。當 時只有跳過可行;否則,有限個子集保證兩個前驅狀態都能取得其最優值;前者直接可行,後者加入第 件仍可行,且不可能重複使用該件。因此兩項均可達到,取最大值得到正確遞推。第零行正確,按 歸納便證明所有表格項,包括零大小和零容量。
還原時,每個選擇位元對應填表所用的等值分支。取物件就扣除其大小,然後轉到前一行;跳過也轉到前一行。所以每件最多取一次,總大小不超過原容量。沿選擇位元反向歸納,所取價值之和正好為 。兩項相等時跳過仍可達到最優;另一套一致的平局規則也可能得到不同的最優子集。
證明透視
一件只用一次的規則在何處落實
關鍵的一步,是從最優子集中刪去第 件,進入前綴指標為 的狀態。由於前綴指標縮小,第 件不可能再被選取,所以每件只用一次的規則是由遞推式的形狀落實的,而不是靠額外檢查。容量只是被限制,而不是被匹配:剩餘部分的大小至多為 ,這正是「至多」狀態所接受的。兩個方向都需要:上界說明最優值不超過兩個選項中的最大者,可達到性則說明它不小於該最大者。對 歸納,從空前綴的一行出發完結論證;零大小並無影響,因為 總是減少。兩個選項相等只影響還原出哪一個子集。
完整算表
例題 2.9.7
(三件互相競爭的物件)
設 依次是 、、,容量為 。第二行最後一格比較跳過第二件所得 ,以及取第二件後加上 所得的 。
| 0 | 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 3 | 3 | 3 | 3 |
| 2 | 0 | 0 | 3 | 4 | 4 | 7 |
| 3 | 0 | 0 | 3 | 4 | 5 | 7 |
從 開始,跳過第三件,因為 ;在 取第二件,剩餘容量二;再在 取第一件。總大小五、總價值七。只取價值最高的單件則只有五。
反例模式
在零一問題中,價值密度不是最優性的憑證
斷言:物件不可分割時,按價值與大小之比由大至小取用同樣最優。容量為 ,三件物件的(大小,價值)為 、、,比值為 。該規則先取第一件,其後兩件都放不下,得到 ;兩件大小為五的物件一起卻得到 。分數背包的交換論證需要用可分割的後面物件替換前面的物件,這裏做不到。修正方法是使用保留各種選擇的表 。
例題 2.9.8
(平局與零大小物件的還原)
設物件依次為 、、,容量為 。在 ,跳過或取第三件的價值都是 ,依照上述平局規則跳過。在 ,取第二件得到 ,大於跳過所得的 ;取它並轉到 。此時零大小物件使價值由 提高到 ,所以取它並轉到 。所得子集大小為 、價值為 。取第一件雖然不改變容量,行號仍減少,還原因此終止。改取第三件而不取第二件也是最優解。
壓縮表格時,次序也是證明的一部分
只求價值時,建立初值全為零的陣列 。對每個物件 ,由大至小遍歷 ,每個位置只賦值一次:
定理 2.9.9
(單陣列更新的次序)
從第零行出發,處理完第 件後,陣列 等於表格的第 行 ,條件是容量 按降序各訪問一次,且小於 的容量保持不變。
證明
(降序只讀取舊值)
若 ,右側較小的下標尚未在本輪更新,仍是前一行的值;若 ,右側讀取同一格賦值之前的舊值,而本輪每格只更新一次。因此每處理完一件,陣列恰好等於完整表格的對應一行。小於 的容量保持不變。不可對每格反覆更新直至不再改變。
證明透視
不變量保護的是物件的可用性
二維遞推只讀取前一物件前綴。降序遍歷在一個陣列中模擬這種隔離:需要較小容量時,它還未被本件更新。正確公式與正確迴圈次序共同保證每件最多使用一次。
壓縮後的最後一行本身亦不足以執行上述回溯;應保存完整選擇表,或另行證明還原方法。可變的容量前驅指標未必仍代表舊行,不能直接假定它正確。
反例模式
升序遍歷容量會重複使用物件
斷言:容量按升序遍歷時,單陣列更新給出相同的答案。只有一件 ,容量為 時,升序先把 設為 ,再用這個新值更新 ,返回 。同一件被用了兩次,而零一最優值是 。修正方法是降序遍歷,它只讀取舊值。
下面的互動圖以兩種容量次序重播壓縮更新,並把儲存的數值與保留的見證、天真的可變指標及完整表格回溯互相比較。
數值大小與輸入長度
常見錯誤
(把偽多項式界當作多項式時間)
狀態有 個,而非只有 個。時間對容量的數值 是多項式,但二進制表示 只需 位元。例如從 增加到 只增加二十位,表格容量維度卻約擴大一百萬倍。因此該算法稱為偽多項式,其操作數並未證明相對於二進制輸入長度的多項式時間。任意大的價值相加也須計入位元成本。
常見錯誤
(把不可能的恰好大小初始化為零)
「至多容量」與「恰好裝滿」不同。恰好大小狀態中,無法達到的大小必須標記為不可能,不能全部初始化成零。例如只有一件大小為二時,恰好大小一無法達到,而至多容量一的最優值是零。
建立恰好裝滿的表
如果要求總大小恰好為 ,定義 為前 件物件中總大小恰好為 的子集的最大價值;用 表示不可能的狀態。沒有物件時只能達到大小零,因此 ,而 時 。當 時,選擇形式仍是
其中約定 ;若 ,便沿用 。證明仍按是否包含第 件劃分,但取走該件後剩餘大小必須恰好是 。這個標記並非某個子集得到的價值:實際實作時,應先判斷前驅是否可能,再做加法。零大小物件仍讀取前一行,因此最多取一次。
例題 2.9.10
(恰好大小可能無法達到)
對於物件 和 ,容量由零至五的各行如下:
| 0 | 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|---|
| 0 | 0 | |||||
| 1 | 0 | 5 | ||||
| 2 | 0 | 5 | 4 | 9 |
其中 不可能:跳過第二件需要不可能的 ,取第二件則需要不可能的 。相比之下,至多容量的答案 ,取大小為二的物件並留下兩個單位空間。恰好大小五時兩件都取,價值為九。求至多容量 時,也可取大小 中可達到的恰好狀態的最大值;不能把不可能狀態當成價值為零的解。
練習與解答
快速檢查
(物件為 、,容量為三。求最優價值和子集。)
列出所有可行子集。
解答 · 答案
兩件一起大小為五,不可行。選第二件,價值五。
快速檢查
(物件為 、、,容量為零。求 ;為甚麼還原仍會終止?)
零大小物件在容量為零時也放得下。
解答 · 答案
兩件零大小物件均可選,價值五;第三件放不下。即使容量不變,還原時行號每步也減少一。
快速檢查
(只有一件 ,容量為二。升序壓縮更新返回甚麼?零一最優值是多少?)
依次追蹤兩次更新。
解答 · 答案
升序先令 ,再令 ,錯誤地重複使用物件。正確值為七。
快速檢查
(只有一件 ,容量為三。比較至多容量與恰好裝滿的答案。)
恰好裝滿的狀態需要一個標記值。
解答 · 答案
至多容量的答案是五,留下一個單位空間;恰好大小三不可能達到,應標記為不可能。
快速檢查
(容量為零且所有大小為正時,算法返回甚麼?考慮空物件表。)
考慮 時哪些子集可行。
解答 · 答案
只有空集可行,答案為零。物件表為空時,第零行就是整個計算。
比較兩個模型時,關鍵是先說明物件能否分割,再核對證明所保護的條件。