在貪婪演算法下, 若制定好貪婪準則, 並且在貪婪準則下作出抉擇之後, 無法對其結果進行更改, 即抉擇作出後無法撤回. 在動態規劃中, 我們需要考察一系列抉擇, 以確定一個最佳的抉擇序列下, 所有子序列都是最佳抉擇序列

以 0/1 背包問題為例. 設有 n 個物品和一個容量為 c 的背包, n 個物品的重量為 w_{1}, w_{2}, ..., w_{n}, 價值為 p_{1}, p_{2}, ..., p_{n}. 我們按照物品的順序確定第 i 個物品是否裝入背包. 若選擇 x_{1} = 1, 則問題轉化為剩餘 n - 1 個物品和裝載容量為 c - w_{1} 的 0/1 背包子問題. 若選擇 x_{1} = 0, 則問題轉化為剩餘 n - 1 個物品和裝載容量為 c 的 0/1 背包子問題

在作出一次選擇之後, 這一次選擇將會規定接下來的問題狀態. 不論 x_{1} = 0 還是 x_{1} = 1, \left \{ x_{2}, x_{3}, ..., x_{n} \right \} 都必須是這個問題的最佳解. 否則, 會存在一個更好的選擇 \left \{ y_{2}, y_{3}, ..., y_{n} \right \}

若我們需要作出最佳抉擇, 而最佳抉擇包含最佳抉擇子序列時, 可以通過建立動態規劃遞迴方程式來幫助我們求解

對於 0/1 背包問題而言, 通過上述描述, 我們可以建立以下遞迴方程式. 記 T_{i}\ (i = 1, 2, ..., n - 1) 為子序列裝在之後的價值, 那麼有

T_{n} = \begin {cases} p_{n} & (x_{n} = 1) \\ 0 & {x_{n} = 0} \end {cases}, T_{i} = \begin {cases} p_{i} + T_{i + 1} & {x_{i} = 1} \\ T_{i + 1} & {x_{i} = 0} \end {cases}

上述遞迴方程式需要我們主動對 x_{i} 的值作出抉擇, 當我們未作出抉擇時, 計算無法繼續進行. 動態規劃遞迴方程式可以幫助我們作出抉擇. 設 f(i, y) 表示在背包的剩餘容量為 y 的情況下, 剩餘物品 x_{i}, x_{i + 1}, ..., x_{n} 所形成的 0/1 背包子問題的最佳解對應的價值總量. 那麼當 i = n 的時候, 有

f(n, y) = \begin {cases} p_{n} & {y \geq w_{n}} \\ 0 & {0 \leq y < w_{n}} \end {cases} \ \ \ \ \ \ \ \ \ \ (I)

