PHP怎么使用動(dòng)態(tài)規(guī)劃實(shí)現(xiàn)最優(yōu)紅包組合

這篇文章主要介紹“PHP怎么使用動(dòng)態(tài)規(guī)劃實(shí)現(xiàn)最優(yōu)紅包組合”，在日常操作中，相信很多人在PHP怎么使用動(dòng)態(tài)規(guī)劃實(shí)現(xiàn)最優(yōu)紅包組合問(wèn)題上存在疑惑，小編查閱了各式資料，整理出簡(jiǎn)單好用的操作方法，希望對(duì)大家解答”P(pán)HP怎么使用動(dòng)態(tài)規(guī)劃實(shí)現(xiàn)最優(yōu)紅包組合”的疑惑有所幫助！接下來(lái)，請(qǐng)跟著小編一起來(lái)學(xué)習(xí)吧！

動(dòng)態(tài)規(guī)劃是什么

動(dòng)態(tài)規(guī)劃 (Dynamic programming 簡(jiǎn)寫(xiě)：DP)是一種在數(shù)學(xué)、管理科學(xué)、計(jì)算機(jī)科學(xué)、經(jīng)濟(jì)學(xué)和生物信息學(xué)中使用的，通過(guò)把原問(wèn)題分解為相對(duì)簡(jiǎn)單的子問(wèn)題的方式求解復(fù)雜問(wèn)題的方法。

動(dòng)態(tài)規(guī)劃常常適用于有重疊子問(wèn)題和最優(yōu)子結(jié)構(gòu)性質(zhì)的問(wèn)題，動(dòng)態(tài)規(guī)劃方法所耗時(shí)間往往遠(yuǎn)少于樸素解法。

動(dòng)態(tài)規(guī)劃適用場(chǎng)景

一般使用動(dòng)態(tài)規(guī)劃來(lái)解決求最優(yōu)解的問(wèn)題。在解決問(wèn)題的過(guò)程中需要多次決策，而每次決策都有產(chǎn)生一組狀態(tài)，然后從最優(yōu)的決策中繼續(xù)下一次的決策，最終找到最優(yōu)的結(jié)果。

另外動(dòng)態(tài)規(guī)劃還具有3個(gè)特征，如下：

最優(yōu)子結(jié)構(gòu)性質(zhì)

如果問(wèn)題的最優(yōu)解所包含的子問(wèn)題的解也是最優(yōu)的，我們就稱(chēng)該問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)（即滿(mǎn)足最優(yōu)化原理）。從而我們可以通過(guò)子問(wèn)題的最優(yōu)解，推導(dǎo)出問(wèn)題的最優(yōu)解，也可以理解為后面階段的狀態(tài)可以通過(guò)前面階段的狀態(tài)推導(dǎo)出來(lái)。

無(wú)后效性

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

可以簡(jiǎn)單理解為 在推導(dǎo)后面階段狀態(tài)的時(shí)候，我們只需要關(guān)心它前一階段的狀態(tài)狀態(tài)，不用去關(guān)心這個(gè)狀態(tài)是怎么一步步推導(dǎo)出來(lái)的。第二個(gè)含義就是某個(gè)階段的狀態(tài)一旦確定下來(lái)，就不會(huì)受之后階段的決策影響。

子問(wèn)題重疊性質(zhì)

子問(wèn)題重疊性質(zhì)是指在用遞歸算法自頂向下對(duì)問(wèn)題進(jìn)行求解時(shí)，每次產(chǎn)生的子問(wèn)題并不總是新問(wèn)題，有些子問(wèn)題會(huì)被重復(fù)計(jì)算多次

0-1背包問(wèn)題

上面的理論比較抽象，和扯犢子一樣的，來(lái)看下經(jīng)典的背包問(wèn)題。

假設(shè)現(xiàn)在有5個(gè)物品他們的重量分別是 2, 2, 5, 11, 4, 現(xiàn)在有一個(gè)背包，能承受的最大重量是 10，請(qǐng)選擇合適的物品放入背包，那么能組合出的物品最大重量是多少?

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

整個(gè)問(wèn)題的求解需要經(jīng)過(guò) 『n』 個(gè)階段，每個(gè)階段都需要決策一個(gè)物品是否放入背包，決策的結(jié)果只有2種 『放入』 或者 『不放入』。在決策完一個(gè)物品后，背包中的物品重量會(huì)有很多種不同的狀態(tài)，我們需要把每一層的 重復(fù)狀態(tài) 合并，然后只留下不同的狀態(tài)。然后基于上一層的狀態(tài)結(jié)果來(lái)推導(dǎo)出下一層的狀態(tài)結(jié)果。最終全部物品決策完就可以找到最優(yōu)的組合解。

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

第1個(gè)物品的重量還是2，然后開(kāi)始對(duì)他決策，決策只有2種選擇 放入背包 或者 不放入背包，但是它的狀態(tài)組合卻多了，因?yàn)樗谥暗谋嘲鼱顟B(tài)來(lái)判斷當(dāng)前的狀態(tài)。對(duì)第1個(gè)物品完成決策后會(huì)有3個(gè)狀態(tài)(其實(shí)是4個(gè)狀態(tài)，不過(guò)有1個(gè)重復(fù)的就不算了 還是算3個(gè)不同的狀態(tài))。

如果決策當(dāng)前物品放入背包,第0個(gè)物品不放入背包，此時(shí)的狀態(tài)是 $status[1][2 + 0] = true; => $status[1][2] = true;
如果決策當(dāng)前物品放入背包,第0個(gè)物品也放入背包，此時(shí)的狀態(tài)是 $status[1][2 + 2] = true; => $status[1][4] = true;

