動機
在 0-1 背包問題中,每個物品有重量和利潤,一個解對每個物品至多選取一次,同時總重量不超過容量。以容量為下標的動態規劃是精確的,但其運行時間可能與一個以二進制編碼的大數成正比。我們可以改為以利潤為下標,並刻意合併相近的利潤。這樣以受控的損失換取一個關於輸入長度和精度參數倒數的多項式規模的狀態空間。
一個看似誘人卻不安全的捷徑,是按所有物品中的最大利潤進行縮放。若該物品比容量還重,它的利潤可能遠大於任何可行解的利潤。此時捨入誤差就是相對於一個與最優值毫無關係的數來衡量的。因此第一步是在選定縮放比例之前先捨棄不可行的物品。
定義
輸入包含 個物品,其重量 與利潤 均為非負整數,以及一個非負整數容量 ,全部以二進制編碼。當 時,子集 稱為可行;其利潤為 。設 為可行子集的最大利潤。對於有理數 ,我們要找一個利潤至少為 的可行子集。
捨棄滿足 的物品。由於重量非負,它們不可能出現在任何可行子集中。捨棄利潤為零的物品對最大化利潤同樣是安全的;包含它們不會改善目標值。若剩餘物品中沒有正利潤物品,則返回空子集。否則剩下 個物品,每個物品單獨都是可行的且利潤為正。設 為它們的最大利潤,則 。
定理
定理 4.5.1
(利潤縮放給出 FPTAS)
對每個這樣的實例和每個有理數 ,下述算法返回一個利潤至少為 的可行子集。其位元運行時間和空間關於二進制輸入長度與 均為多項式。
定理 4.5.2
(精確縮放利潤下的最小重量)
對非負整數縮放利潤 ,定義 為前 個物品中總縮放利潤恰為 的子集的最小重量;若不存在這樣的子集,則取 。於是
其中下標為負的項取 ,初始條件為 ,且當 時 。
證明
算法與動態規劃的證明
令 ,並令 。動態規劃對 以及從零到 的每個 計算上述遞推式。在每個表項處保留一個取到最小值的前驅選擇。取滿足 的最大 ,並沿前驅選擇回溯,得到對應的子集。
證明
(遞推式的正確性)
該遞推式對子集作了窮盡的劃分:一個子集要麼不含物品 ,要麼含有物品 ,且其先前部分的縮放利潤為 。反過來,把物品 加入任何先前的見證子集,都會得到下標互異的有效子集。對 作歸納即可證明每個有限的表項都等於所述的最小值,並且有相應的見證子集。 的情形按常規處理:包含與不包含兩個候選值都引用第 行,因此縮放利潤為零的物品在同一行內不會被重複使用。
在實現中,超過 的重量可用哨兵值 表示,加法在此值處封頂。由於重量非負,一個重量已超過 的部分子集以後永遠不可能變為可行。哨兵表項不必對應某個重量恰為 的真實子集;它只表示尚未儲存任何重量可行的見證子集。所有不超過 的表項都保留有效的見證子集。
近似保證的證明
證明
(近似保證)
設 為一個最優可行子集, 為返回的子集。由於 可行,其縮放總和由某個重量不超過 的表項所表示。算法使可行的縮放總和最大化,因此
對每個物品,。所以
在正利潤分支中,一個單獨可行的正利潤物品保證 非空,因此對各物品的嚴格不等式求和是合理的。返回的子集由所選表項保證可行,所以其真實利潤不可能超過 。當所有可行利潤均為零時,單獨處理的空子集分支恰好是最優的。
證明透視
對真實最優值的下界抵銷了捨入損失
各假設用在哪裏:權重非負,才可以丟棄 的物品,使留下的每個物品單獨可行,從而 。表的最優性只用一次,用來把返回的縮放總值與固定最優解 的縮放總值比較。關鍵一步是雙邊的捨入夾逼 :下側給出 ,上側對 的每個物品損失不到 ,而 至多有 個物品。證明之所以閉合,是因為 ,這正是縮放因子 的取法與界 交會之處。若按一個放不進背包的物品的利潤來縮放,最後一個不等式就會失效。
狀態與位元複雜度
對每個剩餘物品,,故 。因此 。表有 行、至多 列,每個表項只需常數次加法和比較。於是表運算的次數為 ,以 為界。
將 寫成 ,其中 為正整數。計算
時使用精確的整數乘法和除法。這些整數的位元數關於輸入編碼是多項式的。封頂後的重量至多有 的位元長度,而下標 需要 個位元。因此標準整數算術既給出多項式的表運算次數,也給出多項式的位元時間。儲存所有行和前驅選擇只需多項式空間;僅計算數值的話兩行就足夠,但要還原見證子集則需要額外的重構機制。
概念視角算法
把表格看成最短路徑計算
取節點 ,。從節點 到 有一條長度為零的邊,到 有一條長度為 的邊。於是 就是從 到 的最短路徑長度,而每條路徑都記錄了取了哪些物品。這個遞推正是這個分層圖上的最短路徑更新。
例題詳解
例題 4.5.3
(一個小表)
取重量 ,利潤 ,容量 ,以及 。兩個物品單獨都可行,,,。它們的縮放利潤為 。表給出 ,,,。最大的可行縮放總和為二,由第二個物品取得,其真實利潤為四,這也是最優值。
例題 4.5.4
(捨入改變了所選的子集)
取三個重量均為一的物品,利潤為 ,容量為 ,。此時 ,,,縮放利潤為 。縮放總和為三的最小重量見證子集只選第三個物品,其真實利潤為四。選取全部三個物品是可行的,真實利潤為六。該表仍然滿足其保證:它使縮放利潤最大化,並返回了一個可行子集,儘管捨入使它丟掉了一部分原始的正利潤。
例題 4.5.5
(為甚麼要先移除不可行的物品)
設 ,考慮一個重量為一、利潤為二的可行物品,以及一個重量為二、利潤為 的物品。重物品不可能出現在可行子集中。若用它的利潤進行縮放,在精度參數較粗時,可能使該可行物品的捨入利潤變為零。移除它之後,,這是最優值的一個真實下界,近似性的證明便成立。
例題 4.5.6
(零重量與零最優值)
當容量為零時,一個重量為零、利潤為七的物品仍然單獨可行,不得捨棄。動態規劃可以將它包含一次。反之,若所有單獨可行的物品利潤均為零,則空子集的利潤零即為最優值。在該分支中,算法不會除以 。
常見錯誤
反例模式
以錯誤的方向原地更新
一個只有一個物品的實例,重量為一,利潤為一,容量為二,最多容許得到利潤一。若原地遞推立即重用剛為同一物品更新過的表項,就會憑空產生利潤二。應當分開儲存前一行和當前行,或者證明某種更新次序能防止重複使用;雙行遞推使 0-1 約束一目了然。
常見錯誤
(最大化縮放利潤不等於最大化真實利潤)
使縮放利潤最大化並不等同於精確地使真實利潤最大化。該方案透過與最優解的比較,證明了後者的一個下界。特別地,對每個固定的縮放值選取重量較小的見證子集是安全的,因為這保持了該值的可行性;任意選取較重的見證子集,則可能使一個可達的縮放值看起來不可行。
常見錯誤
(把 FPTAS 當作精確的多項式算法)
對 的依賴是結論的一部分。它並非僅關於 的位元長度的多項式。選取指數級小的誤差容限,在緊湊編碼下可能需要指數級的時間,所以 FPTAS 的存在並不意味著二進制編碼的背包問題有精確的多項式時間算法。
理解動態規劃的兩條座標軸
常見的以容量為下標的表,問的是在每個容許的重量下所能達到的最大利潤。本表則把問題反過來:對每個精確的縮放利潤,最小可能的重量是多少?取最小值是正確的概括,因為之後所有物品的重量都非負。對於縮放利潤相同的兩個部分子集,較輕者為任何後續延伸留下的容量都不少於較重者。它們的真實利潤可以不同,但全局的捨入不等式已經考慮了這一差異。
下標表示精確的縮放利潤,而不是「至少為 」的閾值。這一約定使遞推式及其初始化沒有歧義。無法構成的值保持為不可達;絕不能把每個 都初始化為零。最後對所有精確值的掃描,找出其最小重量符合容量的、最好的可達下標。採用閾值語義的表同樣可行,但需要不同的遞推式和證明。
界 是連接數值縮放與相對保證的橋樑。相對地, 給出縮放下標的有限範圍:剩餘的單個利潤都不超過 。這兩個不等式都用到了預處理。它們的用途不同,也都不能僅由對原始、未經過濾的輸入取最大值的定義推出。
在原始實例中驗證輸出
前驅路徑給出一個可審計的原始物品下標列表。要獨立驗證結果,用整數算術將它們的原始重量和利潤相加,檢查沒有重複的下標,並把重量與原始容量比較。因單獨不可行或利潤為零而被捨棄的物品不在見證子集中;在所述的非負重量模型下,這對目標值是安全的。近似性的證明針對的是這個原始利潤,而不是表中報告的縮放總和。
例如,僅憑縮放值十並不能確定唯一的真實利潤。每個被選物品可以貢獻不同的捨入餘數,且被選物品的個數也有影響。這就是證明為甚麼先把縮放後的最優值與一個固定的真實最優解的縮放利潤聯繫起來,再用對其所有餘數的最壞情形界換算回來。它從不假定捨入保持所有子集利潤的大小次序。
若有理精度參數取一,則下界為零,形式上很弱,儘管計算仍可能返回好得多的解。對更小的參數,表隨精度的倒數增大而增大。不存在可行正利潤物品的預處理情形,避免了縮放比例為零這一無意義的情況,並且無需任何近似算術就返回精確答案。
總結
移除單獨不可行以及利潤為零的物品,然後用 縮放其餘利潤。最小重量動態規劃找出最優的可行縮放總和並還原出一個子集。至多 次捨入損失,每次小於 ,合計至多損失最優值的 比例。表的狀態數與位元長度關於輸入和 均為多項式。
練習
快速檢查
(設 ,物品的 為 。取 ,計算 與縮放利潤,並找出一個縮放意義下的最優解。)
先算 ,再算 。
解答 · 答案
兩個物品都可行,故 ,,。縮放利潤為一和二。兩者一起超過容量;單獨取第二個物品具有較大的縮放利潤,其真實利潤為八。
快速檢查
(當 時,為甚麼重量為零且利潤為正的物品不能被捨棄?正確的 0-1 表如何處理它?)
這個物品單獨是否可行?
解答 · 答案
它的重量符合限制且能提高利潤。無論容量是否為零,遞推式都可以從前一行把它包含一次;但它不能在同一行內被重複包含。
快速檢查
(設一個可行實例有 ,剩餘最大利潤 ,且 。求 以及證明中的最大總捨入損失。)
用 與損失界 。
解答 · 答案
。至多五個被選物品,每個損失小於一,所以總損失小於五;這個上界五正好等於 。
快速檢查
(若 ,,物品 的重量為二、縮放利潤為二,計算 。)
比較遞推式中的不取與取兩個候選。
解答 · 答案
不包含的候選值為八,包含的候選值為 。因此 。