1 \leq i < n 時,

  1. 0 \leq y < w_{i}, 此時背包無法容納第 i 個物品, 故必有

    f(i, y) = f(i + 1, y)

  2. y \geq w_{i}, 有且唯有兩種情況 :
    • x_{i} = 1, 則

      f(i, y) = f(i + 1, y - w_{i}) + p_{i}

    • x_{i} = 0, 則

      f(i, y) = f(i + 1, y)

    就目前而言, 我們暫時無法確定 x_{i} 的值, 它和 x_{i + 1}, x_{i + 2}, ..., x_{n} 的值無關, 但是它會影響 x_{1}, x_{2}, ..., x_{i - 1} 的值. 由於我們需要得到價值最高的裝載, 那麼若 y \geq w_{i} 時, 有

    f(i, y) = \max \left \{ f(i + 1, y), f(i + 1, y - w_{i} + p_{i} \right \}

綜上所述, 當 1 \leq i < n 時, 有

f(i, y) = \begin {cases} \max \left \{ f(i + 1, y), f(i + 1, y - w_{i}) + p_{i} \right \} & {y \geq w_{i}} \\ f(i + 1, y) & {0 \leq y < w_{i}} \end {cases}\ \ \ \ \ \ \ \ \ \ (II)

方程式 (I)(II) 共同組成了 0/1 背包問題的動態規劃遞迴方程式

例 1. 令 n = 3, w = \left \{100, 14, 10 \right \}, p = \left \{20, 18, 15 \right \}, c = 116. 要得到這個 0/1 背包問題的最佳解, 實際上是要求 f(1, 116) 的值

:

由於 w_{1} \leq 116, 故有

f(1, 116) = \max \left \{ f(2, 116), f(2, 16) + 20 \right \}

以此類推 :

f(2, 116) = \max \left \{ f(3, 116), f(3, 102) + 18 \right \}

f(3, 116) = p_{3} = 15

f(3, 102) + 18 = p_{3} + 18 = 33

因此, f(2, 116) = f(3, 102) + 18 = 33. 而

f(2, 16) + 20 = \max \left \{ f(3, 2) + 18, f(3, 16) \right \} + 20

f(3, 2) + 18 = 0 + 18 = 18

f(3, 16) = p_{3} = 15

那麼, f(2, 16) + 20 = 18 + 20 = 38. 於是

f(1, 116) = f(2, 16) + 20 = 38

此時, \mathscr {X} = \left \{ x_{1}, x_{2}, x_{3} \right \} = \left \{ 1, 1, 0 \right \}. 目標函數 f(\mathscr {X}) = \sum \limits_{i = 1}^{n}x_{i}p_{i} = 38

綜上所述, 我們得到了該例下的最佳解 \mathscr {X} = \left \{ 1, 1, 0 \right \}

上述例題僅有三個物品, 對於 x_{i} 的值無需太多思考便可以得到. 其中, i = 1, 2, 3. 在物品較多的情況下, x_{i} (i = , 1, 2..., n) 的值計算如下 : 若 f(1, c) = f(2, c), 則 x_{1} = 0; 否則, x_{1} = 1. 因為我們使用容量為 c 的背包裝在剩餘 n - 1 個物品, 說明第 1 個物品並未被放入背包. 若 x_{1} = 1, 則剩餘容量為 c - w_{1}. 接著比較 f(2, c - w_{1})f(3, c - w_{1}) 的值; 若 x_{1} = 0, 則比較 f(2, c)f(3, c) 的值...

從上述分析中, 我們可以得到 : 無論目前的選擇是什麼, 接下來的選擇一定是當前問題狀態下的最佳解, 我們稱此為最佳原則. 最佳原則意味著最佳抉擇序列必定由最佳抉擇子序列構成

對於 0/1 背包問題來說, 觀察其動態規劃遞迴方程式 :

f(n, y) = \begin {cases} p_{n} & {y \geq w_{n}} \\ 0 & {0 \leq y < w_{n}} \end {cases}, \\ f(i, y) = \begin {cases} \max \left \{ f(i + 1, y), f(i + 1, y - w_{i}) + p_{i} \right \} & {y \geq w_{i}} \\ f(i + 1, y) & {0 \leq y < w_{i}} \end {cases}

實際上, 我們已經得到了使用動態規劃演算法來求解 0/1 背包問題的程式碼 :

#include <algorithm>

int solve(int capacity, int *weight, int *profit, int size, int i = 1) {
    if(i == size - 1) {
        return capacity < weight[i] ? 0 : profit[1];
    }
    if(capacity < weight[i]) {
        return solve(capacity, weight, profit, size, i + 1);
    }
    return std::max(solve(capacity, weight, profit, size, i + 1), solve(capacity - weight[i], weight, profit, size, i + 1) + profit[i]);
}

這個程式碼的時間複雜度分析並不採用分而治之演算法所採用的方法, 雖然動態規劃的思想可能和分而治之的思想有一些相似. 我們可以直接通過解動態規劃的遞迴方程式, 就可以得到其時間複雜度 O(2^{n}). 這比我們當時介紹的貪婪演算法下的啟發式演算法的時間複雜度 O(n^{k}) 要高得多. 因此, 我們需要對程式碼進行一些優化. 如果我們完全沒有多餘的空間可用於保存計算結果, 那麼上述程式碼就是最佳的解決方案. 否則, 我們可以通過保存計算結果來提升時間. 這是因為上述程式碼中, 存在著大量的重複計算

對於任意問題, 使用動態規劃演算法求解的過程如下 :

  1. 證實問題確實可以運用動態規劃演算法
  2. 建立動態規劃遞迴方程式
  3. 求解動態規劃遞迴方程式以得到最佳解
  4. 沿著最佳解生成的過程可以獲得全部信息
  5. 編寫程式碼並分析時間複雜度, 在可能的情況下對程式碼進行優化