摘要訊息 : 使用貪婪演算法近似地解 0/1 背包問題.

0. 前言

在《貪婪演算法》中我們介紹了 NP 問題的實用定義, 本篇文章我們將介紹另外一個著名的 NP 問題, 即 0/1 背包問題.

本文在 2022 年 5 月 17 日进行一次更新和修正. 修正之后本文已经归档, 不再享受更新.

1. 0/1 背包問題

有 n 個物品和一個容量為 c 的背包, 從 n 個物品中選取裝包的物品, 第 i 件物品的重量為 w_{i}. 價值為 p_{i} (i = 1, 2, ..., n). 一個可行的背包裝載是裝包物品的總重量不超過背包的容量的 c. 一個最佳背包裝載是指物品的總價值最高的可行背包裝載方案.

根據題目描述可知, 目標函數為 f(\mathscr {X}) = f(x_{1}, x_{2}, ..., x_{n}) = \sum \limits_{i = 1}^{n}x_{i}p_{i}, 限制條件為 \sum \limits_{i = 1}^{n}x_{i}w_{i} \leq c. 只要符合限制條件的解均為可行解, 能使得目標函數 f 取得最大值的解為最佳解. 其中, x_{i} = \begin {cases} 0 & {\text {第 } i \text { 個物品不被放入背包}} \\ 1 & {\text {第 } i \text { 個物品被放入背包}} \end {cases}, i = 1, 2, ..., n.

可能的貪婪策略為 :

1. 從剩餘物品中選擇價值最大的物品放入背包;
2. 從剩餘物品中選擇重量最小的物品放入背包;
3. 價值密度 \frac {p_{i}}{w_{i}} (i = 1, 2, ..., n) 法則 : 從剩餘物品中選擇價值密度較大的物品放入背包;
4. 隨機選擇物品放入背包;
5. ...

現在我們採用貪婪策略 3. 但是在多種變數的影響下, 價值密度法則並不能保證一定能夠得到最佳解. 更多情況下, 使用價值密度法則為貪婪準則的貪婪演算法得到的解是可以接近最佳解的. 根據啟發式演算法的定義, 選擇價值密度法則作為貪婪準則的貪婪演算法可以被稱為啟發式演算法. 那麼是否存在這樣一個 p (0 \leq p \leq 1), 使得啟發式演算法得到的解與最佳解相差在 p 之內呢? 其中, 設 \mathscr {X} = \left \{ x_{1}, x_{2}, ..., x_{n} \right \} 是最佳解, \mathscr {Y} = \left \{ y_{1}, y_{2}, y_{n} \right \} 是啟發式演算法得到的解. 對於 p, 有 \displaystyle {p = \frac {\sum \limits_{i = 1}^{n}x_{i}p_{i} - \sum \limits_{i = 1}^{n}y_{i}p_{i}} {\sum \limits_{i = 1}^{n}x_{i}p_{i}}}. 如果你無法判定, 那麼不妨嘗試尋找一個否定的實例. 考慮 n = 2, \mathscr {W} = \left \{ 1, y \right \}, \mathscr {P} = \left \{ 10, 9y \right \}, c = y. 其中, y 為任意常數. 此時, \frac {p_{1}}{w_{1}} = 10, \frac {p_{2}}{w_{2}} = 9, 則使用啟發式演算法得到的解為 \mathscr {Y} = \left \{ 1, 0 \right \}. 當 y \geq \frac {10}{9}, 最佳解 \mathscr {X} = \left \{ 0, 1 \right \}. 故 p = \frac {9y - 10}{9y}, 令 p \to +\infty, 考慮極限 \displaystyle {\lim \limits_{y \to +\infty} \frac {9y - 10}{9y} = 1}. 顯然, |p - 1| 越小, 策略越不可用, 因為啟發式演算法得到的解和最佳解的差距越來越大. 此時, 需要修改啟發式演算法 : 設最多有 k 件物品放入背包 (0 \leq k \leq n). 若 \sum \limits_{i = 1}^{k}x_{i}w_{i} > c, 則放棄這個解; 否則, 按照順序容量將剩餘物品按 \frac {p_{i}}{w_{i}} (i = 1, 2, ..., n) 的遞減順序放入背包. 考慮所有可能的解 \mathbb {Y} = \left \{ \mathscr {Y}_{1}, \mathscr {Y}_{2}, ..., \mathscr {Y}_{j} \right \}. 其中, 0 \leq \mathop {\mathrm {card}} \mathscr {Y}_{i} \leq n (i = 1, 2, ..., n). 從 \mathbb {Y} 中選擇一個解, 滿足 |p - 1| 最大, 從而使得解的結果與最佳解相差在 p 之內.

