物件可以分割時:密度與交換
定義 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
(單陣列更新的次序)
從第零行出發,處理完第 件後,陣列 等於表格的第 行 ,條件是容量 按降序各訪問一次,且小於 的容量保持不變。
證明
(降序只讀取舊值)
若 ,右側較小的下標尚未在本輪更新,仍是前一行的值;若 ,右側讀取同一格賦值之前的舊值,而本輪每格只更新一次。因此每處理完一件,陣列恰好等於完整表格的對應一行。小於 的容量保持不變。不可對每格反覆更新直至不再改變。
證明透視
不變量保護的是物件的可用性
二維遞推只讀取前一物件前綴。降序遍歷在一個陣列中模擬這種隔離:需要較小容量時,它還未被本件更新。正確公式與正確迴圈次序共同保證每件最多使用一次。
壓縮後的最後一行本身亦不足以執行上述回溯;應保存完整選擇表,或另行證明還原方法。可變的容量前驅指標未必仍代表舊行,不能直接假定它正確。
反例模式
升序遍歷容量會重複使用物件
斷言:容量按升序遍歷時,單陣列更新給出相同的答案。只有一件 ,容量為 時,升序先把 設為 ,再用這個新值更新 ,返回 。同一件被用了兩次,而零一最優值是 。修正方法是降序遍歷,它只讀取舊值。
下面的互動圖以兩種容量次序重播壓縮更新,並把儲存的數值與保留的見證、天真的可變指標及完整表格回溯互相比較。
數值正確,不代表已得到合法子集
逐步重播壓縮 0/1 背包更新,查看讀取的是較小容量狀態的哪個版本,再比較保留歷史的見證與指向可變單元的天真指標。每個物件索引最多出現一次。
已在最後事件。
| 物件索引 | 重量 | 價值 |
|---|---|---|
| 0 | 2 | 4 |
| 1 | 3 | 5 |
| 2 | 4 | 7 |
重播事件 15/15: 完成一個物件的遍歷; 物件索引: 2 (w=4, v=7); 目前容量更新嘗試數: 9.
T 標示剛更新的目標,S 標示較小容量來源。粗邊表示檢查容量,虛線邊表示本次遍歷尚未訪問。來源資料在寫入前擷取。表格逐格列出應對照的完整前綴:本次遍歷已訪問者用新前綴,未訪問者用舊前綴。遍歷完成後全部單元都對應新前綴,包括低於物件重量而保持不變的容量。
| 檢查容量 c | 目前單元值 | 本次物件遍歷已訪問 | 應對照的前綴 | 正確 0/1 參考值 | 單元值符合參考 | 天真的目前容量指標 (檢查容量 c,物件索引) |
|---|---|---|---|---|---|---|
| 0 | 否 | 3 | 0 | 是 | 無 | |
| 0 | 否 | 3 | 0 | 是 | 無 | |
| 4 | 否 | 3 | 4 | 是 | (0,0) | |
| 5 | 否 | 3 | 5 | 是 | (0,1) | |
| 7 | 是 | 3 | 7 | 是 | (0,2) | |
| 9 | 是 | 3 | 9 | 是 | (2,1) |
所檢查容量的見證: c=5; 應對照的前綴: i=3.
歷史清單複製成功更新時讀取的見證。天真指標只記前驅容量與物件,再沿這個快照的目前單元追蹤。即使降序值正確,這些可變指標也未必保留正確版本。可行性與數值吻合是不同檢查;升序清單可符合數值,卻因重用索引而不合法。
| 所檢查容量的見證 | 物件索引,重複會明確顯示 | 重量 | 價值 | 所宣稱數值 | 每個物件索引最多一次 | 容量內的合法 0/1 子集 | 見證價值等於所宣稱數值 |
|---|---|---|---|---|---|---|---|
| 保留歷史的索引 | [0,1] | 5 | 9 | 9 | 是 | 是 | 是 |
| 天真的目前容量指標 | [0,1] | 5 | 9 | 9 | 是 | 是 | 是 |
| 獨立完整表回溯 D_3(5) | [0,1] | 5 | 9 | 9 | 是 | 是 | 是 |
獨立完整 0/1 前綴表
D_i(c) 只容許索引 0 至 i−1,總重至多 c。沒有物件的每個單元都是零。此參考表預先算出全部前綴,不表示重播已完成它們。選取表格單元會改變檢查容量與獨立前綴,重播事件不變。
| i / c | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 0 | ||||||
| 1 | ||||||
| 2 | ||||||
| 3 |
回溯獨立選定單元: D_3(5)=9
相等時略過目前物件;否則選取它,減去其重量,再移到上一前綴。每步都減少 i,因此索引不會重複。剩餘容量不必降至零。
| 獨立完整表前綴 i | 檢查容量 c | 物件索引 | 更新決定 | 此決定後剩餘容量 |
|---|---|---|---|---|
| 3 | 5 | 2 | 保留原單元 | 5 |
| 2 | 5 | 1 | 選目前物件 | 2 |
| 1 | 2 | 0 | 選目前物件 | 0 |
- 目前單元值
- 9
- 應對照的前綴
- 3
- 正確 0/1 參考值
- 9
- 單元值符合參考
- 是
- 保留歷史的索引: 容量內的合法 0/1 子集
- 是
- 保留歷史的索引: 見證價值等於所宣稱數值
- 是
- 天真的目前容量指標: 容量內的合法 0/1 子集
- 是
- 天真的目前容量指標: 見證價值等於所宣稱數值
- 是
教材的三個物件 · 由大至小:保留舊列, W=5; 重播事件 15/15: 完成一個物件的遍歷. c=5: 目前單元值=9, D_3(5)=9; 單元值符合參考: 是. 保留歷史的索引: [0,1], 容量內的合法 0/1 子集: 是, 見證價值等於所宣稱數值: 是. 天真的目前容量指標: [0,1], 容量內的合法 0/1 子集: 是, 見證價值等於所宣稱數值: 是. 獨立完整表回溯: D_3(5)=9, [0,1].
為何順序與見證版本都重要
D_i(c) 是前 i 個物件中總重至多 c 的子集之最佳價值。最優解若略過物件 i−1,得 D_{i−1}(c);若選它一次,在 c≥w 時得 v+D_{i−1}(c−w)。兩分支都使用上一前綴。沒有物件時,空子集在每個容量上都可行,因此 D_0(c) 全為零。這不是恰好裝滿的狀態定義。
降序更新 c 前,大於 c 的容量已是新列,c 與較小容量仍是舊列。重量為正,所以 c−w<c,兩個運算元都保持所需舊前綴意義。小於 w 的容量不變。遍歷結束時數值符合完整 0/1 遞迴。本圖把更新嘗試與快照、參考表的額外工作分開計數。
單一物件(重量 2、價值 3)、容量 4,升序先在容量 2 寫入 3,再於容量 4 讀取它,得到 6 與索引 [0,0]。這不是子集。降序更新容量 4 時讀到容量 2 的舊零值,得到價值 3 與歷史見證 [0]。
只有降序數值正確,仍不能修好天真重建。容量 4 更新記錄使用物件 0 的父指標 4→2,本意是指向舊的零值容量 2。稍後同一遍歷覆寫容量 2,記錄使用物件 0 的 2→0。沿目前指標從 4 出發,就列出價值 6 的 [0,0],儲存數值卻仍正確地是 3。缺少前綴/版本的容量,已不是原本的 DP 狀態。
複製歷史見證會保留當時實際讀取的來源。降序時它們保持合法 0/1 子集,但需要額外儲存與複製成本,不能等同只存值的 O(W+1) 陣列。完整表回溯也保留前綴版本。兩個相同物件 (2,3)、(2,3),容量 2,相等時略過較後物件會得 [0];[1] 也是最優解。屬性相等不會把索引變成同一個。
參考表有 (n+1)(W+1) 個單元,包含初始化,在常數算術成本下做 O((n+1)(W+1)) 單元工作;回溯 O(n)。只求值的壓縮解法保留 O(W+1) 個單元。容量維度由數值 W 決定,不是 W 的二進位位數,因此稱為偽多項式。教學紀錄與複製見證另佔記憶體,本圖並非壓縮解法空間界限的實例。
見證總價值正確,就一定是合法答案嗎?
還須是可用物件的子集,且不超過容量。升序單物件模式的 [0,0] 符合回報值 6,卻非法重用索引。降序的天真指標 [0,0] 不合法,也不符合正確值 3。數值宣稱與見證限制要分開檢查。
至多容量的 0/1 背包,重量為正整數、價值非負,容許空子集。五個固定例子最多三個物件;內核支援最多四個物件、重量 1–8、價值 0–9、容量 0–10。所有數值與計數皆精確。改容量/順序會重建完整紀錄並選最後事件。改重播事件保留獨立表格檢查器。恰好裝滿、可分割物件、零/負重量及最佳化見證儲存不在範圍。
數值大小與輸入長度
常見錯誤
(把偽多項式界當作多項式時間)
狀態有 個,而非只有 個。時間對容量的數值 是多項式,但二進制表示 只需 位元。例如從 增加到 只增加二十位,表格容量維度卻約擴大一百萬倍。因此該算法稱為偽多項式,其操作數並未證明相對於二進制輸入長度的多項式時間。任意大的價值相加也須計入位元成本。
常見錯誤
(把不可能的恰好大小初始化為零)
「至多容量」與「恰好裝滿」不同。恰好大小狀態中,無法達到的大小必須標記為不可能,不能全部初始化成零。例如只有一件大小為二時,恰好大小一無法達到,而至多容量一的最優值是零。
建立恰好裝滿的表
如果要求總大小恰好為 ,定義 為前 件物件中總大小恰好為 的子集的最大價值;用 表示不可能的狀態。沒有物件時只能達到大小零,因此 ,而 時 。當 時,選擇形式仍是
其中約定 ;若 ,便沿用 。證明仍按是否包含第 件劃分,但取走該件後剩餘大小必須恰好是 。這個標記並非某個子集得到的價值:實際實作時,應先判斷前驅是否可能,再做加法。零大小物件仍讀取前一行,因此最多取一次。
例題 2.9.10
(恰好大小可能無法達到)
對於物件 和 ,容量由零至五的各行如下:
| 0 | 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|---|
| 0 | 0 | |||||
| 1 | 0 | 5 | ||||
| 2 | 0 | 5 | 4 | 9 |
其中 不可能:跳過第二件需要不可能的 ,取第二件則需要不可能的 。相比之下,至多容量的答案 ,取大小為二的物件並留下兩個單位空間。恰好大小五時兩件都取,價值為九。求至多容量 時,也可取大小 中可達到的恰好狀態的最大值;不能把不可能狀態當成價值為零的解。
練習與解答
快速檢查
(物件為 、,容量為三。求最優價值和子集。)
列出所有可行子集。
解答 · 答案
兩件一起大小為五,不可行。選第二件,價值五。
快速檢查
(物件為 、、,容量為零。求 ;為甚麼還原仍會終止?)
零大小物件在容量為零時也放得下。
解答 · 答案
兩件零大小物件均可選,價值五;第三件放不下。即使容量不變,還原時行號每步也減少一。
快速檢查
(只有一件 ,容量為二。升序壓縮更新返回甚麼?零一最優值是多少?)
依次追蹤兩次更新。
解答 · 答案
升序先令 ,再令 ,錯誤地重複使用物件。正確值為七。
快速檢查
(只有一件 ,容量為三。比較至多容量與恰好裝滿的答案。)
恰好裝滿的狀態需要一個標記值。
解答 · 答案
至多容量的答案是五,留下一個單位空間;恰好大小三不可能達到,應標記為不可能。
快速檢查
(容量為零且所有大小為正時,算法返回甚麼?考慮空物件表。)
考慮 時哪些子集可行。
解答 · 答案
只有空集可行,答案為零。物件表為空時,第零行就是整個計算。
比較兩個模型時,關鍵是先說明物件能否分割,再核對證明所保護的條件。