iT邦幫忙

2

動態規劃經典題: 01背包問題(knapsack problem)

嗨,大家好,今天要跟大家分享動態規劃問題中的經典問題-
01背包問題

返回主頁: 系列篇章統整: 好好規劃學習動態規劃(Dynamic Programming)

故事是這樣的,有一天,一位小偷成功潛入一戶人家,
看到有很多有價值的東西,
但是小偷的背包容量有限,
每樣東西可以選擇拿或不拿(像是把電腦切一半,把電視折斷,就壞掉了,這是不行的),
請問小偷該怎麼拿可以拿到最多價值的東西呢?

比如說
小偷的背包可以裝9公斤的物品,這些是他搜索到有價值的物品

  • 電冰箱 7公斤 8萬元 (單位價值: 每公斤 1.14萬)
  • 智障型手機 3公斤 3萬元 (單位價值: 每公斤 1萬)
  • XBOX主機 3公斤 3萬元 (單位價值: 每公斤 1萬)
  • 鑲金的小馬玩偶 3公斤 3萬元 (單位價值: 每公斤 1萬)

貪婪法可行嗎?

比如說,這個問題最直覺的想法是,可不可以貪心的拿?
既然背包容量是有限的,
那就單位價值最高的優先拿,
比方說上例小偷看到電冰箱的cp值最高,就先拿電冰箱,
拿完之後就發現背包有一些空間浪費了,
還不如拿「智障型手機」、「XBOX主機」、「鑲金的小馬玩偶」三樣,
恰好把背包裝滿,總價值高於拿電冰箱的價值

動態規劃解法

令物品編號為: 1,2,…,n號,
我們可以定義這樣的一張表格: DP[n][w]
意思是背包容量w單位的前提下,1~n號可以拿到的最高價值

case1: 如果我們不拿第n號物品,則DP[n][w] = DP[n-1][w]
case2: 如果我們拿第n號物品,則DP[n][w] = DP[n-1][w-(n號物品重量)]+ n號物品價值
將case1,case2的答案取最大值就是DP[n][w]要填的值啦

初始值: 當 n=0 或 w=0時,DP[n][w]=0

01背包解題範例

參考題目: zerojudge- b184: 5. 裝貨櫃問題

(註: 本題不需要求哪些物品有放進背包,
不過為了方便知道哪些物品有放進背包,
還是順便求了。)
c++程式碼如下:

#include <iostream>
#include <vector>
using namespace std;

/**解01背包問題,W是背包容量,n是物品數量,wt, val分別是物品的重量(>0)和價值(>0),ans陣列用來記錄哪些物品有放進背包**/
int knapSack(int W, const vector<int> &wt, const vector<int> &val, int n, vector<bool> &ans)
{
    vector<vector<int>> DP(n+1, vector<int>(W+1, 0));

    for (int i = 1; i <= n; i++)
    {
        for (int w = 1; w <= W; w++)
        {
            DP[i][w] = DP[i-1][w];
            if(wt[i-1] <= w)
            {
                DP[i][w] = max(DP[i][w], val[i-1] + DP[i-1][w-wt[i-1]]);
            }
        }
    }

    int j = W;
    /**往回倒推, 求出所有放入的物品*/
    for(int i = n-1; i >= 0; --i)
    {
        //背包可以擁有該物品
        if(j - wt[i] >= 0 && DP[i+1][j] == DP[i][j - wt[i]] + val[i])
        {
            //cout<< "第"<<i<<"個物品有放進背包"<<endl;
            ans[i] = true;
            j -= wt[i];
        }
    }

    return DP[n][W];
}

int main()
{
    int n;
    while(cin >> n)
    {
        vector<int> val(n), wt(n);
        vector<bool> ans(n);
        for(int i = 0; i < n; ++i)
        {
            cin >> wt[i] >> val[i];
        }
        cout << knapSack(100, wt, val, n,ans) <<endl;
    }
    return 0;
}

尚未有邦友留言

立即登入留言