摘要：動(dòng)態(tài)規(guī)劃概念動(dòng)態(tài)規(guī)劃過(guò)程每次決策依賴于當(dāng)前狀態(tài)，又隨即引起狀態(tài)的轉(zhuǎn)移。相關(guān)文章王者編程大賽之一王者編程大賽之二蓄水池王者編程大賽之四約瑟夫環(huán)王者編程大賽之五最短路徑

首發(fā)于 樊浩柏科學(xué)院

服務(wù)目前每月會(huì)對(duì)搬家?guī)煾颠M(jìn)行評(píng)級(jí)，根據(jù)師傅的評(píng)級(jí)排名結(jié)果，我們將優(yōu)先保證最優(yōu)師傅的全天訂單。

假設(shè)師傅每天工作 8 個(gè)小時(shí)，給定一天 n 個(gè)訂單，每個(gè)訂單其占用時(shí)間長(zhǎng)為 $T_i$，掙取價(jià)值為 $V_i$，現(xiàn)請(qǐng)您為師傅安排訂單，并保證師傅掙取價(jià)值最大。

輸入格式
輸入 n 組數(shù)據(jù)，每組以逗號(hào)分隔，并且每一個(gè)訂單的編號(hào)、時(shí)長(zhǎng)、掙取價(jià)值以空格分隔
輸出格式
輸出爭(zhēng)取價(jià)值和訂單編號(hào)，訂單編號(hào)按照價(jià)值由大到小排序，爭(zhēng)取價(jià)值相同，則按照每小時(shí)平均爭(zhēng)取價(jià)值由大到小排序

示例：
輸入：[MV10001 2 100,MV10008 2 30,MV10003 1 200,MV10009 6 500,MV10010 3 400]
輸出：730 MV10010 MV10003 MV10001 MV10008
輸入：[M10001 2 100,M10002 3 210,M10003 3 300,M10004 2 150,M10005 1 70,M10006 2 220,M10007 1 10,M10008 3 30,M10009 3 200,M10010 2 400]
輸出：990 M10010 M10003 M10006 M10005

由于本題每個(gè)訂單每天只被安排一次，是典型地采用 動(dòng)態(tài)規(guī)劃 求解的 01 背包問(wèn)題。

動(dòng)態(tài)規(guī)劃過(guò)程：每次決策依賴于當(dāng)前狀態(tài)，又隨即引起狀態(tài)的轉(zhuǎn)移。一個(gè)決策序列就是在變化的狀態(tài)中產(chǎn)生出來(lái)的，所以，這種多階段最優(yōu)化決策解決問(wèn)題的過(guò)程就稱為動(dòng)態(tài)規(guī)劃。

動(dòng)態(tài)規(guī)劃原理：動(dòng)態(tài)規(guī)劃與分治法類似，都是把原問(wèn)題拆分成不同規(guī)模相同特征的小問(wèn)題，通過(guò)尋找特定的遞推關(guān)系，先解決一個(gè)個(gè)小問(wèn)題，最終達(dá)到解決原問(wèn)題的效果。

假設(shè)，師傅掙取價(jià)值最大時(shí)的訂單為 $x_1$,$x_2$,$x_3$,...,$x_i$（其中 $x_i$ 取 1 或 0，表示第 i 個(gè)訂單被安排或者不安排），$v_i$ 表示第 i 個(gè)訂單的價(jià)值，$w_i$ 表示第 i 個(gè)訂單的耗時(shí)時(shí)長(zhǎng)，$wv(i,j)$ 表示安排了第 i 個(gè)訂單，師傅總耗時(shí)為 j 時(shí)的最大價(jià)值。

可得訂單價(jià)值和耗時(shí)的關(guān)系圖：

因此，可得 動(dòng)態(tài)方程：

$$wv(i,j) = begin{cases}
wv(i-1,j)(j < w(i))
max(wx(i-1,j),wv(i-1,j-w(i))+v(i))(j geq w(i))
end{cases}$$

說(shuō)明：$j 確定邊界

可以確定邊界條件 $wx(0,j) = wx(i, 0) = 0$，$wx(0,j)$ 表示一個(gè)訂單都沒(méi)安排，再怎么耗時(shí)價(jià)值都為 0，$wx(i,0)$ 表示沒(méi)有耗時(shí)，安排多少訂單價(jià)值都為 0。

求解過(guò)程，可以填表來(lái)進(jìn)行模擬：

1) 如 i=1,j=1 時(shí)，有 $j2) 又如 i=1,j=2 時(shí)，有 $j=w(i)$，故 $wx(1,2) = max(wx(1-1,1), wx(1-1,2-w(1)) + v(1) = 100$；
3) 如此下去，直至填到最后一個(gè)，i=5,j=8 時(shí)，有 $j4) 在耗時(shí)沒(méi)有超過(guò) 8 小時(shí)的前提下，當(dāng)前 5 個(gè)訂單都被安排過(guò)時(shí)，$wx(5,8) = 730$ 即為所求的最大價(jià)值；

盡管 求解 過(guò)程已經(jīng)求出了最大價(jià)值，但是并沒(méi)有得出哪些訂單被安排了，也就是沒(méi)有得出解的組成部分。

但是在求解的過(guò)程中不難發(fā)現(xiàn)，尋解方程滿足如下定義：

$$x(i) = begin{cases}
wv(i,j) = wv(i-1,j)
wv(i,j) neq wv(i-1,j)
end{cases}$$

從表格右下到左上為尋解方向，尋解過(guò)程如下：

