詳解PHP怎麼使用動態規劃實現最優紅包組合

#                                                        

最近在做一個小需求，每筆訂單會根據金額決定用戶可以使用的紅包最大值，如果用戶選擇使用紅包，需要幫助用戶從擁有的紅包列表中選取最優的紅包組合，要求組合出的紅包值最接近或等於可以使用的紅包最大值。後面思考了一圈，這不就是 『0-1背包問題』麼，終於可以把以前學過的 『動態規劃』 演算法拿來實戰一下了！

動態規劃是什麼

#動態規劃(Dynamic programming 簡寫：DP)是一種在數學、管理科學、電腦科學、經濟學和生物資訊學中所使用的，透過把原問題分解為相對簡單的子問題的方式來求解複雜問題的方法。

動態規劃常常適用於重疊子問題和最優子結構性質的問題，動態規劃方法所耗時間往往遠少於樸素解法。

動態規劃適用場景

一般使用動態規劃來解決求最優解的問題。在解決問題的過程中需要多次決策，而每次決策都有產生一組狀態，然後從最優的決策中繼續下一次的決策，最終找到最優的結果。

另外動態規劃還具有3個特徵，如下：

最優子結構性質

如果問題的最優解所包含的子問題的解也是最優的，我們就稱問題具有最優子結構性質（即滿足最最佳化原理）。從而我們可以透過子問題的最優解，推導出問題的最優解，也可以理解為後面階段的狀態可以透過前面階段的狀態推導出來。

無後效性

即子問題的解一旦確定，就不再改變，不受在這之後、包含它的更大的問題的求解決策影響。

可以簡單理解為 在推導後面階段狀態的時候，我們只需要關心它前一階段的狀態狀態，不用去關心這個狀態是怎麼一步步推導出來的。第二個意義就是某個階段的狀態一旦確定下來，就不會受之後階段的決策影響。

子問題重疊性質

子問題重疊性質是指在用遞歸演算法自頂向下對問題進行求解時，每次產生的子問題並不總是新問題，有些子問題會被重複計算多次

0-1背包問題

上面的理論比較抽象，和扯犢子一樣的，來看下經典的背包問題。

假設現在有5個物品他們的重量分別是2, 2, 5, 11, 4, 現在有一個背包，能承受的最大重量是10，請選擇合適的物品放入背包，那麼能組合出的物品最大重量是多少?

不同的物品組合會有多種不同的狀態，我們可以使用f(i, w) 來表示一種狀態，其中 i = index 表示第幾個物品，w = weight 表示當前的總重量。

整個問題的解題需要經過 ‘n’ 個階段，每個階段都需要決策一個物品是否放入背包，決策的結果只有2種 ‘放入’ 或 ‘不放入’。在決策完一個物品後，背包中的物品重量會有很多種不同的狀態，我們需要把每一層的 重複狀態 合併，然後只留下不同的狀態。然後基於上一層的狀態結果來推導出下一層的狀態結果。最後全部物品決策完就可以找到最優的組合解。

第0（其實也就是第一個物品，依照習慣從0開始下標吧）個物品的重量是2，然後開始決策是否放入背包，結果只有2種。如果放入背包那麼此時背包的重量就是2，如果不放入背包那麼背包的重量就是0.記作$status[0][0] = true; 和$status [0][2] = true; 和上面的f(i, w) 一樣，前一位表示物品，後一位表示重量。

第1個物品的重量還是2，然後開始對他決策，決策只有2種選擇放入背包或不放入背包，但是它的狀態組合卻多了，因為它要基於之前的背包狀態來判斷當前的狀態。對第1個物品完成決策後會有3個狀態(其實是4個狀態，不過有1個重複的就不算了 還是算3個不同的狀態)。

如果決策目前物品放入背包,第0個物品不放入背包，此時的狀態是$status[1][2 0] = true; => $status[1][2 ] = true;
如果決策目前物品放入背包,第0個物品也放入背包，此時的狀態是$status[1][2 2] = true; => $status[1][4] = true;

如果決策目前物品不放入背包,第0個物品不放入背包，此時的狀態是$status[1 ][0 0] = true; => $status[1][0] = true;
如果決策當前物品不放入背包,而第0個物品放入背包，此時的狀態是$status[1][0 2] = true; => $status[1][2] = true;

其中$status[1][2 ] 是重複的，所有會產生3種結果。

後面的物品也是以此類推，直到對所有的物品都決策完，整個狀態的陣列就都找出來了，然後只需要在最後一層找到一個值為true的最接近最大值(上面的例子中是10)的值就是背包能承受的最大值。然後可以從最後依序往前推就可以找出對應的物品下標，也就是哪些物品的組合是這個最優解組合了。

推導過程如下圖：

#其實在上面的推導過程中就是動態規劃的解題思路。把問題分解為多個階段，每個階段對應一種策略。然後記錄下每個階段的狀態（注意要去掉重複項），然後透過目前狀態的可能推導出下一個階段的所有狀態可能，動態的推導下去。

PHP實作偽代碼：

function dynamicKnapsack($arr, $n, $max){
    // 初始化二维数组
    $status = [];
    for ($i = 0; $i = 0; $j--) {
        if ($status[$n - 1][$j] == true) {
            break;
        }
    }
    for ($i = $n - 1; $i >= 1; $i--) { // 外层遍历行
        if ($j - $arr[$i] >= 0 && $status[$i - 1][$j - $arr[$i]] == 1) {
            var_dump('buy this product: '.$arr[$i]);
            $best[] = $i;
            $j = $j - $arr[$i];
        }
    }
    if ($j != 0) {
        var_dump('buy first product:'.$arr[0]);
        $best[] = 0;
    }
    return $best;}// 测试数据$arr = [
    2, 2, 5, 11, 4,];$n = 5;$max = 10;$best = dynamicKnapsack($arr, $n, $max);var_dump($best);

如果求的結果是11，得到的結果是4, 5, 2 的組合，你可能會有疑問不是還有11這個結果麼，剛好它一個就滿足了不是麼。我覺得這應該是看實際的需求。例如我這次的需求是把紅包按過期時間排序，快過期的優先使用，然後我在組裝數據的時候按過期時間順序強行把快過期的紅包放到數組最後面拼成數組，那最後的4就是最接近快過期的紅包了，我要優先消耗掉這個紅包，如果使用了4那11就不能使用了，只能繼續去前面找，就是這麼回事！

總結

這段程式碼的時間複雜度是多少? 耗時最多的部分是中間的嵌套2層循環，所有時間複雜度是O(n*max)，其中n 表示物品的個數，max表示最大的承重。

空間複雜度是一開始申請的陣列空間O(n*max 1) 加上計算結果的累加有可能出現O(n*2*max) 的情況，空間消耗還是很高的。

整體來說這是一種空間換時間的想法。另外在中間決策的嵌套迴圈裡如果使用j從小到大遍歷的話會出現for迴圈重複計算的問題。

建議學習：《PHP影片教學》                              

以上是詳解PHP怎麼使用動態規劃實現最優紅包組合的詳細內容。更多資訊請關注PHP中文網其他相關文章！