优化思路
因为每一个物品都有一个次数限制,所以选取的时候不一定会把背包占满,可能会留有空间
这就导致多重背包不能像完全背包那样进行优化
所以采用一种二进制的方式来进行优化
我觉得更像是一种拆分的思想
比如一个物品能选10次
按照二进制给他拆分成1 2 4,还剩下3也要补上
这样子原来的十次就被拆分成了四堆,每堆的价值和体积分别不同,问题就转换成了01背包
于是可以采用01背包+二进制来对多重背包进行优化
代码实现
//记得将n改成conut
#include <iostream>
using namespace std;
const int N=25000;
int f[N],v[N],w[N];
int n,m;
int main()
{
cin>>n>>m;
int conut=0;
for(int i=1;i<=n;i++)
{
int a,b,c;
cin>>a>>b>>c;
int k=1;
while(c>=k)
{
conut++;
v[conut]=k*a;
w[conut]=k*b;
c-=k;
k*=2;
}
if(c>0)
{
conut++;
w[conut]=c*b;
v[conut]=a*c;
}
}
n=conut;
for(int i=1;i<=n;i++)
for(int j=m;j>=v[i];j--)
f[j]=max(f[j],f[j-v[i]]+w[i]);
cout<<f[m];
}