2012年2月11日 星期六

Knapsack Problem(背包問題)

Knapsack Problem(背包問題)
這裡以在有限體積下, 物品總價值最高
考慮的是夠不夠放進去, 假設不夠那就是不能放進去, 價值也就保持一樣
若可以放進去, 考慮放進去的價值會不會比不放進去的價值高
可分物品是否重複
1.物品無重複下, 每一物品最多就是放一個或不放
ex:有一背包總重100
當 V[100]現在最大價值 = 10, 若有一個物重為8, 且價值為4
若V[100-8]的價值加上4 > V[100]的價值, 就update!!
可參考:背包問題(重複拿)
練習:zerojudge的b131b184d637

二維寫法:
#include <iostream>
using namespace std;
int DP[10001][101]={0};
int main()
{
    int n, s[10000], v[10000];  //假設有10000個物品
    cin >> n;
    for(int i = 0; i < n; i++)
        cin >> s[i] >> v[i];
    for(int i = 0; i < n; i++)
        for(int j = 0; j <= 100; j++)   //總背重為100
            if(j-s[i] < 0)  DP[i+1][j] = DP[i][j];  //當目前背重-目前物重<0, 放不下, 維持不變就是說不要放進來
            else    DP[i+1][j] = max(DP[i][j], DP[i][j-s[i]]+v[i]); //有足夠空間可放, 但要比較放上去價值是否會比較高
    cout << DP[n][100] << endl;
    return 0;
}

可用一維來寫, 記憶體相對較少, 因為我們每次是看上一個物品考慮放或不放完的結果
但用一維要從後面寫回來, 原因是若前面寫過來, 會把原本資料蓋過去
ex:
假設有一總背重為5, 現在有一物品物重2 價值7, 下列是0~5價值
                  0 1 2 3 4 5
                  0 4 4 5 5 5
當從前面過來時, 2會變為7, 往下跑到4時會變成V[4] = V[2]+7 = 14, 這是錯誤的!!
因為這樣就重複拿了, 因此要從後面寫回去也就是V[4] = V[2]+7 = 4+7 = 11, 才是正確的

一維寫法:
#include <iostream>
using namespace std;
int main()
{
    int n, s, v, DP[101]={0};
    cin >> n;
    while(n--){
        cin >> s >> v;
        //ex:DP[100]=10, DP[92] = 8, 當有物重為8, 且價值高於2, 即更新
        for(int i = 100; i-s >= 0; i--) //從後面往回跑, 確保總重-物重>0
            DP[i] = max(DP[i], DP[i-s]+v);  //去比較原本價值較高, 或減掉該物重時重量價值+現在價值較高
    }
    cout << DP[100] << endl;
    return 0;
}
2.物品重複下, 可拿很多個亦或都不拿
那就很類似零錢問題了, 直接看程式碼
#include <iostream>
using namespace std;
int main()
{
    int s[5], v[5], DP[11]={0};
    for(int i = 0; i < 5; i++)
        cin >> s[i] >> v[i];
    for(int i = 0; i < 5; i++)
        for(int j = s[i]; j <= 10; j++)
            DP[j] = max(DP[j], DP[j-s[i]]+v[i]);
    cout << DP[10] << endl;
    return 0;
}

6 則留言:

  1. http://hoyusun.blogspot.com/2012/02/knapsack-problem.html
    0 1 2 3 4 5 (weight)
    0 4 4 5 5 5 (value)

    用一維要從後面寫回來, 原因是若前面寫過來, 會把原本資料蓋過去 能解释一下?而且我没看到value 等于7的物品啊?

    回覆刪除
  2. dp[i] i表示剩余容量时的转移方程 和
    dp[i] i表示使用容量时的转移方程 是不一样的
    which one are you trying to say?

    回覆刪除
  3. actually i got it now. thanks for the great post

    回覆刪除
  4. 如果从前面写的话你会重复放同一个物品。比如哪个例子来说DP[4] = DP[2]+7 where DP[2]= 7. 你重复放 同一个物品。是吗?

    回覆刪除
    回覆
    1. 是的。
      如你取零錢取最大意思相同

      刪除
  5. http://pastebin.com/8vD5utRL << i'm not sure this will work?

    回覆刪除