離散資源分配
假設每個項目最多選一次,資源需求 是正整數,價值 非負,可用整數容量 。我們要選取總重量不超過 、總價值最大的項目集合。項目不能拆分時,按單位資源價值排序未必最優。
以下假設有限輸入、整數重量及容量,並用精確運算。數學遞推允許實數價值;下文位元複雜度討論則假設價值是以二進制編碼的非負整數。
定義 3.2.1
(0–1 背包實例與容量表)
一個實例由 件物品及整數容量 組成,第 件的重量是整數 ,價值為 。若 ,則子集 稱為可行。輸出是可行 上 的最大值,以及一個取得此值的可行子集(證據)。
對 及整數 ,令
由於空集總是容許的,最大值是在有限非空的集合族上取的。實例的最優值為 。
狀態記錄哪些項目仍可用
下標 記錄仍可使用哪些物品, 記錄餘下多少容量。空集可行,故 。
定理 3.2.2
(容量遞推)
對每個整數 ,有 ;對 ,
證明
(按是否選第 件劃分可行子集)
固定 及 。 中重量不超過 的子集 恰屬以下兩類之一。若 ,則 且重量不超過 ,所以其價值至多為 。若 ,則 ,而 的重量不超過 ;因此 的價值至多為 。於是 不超過右邊。
反過來,取得 的子集對 可行。當 時,把第 件加入取得 的子集,便得到 中重量不超過 、價值為 的子集。所以右邊可以取得,等式成立。由基礎行出發對 歸納,便證明了每個表項的遞推,即使價值為零或有多個並列集合亦然。
證明透視
為何上一行確保每件最多一次
選第 件後,餘下子問題是 ,不是 。上一行不可能再選第 件;若重用當前行,就允許重複,變成另一個無限件數模型。若只用一個數組,應由大至小更新容量,使 的值仍屬上一階段;由小至大則有同樣重用風險。
這裏使用的兩種容量約定不可混淆。
常見錯誤
(混淆「至多」與「恰好」容量)
基礎行對每個 都設 時, 是重量至多為 的最佳價值,而不是重量恰好為 的最佳價值。在下表中 ,但三件物品的任何子集(連空集在內)都沒有恰好為一的重量。若要計算恰好重量的表,基礎行須取 、對 取 ,遞推不變;此時背包最優值是 ,而不是 。
表格與最優證據
例題 3.2.3
(三件物品的表格及其證據)
重量 、價值 、容量 時,容量 的各行為
在 ,不選第三件得七,選它得 ,所以不選。在 ,選第二件得 ,所以選它並回到 ,再選第一件。證據集合重量 、價值 。若兩項相等,任選一分支均可重構最優解;價值為零時,更不能單憑表值推斷集合唯一。
例題 3.2.4
(永遠放不下或毫無貢獻的物品)
在上一實例後加入第 4 件 及第 5 件 ,容量仍為 。由於對每個 都有 ,遞推只出現第一種情況, 與 逐項相同。實例中最大的價值根本無法取得。
對第 5 件,當 時 。每一行對 都是非遞減的,因為容量較大時可選的子集較多,所以 ,最優值仍是七。在 兩個分支都給出零:不選第 5 件得 ,選它得 。在容量一時 與 都是最優證據;因此在稱重構結果唯一之前,必須先固定平手規則。
例題 3.2.5
(由大至小的單數組掃描)
只保留一個數組 ,由 開始;對每件物品,按 的次序更新 。 的項不變,這正是遞推的第一種情況。
- 第 1 件 :容量 讀到的 都是 ,所以 。
- 第 2 件 : 得 ; 得 ; 得 。現在 。
- 第 3 件 : 得 ; 得 。現在 。
每處理完一件物品,數組都等於表中相應的一行。處理第 2 件、 時,掃描讀到的 尚未被第 2 件改動,所以它仍屬上一階段。
反例模式
單位重量價值貪心可能失敗
容量為四,有三個不同項目 。第一件的比例 大於較小項目的 ,按比例貪心先選它,餘量不足以再選一件,價值為五;兩個較小項目合共重量四、價值六。它們是兩個不同的 0–1 選擇。
算法成本
命題 3.2.6
(填表計算的規模)
完整表可用 次算術運算及 個儲存值填好。由大至小更新的單數組實作以 次運算及 個儲存值求得 。
完整表有 項,每次更新用常數次算術運算及比較,這就證明了兩個界。單數組實作只保留當前一行;重構集合則須保留適當選擇或重算階段。對二進制整數價值,表項不超過輸入價值總和,因此位元長度是輸入長度的多項式;但一次算術運算不自動等於常數次位元運算。
常見錯誤
(把 界稱為多項式時間)
這個界以 的數值計算運算次數。輸入只用約 個位元寫出 ,所以容量 只佔 個位元,表格卻有 列。把 的位元數加倍,可使填表方法的運行時間變為平方。因此這是偽多項式界:它是 與 的數值的多項式,而不是輸入長度的多項式。
練習
快速檢查
(重算 ,並說明所選項目。)
解答 · 答案
不選第三件得 ,選它得 ,故單選第三件。
快速檢查
(只有重量二、價值三的一件物品時,為何單數組由小至大更新會在容量四錯得價值六?)
解答 · 答案
更新容量二為三後,由小至大掃描可在容量四讀到該新值並再次加上同一物品,錯得六。由大至小則讀取上一階段的零。
快速檢查
(按正重量假設, 時最優值是多少?)
解答 · 答案
沒有正重量物品可放入;空集價值零,故最優值為零。
快速檢查
(兩件不同物品的重量和價值都為一,而 。給出兩個不同最優集合。)
解答 · 答案
兩個單件集合均可行且價值為一;兩件同選超過容量,因此兩個單件集合都是最優。平手規則只需回傳其中一個。