如果決策當(dāng)前物品不放入背包,第0個(gè)物品不放入背包，此時(shí)的狀態(tài)是 $status[1][0 + 0] = true; => $status[1][0] = true;
如果決策當(dāng)前物品不放入背包,而第0個(gè)物品放入背包，此時(shí)的狀態(tài)是 $status[1][0 + 2] = true; => $status[1][2] = true;

其中 $status[1][2] 是重復(fù)的，所有會(huì)產(chǎn)生3種結(jié)果。

后面的物品也是以此類(lèi)推，直到對(duì)所有的物品都決策完，整個(gè)狀態(tài)的數(shù)組就都找出來(lái)了，然后只需要在最后一層找到一個(gè)值為true的最接近最大值(上面的例子中是10)的值就是背包能承受的最大值。然后可以從最后依次往前推就可以找出對(duì)應(yīng)的物品下標(biāo)，也就是哪些物品的組合是這個(gè)最優(yōu)解組合了。

推導(dǎo)過(guò)程如下圖：

實(shí)際上在上面的推導(dǎo)過(guò)程中就是動(dòng)態(tài)規(guī)劃的解題思路。把問(wèn)題分解為多個(gè)階段，每個(gè)階段對(duì)應(yīng)一種策略。然后記錄下每個(gè)階段的狀態(tài)（注意要去掉重復(fù)項(xiàng)），然后通過(guò)當(dāng)前狀態(tài)的可能推導(dǎo)出下一個(gè)階段的所有狀態(tài)可能，動(dòng)態(tài)的推導(dǎo)下去。

PHP實(shí)現(xiàn)偽代碼：

function dynamicKnapsack($arr, $n, $max){
    // 初始化二維數(shù)組
    $status = [];
    for ($i = 0; $i < $n; $i++) {
        // max + 1 才能有max的值 因?yàn)橄聵?biāo)從0開(kāi)始的
        for ($j = 0; $j < $max + 1; $j++) {
            $status[$i][$j] = 0;
        }
    }
    // 第一個(gè)物品特殊處理
    // 對(duì)第一個(gè)物品決策不放入
    $status[0][0] = 1;
    // 對(duì)第一個(gè)物品決策放入
    if ($arr[0] <= $max) {
        $status[0][$arr[0]] = 1;
    }

    // 開(kāi)始動(dòng)態(tài)規(guī)劃進(jìn)行決策 -- 外層是物品
    for ($i = 1; $i < $n; $i++) {
        // 決策放入背包
        for ($j = 0; $j < $max + 1; $j++) {
            // 找到他上一層的組合，在上一層的基礎(chǔ)上變更當(dāng)前層的結(jié)果
            if ($status[$i - 1][$j] == 1) {
                $status[$i][$j + $arr[$i]] = 1;
            }
        }
        // 決策不放入背包
        for ($j = 0; $j < $max + 1; $j++) {
            // 找到上一層的組合直接取上一層的值
            if ($status[$i - 1][$j] == 1) {
                // $status[$i][$j] = 1; 等價(jià)于下面
                $status[$i][$j] = $status[$i - 1][$j];
            }
        }
    }
    // 尋找最優(yōu)組合
    $best = [];
    $j = 0;
    // 為了找到尋找最優(yōu)解的開(kāi)始位置
    // 也就是當(dāng)前能組合出的最大值是多少
    // 最后一行是最大的組合，它包含了所有都放入的結(jié)果
    // 最終確定了j開(kāi)始的位置
    for ($j = $max; $j >= 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;}// 測(cè)試數(shù)據(jù)$arr = [
    2, 2, 5, 11, 4,];$n = 5;$max = 10;$best = dynamicKnapsack($arr, $n, $max);var_dump($best);

如果求的結(jié)果是 11，得出的結(jié)果是 4, 5, 2 的組合，你可能會(huì)有疑問(wèn)不是還有11這個(gè)結(jié)果么，剛好它一個(gè)就滿(mǎn)足了不是么。我覺(jué)得這個(gè)應(yīng)該是看實(shí)際的需求。比如我這次的需求是把紅包按過(guò)期時(shí)間排序，快過(guò)期的優(yōu)先使用，然后我在組裝數(shù)據(jù)的時(shí)候按過(guò)期時(shí)間順序強(qiáng)行把快過(guò)期的紅包放到數(shù)組最后面拼成數(shù)組，那最后的4就是最接近快過(guò)期的紅包了，我要優(yōu)先消耗掉這個(gè)紅包，如果使用了4那11就不能使用了，只能繼續(xù)去前面找，就是這么回事！

總結(jié)

這段代碼的時(shí)間復(fù)雜度是多少? 耗時(shí)最多的部分是中間的嵌套2層循環(huán)，所有時(shí)間復(fù)雜度是 O(n*max)，其中 n 表示物品的個(gè)數(shù)，max表示最大的承重。

空間復(fù)雜度是一開(kāi)始申請(qǐng)的數(shù)組空間 O(n*max+1) 加上計(jì)算結(jié)果的累加有可能出現(xiàn) O(n*2*max) 的情況，空間消耗還是很高的。

總體來(lái)說(shuō)這是一種空間換時(shí)間的思路。另外在中間決策的嵌套循環(huán)里如果使用j從小到大遍歷的話(huà)會(huì)出現(xiàn)for循環(huán)重復(fù)計(jì)算的問(wèn)題。

到此，關(guān)于“PHP怎么使用動(dòng)態(tài)規(guī)劃實(shí)現(xiàn)最優(yōu)紅包組合”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實(shí)踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識(shí)，請(qǐng)繼續(xù)關(guān)注億速云網(wǎng)站，小編會(huì)繼續(xù)努力為大家?guī)?lái)更多實(shí)用的文章！