国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

王者編程大賽之三 — 01背包

Cympros / 2657人閱讀

摘要:動態規劃概念動態規劃過程每次決策依賴于當前狀態,又隨即引起狀態的轉移。相關文章王者編程大賽之一王者編程大賽之二蓄水池王者編程大賽之四約瑟夫環王者編程大賽之五最短路徑

首發于 樊浩柏科學院

服務目前每月會對搬家師傅進行評級,根據師傅的評級排名結果,我們將優先保證最優師傅的全天訂單。

假設師傅每天工作 8 個小時,給定一天 n 個訂單,每個訂單其占用時間長為 $T_i$,掙取價值為 $V_i$,現請您為師傅安排訂單,并保證師傅掙取價值最大。

輸入格式
輸入 n 組數據,每組以逗號分隔,并且每一個訂單的編號、時長、掙取價值以空格分隔
輸出格式
輸出爭取價值和訂單編號,訂單編號按照價值由大到小排序,爭取價值相同,則按照每小時平均爭取價值由大到小排序

示例:
輸入:[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

解題思路

由于本題每個訂單每天只被安排一次,是典型地采用 動態規劃 求解的 01 背包問題。

動態規劃概念

動態規劃過程:每次決策依賴于當前狀態,又隨即引起狀態的轉移。一個決策序列就是在變化的狀態中產生出來的,所以,這種多階段最優化決策解決問題的過程就稱為動態規劃。

動態規劃原理:動態規劃與分治法類似,都是把原問題拆分成不同規模相同特征的小問題,通過尋找特定的遞推關系,先解決一個個小問題,最終達到解決原問題的效果。

建立動態方程

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

可得訂單價值和耗時的關系圖:

i 1 2 3 4 5
w(i) 2 2 1 6 3
v(i) 100 30 200 500 400

因此,可得 動態方程:

$$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}$$

說明:$j 確定邊界

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

求解

求解過程,可以填表來進行模擬:

1) 如 i=1,j=1 時,有 $j2) 又如 i=1,j=2 時,有 $j=w(i)$,故 $wx(1,2) = max(wx(1-1,1), wx(1-1,2-w(1)) + v(1) = 100$;
3) 如此下去,直至填到最后一個,i=5,j=8 時,有 $j4) 在耗時沒有超過 8 小時的前提下,當前 5 個訂單都被安排過時,$wx(5,8) = 730$ 即為所求的最大價值;

解的組成

盡管 求解 過程已經求出了最大價值,但是并沒有得出哪些訂單被安排了,也就是沒有得出解的組成部分。

但是在求解的過程中不難發現,尋解方程滿足如下定義:

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

從表格右下到左上為尋解方向,尋解過程如下:

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

編碼實現

實現的類結構如下,特殊的方法已提取出,并將一一詳細說明。

class Knapsack
{
    //物品重量,index從1開始表示第1個物品
    public $w = array();
    //物品價值,index從1開始表示第1個物品
    public $v = array();
    //最大價值,$wv[$i][$w]表示前i個物品重量為w時的最大價值
    public $wv = array();
    //物品總數
    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);
        //初始化物品價值
        $v = array_column($goods, 2);
        array_unshift($v, 0);
        $this->v = $v;
        //初始化物品重量
        $w = array_column($goods, 1);
        array_unshift($w, 0);
        $this->w = $w;
        //初始化最大價值
        $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];
    }
}

動態求解過程:

public function pd()
{
    for ($i = 0; $i <= $this->W; $i++) {
        for ($j = 0; $j <= $this->n; $j++) {
            //未放入物品和重量為空時,價值為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]);
            }
        }
    }
}

尋解過程:

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

        //背包質量為c時,前i-1個和前i-1個物品價值不變,表示第1個物品未放入
        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];
        }
    }
}

按照訂單價值降序獲取訂單信息(若訂單價值相同則按單位時間平均價值降序排列):

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;
}

接收標準輸入處理并輸出結果:

$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;
總結

該題使用動態規劃求解,算法的時間復雜度為 $O(nc)$,當然也可以采用其他方式求解。例如先將訂單按照價值排序,然后依次嘗試進行安排訂單,直至剩余耗時不能再被安排訂單。

有關動態規劃的其他典型應用,請參考 常見的動態規劃問題分析與求解 一文。

相關文章 ?

王者編程大賽之一(2017-12-05)

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

王者編程大賽之四 — 約瑟夫環(2017-12-06)

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

文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。

轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/31075.html

相關文章

  • 王者編程大賽之五 — 最短路徑

    摘要:由于是從頂點到的最短路徑,則有。算法流程根據最短路徑的最優子結構性質,提出了以最短路徑長度遞增,逐次生成最短路徑的算法。相關文章王者編程大賽之一王者編程大賽之二蓄水池王者編程大賽之三背包王者編程大賽之四約瑟夫環 首發于 樊浩柏科學院 自如年底就會擁有 50W 間房子,大家知道每間房房子都是需要配置完才能出租給自如客的,整個房租的配置過程是很復雜的,每天都需要大量的物流師傅將家電、家具...

    yuanzhanghu 評論0 收藏0
  • 王者編程大賽之一

    摘要:首發于樊浩柏科學院本次王者編程大賽分為個組別,分別為研發測試移動戰場。本章只敘述前道相對簡單的題目,后續題目及解題思路將在王者編程大賽系列中列出。 首發于 樊浩柏科學院 本次王者編程大賽分為 3 個組別,分別為研發、測試、移動戰場。這里只討論研發戰場所考的 題目,本次大賽共有 7 道題,主要考查點為基礎算法,解題所用語言不做限制,但是需要在 在線驗證平臺 使用標準輸入并驗證通過,最后...

    justCoding 評論0 收藏0
  • 王者編程大賽之二 — 蓄水池

    摘要:相關文章王者編程大賽之一王者編程大賽之三背包王者編程大賽之四約瑟夫環王者編程大賽之五最短路徑 首發于 樊浩柏科學院 自如寓打算門口用磚頭圍立一個蓄水池子,從上面看凹凸不平,凹的地方會有積水。那如果用數字代表每個磚頭的高度,就形成一個二維數據(如示例),請問這個池子能存儲多少單位的水?showImg(https://segmentfault.com/img/remote/1460000...

    Me_Kun 評論0 收藏0
  • 背包問題學習筆記

    摘要:狀態轉移方程背包問題的狀態轉移方程是其中即表示前件物品恰放入一個容量為的背包可以獲得的最大價值。求解將哪些物品裝入背包可使這些物品的體積總和不超過背包容量,且價值總和最大。 01背包 01背包的概念 有N件物品和一個容量為V的背包。第i件物品的費用是c[i],價值是w[i]。求解將哪些物品裝入背包可使價值總和最大。從這個題目中可以看出,01背包的特點就是:每種物品僅有一件,可以選擇放或...

    xiao7cn 評論0 收藏0
  • 經典動態規劃--01背包問題

    摘要:背包問題具體例子假設現有容量的背包,另外有個物品,分別為,,。最后,就是動態規劃的思路了。而前個物體放入容量為的背包,又可以轉化成前個物體放入背包的問題。 背包問題具體例子:假設現有容量10kg的背包,另外有3個物品,分別為a1,a2,a3。物品a1重量為3kg,價值為4;物品a2重量為4kg,價值為5;物品a3重量為5kg,價值為6。將哪些物品放入背包可使得背包中的總價值最大? 首先...

    warkiz 評論0 收藏0

發表評論

0條評論

Cympros

|高級講師

TA的文章

閱讀更多
最新活動
閱讀需要支付1元查看
<