您當(dāng)前位置：首頁 > php開源 > php教程 > 0-1背包問題與分?jǐn)?shù)背包問題

0-1背包問題與分?jǐn)?shù)背包問題

來源：程序員人生發(fā)布時(shí)間：2015-08-24 08:22:04 閱讀次數(shù)：8256次

0⑴背包問題與分?jǐn)?shù)背包問題
- 問題描寫
- 問題分析之分?jǐn)?shù)背包
- 代碼設(shè)計(jì)之分?jǐn)?shù)背包問題
- 問題分析之0⑴背包問題
- 代碼設(shè)計(jì)之0⑴背包問題
- 動態(tài)計(jì)劃算法之間的差別

0⑴背包問題與分?jǐn)?shù)背包問題

我們在文章《貪心算法原理》:http://blog.csdn.net/ii1245712564/article/details/45369491中提到過動態(tài)計(jì)劃和貪心算法的區(qū)分。和兩個(gè)經(jīng)典的例子：0⑴背包問題和分?jǐn)?shù)背包問題，我么知道0⑴背包問題是不能夠使用貪心算法求解的，而貪心算法則是分?jǐn)?shù)背包問題的不2之選。
這次我們來側(cè)重實(shí)現(xiàn)1下0⑴背包問題的動態(tài)計(jì)劃解法和分?jǐn)?shù)背包問題的貪心算法。

問題描寫

0⑴背包問題：我們有1堆物品 $S=lbrace a_1,a_2,...,a_n brace$ ,每個(gè)物品 $a_i$ 都有1個(gè)重量 $w_i$ 和1個(gè)價(jià)值 $v_i$ .現(xiàn)在有1個(gè)背包，這個(gè)背包的容量為 $W$ ,現(xiàn)在要將這些物品在不超越背包容量的情況下選擇性的放入背包，使得背包里面物品的價(jià)值最大，物品不能只選取其中1部份，必須選擇全部，或不選！

分?jǐn)?shù)背包問題：這個(gè)問題和上面的問題比較類似，唯1不同的就是該問題里面的物品可以進(jìn)行分割，便可以只選取1個(gè)物品 $a_i$ 的1部份

這里我們采取例子：

我們有3個(gè)物品和1個(gè)容量為 $50$ 的背包，這3個(gè)物品<重量,價(jià)值>分別為: $a1<10,60>,a2<20,100>,a3<30,120>$ .

問題分析之分?jǐn)?shù)背包

為簡單期間，我們首先來分析1下分?jǐn)?shù)背包問題。如果要設(shè)計(jì)1個(gè)貪心算法，那末首先要肯定1個(gè)貪心策略，換句話說就是要怎樣在當(dāng)前的情況下做出1個(gè)公道的貪心選擇。
我們首先得到每個(gè)物品單位重量的價(jià)值 $v_i/w_i$ ,那末我們要設(shè)計(jì)1個(gè)貪心策略來使得裝入背包物品的價(jià)值最大。我們的第1直覺肯定是要選擇單位重量價(jià)格最高的嘍，然后再選擇物品里面第2高的，1次類推直到裝滿背包為止！

下面我們來證明1下上面貪心選擇的料想：

證明:

我們首先假定我們有1個(gè)最優(yōu)解 $A_1$ ,那末我們首先找到 $A_1$ 里面平均價(jià)值最高的物品 $a_m$ ，讓后我們將用商品里面平均價(jià)值最高的物品 $a_1$ 將 $a_m$ 進(jìn)行全部替換或部份替換得到解 $A_2$ ，又因 $v_1/w_1 geq v_m/w_m$ 所以 $A_2$ 的總價(jià)值高于 $A_1$ 的總價(jià)值，這 $A_1$ 是最優(yōu)解矛盾，因而得到 $A_1$ 里面包括平均價(jià)值最高的物品。

因而我們得到最優(yōu)子結(jié)構(gòu) $S_i = S_k +a_k$ ， $a_k$ 是 $S_i$ 里面平均價(jià)值最高的， $S_k$ 是選擇 $a_k$ 剩下來的物品。

代碼設(shè)計(jì)之分?jǐn)?shù)背包問題

依照我們上面描寫的分?jǐn)?shù)背包問題的最好貪心策略，每次都選出平均價(jià)值最高的物品

/*************************************************
* @Filename:    fractionPackage.cc
* @Author:      qeesung
* @Email:       qeesung@qq.com
* @DateTime:    2015-04⑶0 14:44:28
* @Version:     1.0
* @Description: 貪心策略，分?jǐn)?shù)背包問題
**************************************************/

#include <iostream>
#include <utility>
#include <vector>

using namespace std;

#define PACKAGE_CAPACITY 50

/**
 * 求得goodslist對應(yīng)的最大價(jià)值,我們首先假定物品依照平均價(jià)值降序排序
 * @param  goodsList 商品列表
 * @return           最大價(jià)值
 */
unsigned fractionPackage(std::vector<pair<unsigned , unsigned> > goodsList)
{
    unsigned valueSum=0;
    unsigned capacitySum=0;
    for (int i = 0; i < goodsList.size(); ++i)
    {
        // 轉(zhuǎn)完這次就退出
        if(goodsList[i].second + capacitySum >= PACKAGE_CAPACITY)
        {
            valueSum+=(PACKAGE_CAPACITY - capacitySum)*(goodsList[i].first/goodsList[i].second);
            return valueSum;
        }
        valueSum+=goodsList[i].first;
        capacitySum+=goodsList[i].second;
    }
    return valueSum;
}

int main(int argc, char const *argv[])
{
    std::vector<pair<unsigned , unsigned> > goodsList;
    goodsList.push_back(pair<unsigned , unsigned>(60,10));
    goodsList.push_back(pair<unsigned , unsigned>(100,20));
    goodsList.push_back(pair<unsigned , unsigned>(120,30));
    cout<<"max value is : "<<fractionPackage(goodsList)<<endl;
    while(1);
    return 0;
}

運(yùn)行結(jié)果為:

max value is 240

我們這里首先選擇平均價(jià)值最高的a1放入背包，然后放入a2,由于此時(shí)a3不能全部放入背包，因而我們放入a3的1部份進(jìn)入到背包。這里也很好理解，那就是我們在物品總能裝滿背包的情況下，背包總是可以被裝滿的，我們?nèi)绻箍們r(jià)值最高，那我們就應(yīng)當(dāng)提升平均的價(jià)值密度，那就把平均價(jià)值最高的順次放入背包！

問題分析之0⑴背包問題

為何我們不能用貪心算法來解決0⑴背包問題呢，我們只需要舉1個(gè)反例就能夠了，我們還是依照之前的將平均價(jià)值最大的放入背包里面，放入 $a_1$ ,然后 $a_2$ , $a_3$ 已不能再放入了，因而我們得到背包物品總價(jià)值為 $60+100=160$ ，但是這個(gè)是最優(yōu)解么？肯定不是,由于只放入 $a_2$ 和 $a_3$ 總價(jià)值就到達(dá) $100+120=220$ ,所以這里我們只能另辟蹊徑。
每個(gè)物品只有兩種選擇，那就是放入背包與不放入背包。所以我們要做的就是決定1個(gè)物品是放入還是不放入背包。
在求解動態(tài)計(jì)劃問題中，我們首先要做的,就是找到最優(yōu)子結(jié)構(gòu)和遞歸表達(dá)式。因而我們假定 $f(i,W)$ 為有<