多重背包1

有 N 種物品和一個(gè)容量是 V的背包。
第 i種物品最多有 si 件，每件體積是 vi，價(jià)值是 wi。
求解將哪些物品裝入背包，可使物品體積總和不超過背包容量，且價(jià)值總和最大。
輸出最大價(jià)值。
輸入格式
第一行兩個(gè)整數(shù)，N，V，用空格隔開，分別表示物品種數(shù)和背包容積。
接下來(lái)有 N行，每行三個(gè)整數(shù) vi,wi,si，用空格隔開，分別表示第 i種物品的體積、價(jià)值和數(shù)量。
輸出格式
輸出一個(gè)整數(shù)，表示最大價(jià)值。
數(shù)據(jù)范圍
0<N,V≤100
0<vi,wi,si≤100

輸入樣例

4 5 1 2 3 2 4 1 3 4 3 4 5 2

輸出樣例：

10

分析：
多重背包是說每個(gè)物品可以選擇s次。

狀態(tài)表示
f(j)表示背包容量不超過j時(shí)候的最大價(jià)值
這樣的話狀態(tài)轉(zhuǎn)移
對(duì)于第i個(gè)物品，有s+1種決策:選擇0個(gè)，選擇1個(gè)，選擇2個(gè)，一直到選擇s個(gè)。
如果選擇0個(gè)：相當(dāng)于f(j)
如果選擇1個(gè)：相當(dāng)于 f(j-v)+w
如果選擇2個(gè)：相當(dāng)于 f(j-2v)+2w
…
如果選擇s個(gè)：相當(dāng)于f(j-sv)+sw

然后在上述決策中取最大值。

$f[j]=max(f[j],f[j?v]+w,f[j?2v]+2w,...,f[j?sv]+sw)$,s表示物品最多選擇s次

for(int i=1;i<=n;i++){//枚舉物品for(int j=m;j>=v[i];j--){//枚舉背包容量for(int k=1;k<=s&&k*v[i]<=j;k++)//狀態(tài)轉(zhuǎn)移需要一層循環(huán)f[j]=max(f[j],f[j-k*v[i]]+k*w[i]);}}

這里的問題：枚舉背包容量的時(shí)候應(yīng)該從小到大枚舉還是從大到小枚舉？
這就要看狀態(tài)轉(zhuǎn)移需要的是i-1層的數(shù)據(jù)，還是第i層的數(shù)據(jù)。
如果需要第i-1層的數(shù)據(jù)，需要從大到小枚舉，對(duì)應(yīng)的是01背包f(i,j)=max(f(i-1,j),f(i-1,j-v)+w)。
如果需要第i層更新過的數(shù)據(jù)，需要從小到大枚舉，對(duì)應(yīng)的是完全背包f(i,j)=max(f(i-1,j),f(i,j-v)+w)
這里第i-1層數(shù)據(jù)還是第i層數(shù)據(jù)指的是max里面第二個(gè)f，即是f(i-1,j-v)+w還是f(i,j-v)+w,如果是f(i-1,j-v)+w，則表示第i-1層的數(shù)據(jù)，如果是f(i,j-v)+w，則表示第i層數(shù)據(jù)。

對(duì)于多重背包
我們稍微分析一下，f(i,j)，如果第i個(gè)選一個(gè)，那么第i個(gè)物品是確定的(體積和價(jià)值，背包容量減去v，價(jià)值+w)，只需要考慮第i-1個(gè)物品，則是f[i-1][j-v[i]]+w[i] ，對(duì)應(yīng)的是第i-1層的數(shù)據(jù)，故和01背包相似，背包容量從大到小枚舉！

復(fù)雜度分析
復(fù)雜度$O(n^3)$,未優(yōu)化

題目數(shù)據(jù)100以內(nèi)，可以過。

acwing網(wǎng)站上ac代碼

#include<iostream> #include<cstring> #include<algorithm> using namespace std; const int maxn=110; int n,m,v[maxn],w[maxn],s[maxn];//分別表示 重量，價(jià)值和物品數(shù)量 int f[maxn];//狀態(tài)數(shù)組：f[j]表示背包容量≤j時(shí)候的最大價(jià)值 int main(){cin>>n>>m;for(int i=1;i<=n;i++){cin>>v[i]>>w[i]>>s[i];}memset(f,0,sizeof(f));for(int i=1;i<=n;i++){for(int j=m;j>=v[i];j--){//背包容量從大到小枚舉for(int k=1;k<=s[i]&&k*v[i]<=j;k++)f[j]=max(f[j],f[j-k*v[i]]+k*w[i]);}}cout<<f[m]<<endl;return 0; }

總結(jié)

以上是生活随笔為你收集整理的多重背包1dp的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。