例題 1. 設 n = 4, \mathscr {W} = \left \{2, 4, 6, 7 \right \}, \mathscr {P} = \left \{ 6, 10, 12, 13 \right \}, c = 11.

解 :

使用修改之前的啟發式演算法, 得到的解 \mathscr {Z} = \left \{ 1, 1, 0, 0 \right \}, f(\mathscr {Z}) = 16. 接著, 我們使用修改後的啟發式演算法求解.

當 k = 1 時, 考慮將一件物品放入背包, 可選的物品有 x_{1}, x_{2}, x_{3}, x_{4}. 當 x_{1} = 1 或 x_{2} = 1 時, 產生的結果與價值密度貪婪準則一樣. 考慮 x_{3} = 1, 此時背包剩餘容量為 5, 僅有 x_{1} 和 x_{2} 可以放入背包, 選擇價值密度較小的 x_{1} 放入背包得到的解為 \mathscr {Y}_{1} = \left \{ 1, 0, 0, 1 \right \}, 此時 f(\mathscr {Y}_{1}) = 19. 除此之外, 其餘解都是當 k = 1 時的不可行解.

當 k = 2 時, 可選的物品有 \left \{ x_{1}, x_{2} \right \}, \left \{ x_{2}, x_{3} \right \}, \left \{ x_{1}, x_{4} \right \}, \left \{ x_{2}, x_{3} \right \}, \left \{ x_{2}, x_{4} \right \}, \left \{ x_{3}, x_{4} \right \}. 排除已經考慮過的 \left \{ x_{1}, x_{2} \right \}, \left \{ x_{1}, x_{3} \right \}, \left \{ x_{1}, x_{4} \right \} 還有不可行的 \left \{ x_{2}, x_{4} \right \}. 還剩下 \left \{ x_{2}, x_{3} \right \} 和 \left \{ x_{2}, x_{4} \right \}. 考慮 x_{2} = 1, x_{3} = 1, 此時背包剩餘容量為 1, 不能再放入任何物品, 因此得到解 \mathscr {Y}_{2} = \left \{ 0, 1, 1, 0 \right \}, f(\mathscr {Y}_{2}) = 22. 考慮 x_{2} = 1, x_{4} = 1, 此時背包容量為 0, 不能再放入任何物品, 得到解 \mathscr {Y}_{3} = \left \{ 0, 1, 0, 1 \right \}, f(\mathscr {Y}_{3}) = 23.

當 k = 3 或者 k = 4, 物品的總重量已經超過 c, 不歸入可行解.

綜上所述, 選擇 \mathscr {Y}_{3} 作為修改後啟發式演算法的解.

\blacksquare

稱修改後的啟發式演算法稱為 k 階優化. 將這種啟發式演算法稱為有界性能啟發式演算法. 這種演算法所得到的解在最佳解的 \frac {1}{k + 1} 之內. 有界性能啟發式演算法的運作時間隨著 k 值的增大而增大, 需要嘗試的子集數目為 O(k^{n}), 每一個子集所用的時間為 \Theta(n - k). 設物品排序的時間為 \Theta(n\log {n}), 當 k > 0 時, 總的時間複雜度為 O(n^{k + 1}).