多重背包1dp

多重背包1

有 N 种物品和一个容量是 V的背包。
第 i种物品最多有 si 件，每件体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。
接下来有 N行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i种物品的体积、价值和数量。
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤100
0<vi,wi,si≤100

输入样例

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

输出样例：

10

分析：
多重背包是说每个物品可以选择s次。

状态表示
f(j)表示背包容量不超过j时候的最大价值
这样的话状态转移
对于第i个物品，有s+1种决策:选择0个，选择1个，选择2个，一直到选择s个。
如果选择0个：相当于f(j)
如果选择1个：相当于 f(j-v)+w
如果选择2个：相当于 f(j-2v)+2w
…
如果选择s个：相当于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++)//状态转移需要一层循环f[j]=max(f[j],f[j-k*v[i]]+k*w[i]);}}

这里的问题：枚举背包容量的时候应该从小到大枚举还是从大到小枚举？
这就要看状态转移需要的是i-1层的数据，还是第i层的数据。
如果需要第i-1层的数据，需要从大到小枚举，对应的是01背包f(i,j)=max(f(i-1,j),f(i-1,j-v)+w)。
如果需要第i层更新过的数据，需要从小到大枚举，对应的是完全背包f(i,j)=max(f(i-1,j),f(i,j-v)+w)
这里第i-1层数据还是第i层数据指的是max里面第二个f，即是f(i-1,j-v)+w还是f(i,j-v)+w,如果是f(i-1,j-v)+w，则表示第i-1层的数据，如果是f(i,j-v)+w，则表示第i层数据。

对于多重背包
我们稍微分析一下，f(i,j)，如果第i个选一个，那么第i个物品是确定的(体积和价值，背包容量减去v，价值+w)，只需要考虑第i-1个物品，则是f[i-1][j-v[i]]+w[i] ，对应的是第i-1层的数据，故和01背包相似，背包容量从大到小枚举！

复杂度分析
复杂度$O(n^3)$,未优化

题目数据100以内，可以过。

acwing网站上ac代码

#include<iostream> #include<cstring> #include<algorithm> using namespace std; const int maxn=110; int n,m,v[maxn],w[maxn],s[maxn];//分别表示 重量，价值和物品数量 int f[maxn];//状态数组：f[j]表示背包容量≤j时候的最大价值 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; }

总结

以上是生活随笔为你收集整理的多重背包1dp的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。