1) i=5,j=8 時(shí)，有 $wv(5,8) != wv(4,8)$，故 $x(5) = 1$，此時(shí) $j -= w(5)$，$j = 5$；
2) i=4 時(shí)，無(wú)論 j 取何值，都有 $wv(4,j) == wv(3,j)$，故 $x(5) = 0$，此時(shí) $j = 5$；
3) i=3,j=5 時(shí)，有 $wv(3,5) != wv(2,5)$，故 $x(3) = 1$，此時(shí) $j -= w(3)$，$j = 4$；
4) i=2,j=4時(shí)，有 $wv(2,4) != wv(1,4)$，故 $x(2) = 1$，此時(shí) $j -= w(2)$，$j = 2$；
5) i=1,j=2時(shí)，有 $wv(1,2) != wv(1,2)$，故 $x(1) = 1$，此時(shí) $j -= w(1)$，$j = 0$，尋解結(jié)束；

實(shí)現(xiàn)的類結(jié)構(gòu)如下，特殊的方法已提取出，并將一一詳細(xì)說(shuō)明。

class Knapsack
{
    //物品重量,index從1開(kāi)始表示第1個(gè)物品
    public $w = array();
    //物品價(jià)值,index從1開(kāi)始表示第1個(gè)物品
    public $v = array();
    //最大價(jià)值,$wv[$i][$w]表示前i個(gè)物品重量為w時(shí)的最大價(jià)值
    public $wv = array();
    //物品總數(shù)
    public $n = 0;
    //物品總重量
    public $W = 0;
    //背包中的物品
    public $goods = array();

    /**
     * Knapsack constructor.
     * @param array $goods 物品信息,格式如下:
     * [
     *   [index, w, v]   //good1
     *   ...
     * ]
     * @param $c
     */
    public function __construct(array $goods, $c)
    {
        $this->goods = $goods;

        $this->W = $c;
        $this->n = count($goods);
        //初始化物品價(jià)值
        $v = array_column($goods, 2);
        array_unshift($v, 0);
        $this->v = $v;
        //初始化物品重量
        $w = array_column($goods, 1);
        array_unshift($w, 0);
        $this->w = $w;
        //初始化最大價(jià)值
        $this->wv = array_fill(0, $this->n + 1, array_fill(0, $this->W + 1, 0));

        $this->pd();
        $this->canPut();
    }

    public function getMaxPrice()
    {
        return $this->wv[$this->n][$this->W];
    }
}

動(dòng)態(tài)求解過(guò)程：

public function pd()
{
    for ($i = 0; $i <= $this->W; $i++) {
        for ($j = 0; $j <= $this->n; $j++) {
            //未放入物品和重量為空時(shí),價(jià)值為0
            if ($i == 0 || $j == 0) {
                continue;
            }

            //決策
            if ($i < $this->w[$j]) {
                $this->wv[$j][$i] = $this->wv[$j - 1][$i];
            } else {
                $this->wv[$j][$i] = max($this->wv[$j - 1][$i], $this->wv[$j - 1][$i - $this->w[$j]] + $this->v[$j]);
            }
        }
    }
}

尋解過(guò)程：

public function canPut()
{
    $c = $this->W;
    for ($i = $this->n; $i > 0; $i--) {

        //背包質(zhì)量為c時(shí),前i-1個(gè)和前i-1個(gè)物品價(jià)值不變,表示第1個(gè)物品未放入
        if ($this->wv[$i][$c] == $this->wv[$i - 1][$c]) {
            $this->goods[$i - 1][3] = 0;
        } else {
            $this->goods[$i - 1][3] = 1;
            $c = $c - $this->w[$i];
        }
    }
}

按照訂單價(jià)值降序獲取訂單信息（若訂單價(jià)值相同則按單位時(shí)間平均價(jià)值降序排列）：

public function getGoods()
{
    $filter = function($value) {
        return $value[3];
    };
    $goods = array_filter($this->goods, $filter);
    usort($goods, function($a, $b) {
        if ($a[2] == $b[2]) {
            if ($a[2] / $a[1] < $b[2] / $b[1]) {
                return 1;
            }
            return 0;
        }
        return $a[2] < $b[2];
    });

    return $goods;
}

接收標(biāo)準(zhǔn)輸入處理并輸出結(jié)果：

$arr = explode(",", $input);
$filter = function ($value) {
    return explode(" ", $value);
};

$knapsack = new Knapsack(array_map($filter, $arr), 8);
$goods = $knapsack->getGoods();

echo $knapsack->getMaxPrice(), " ", implode(" ", array_column($goods, 0)), PHP_EOL;

該題使用動(dòng)態(tài)規(guī)劃求解，算法的時(shí)間復(fù)雜度為 $O(nc)$，當(dāng)然也可以采用其他方式求解。例如先將訂單按照價(jià)值排序，然后依次嘗試進(jìn)行安排訂單，直至剩余耗時(shí)不能再被安排訂單。

有關(guān)動(dòng)態(tài)規(guī)劃的其他典型應(yīng)用，請(qǐng)參考 常見(jiàn)的動(dòng)態(tài)規(guī)劃問(wèn)題分析與求解 一文。

相關(guān)文章 ?

王者編程大賽之一（2017-12-05）

王者編程大賽之二 — 蓄水池 （2017-12-05）

王者編程大賽之四 — 約瑟夫環(huán)（2017-12-06）

王者編程大賽之五 — 最短路徑（2017-12-06）