思路
考虑到2的10次方为1024>1000,v,w数组均为v[10000],w[10000]
解题思路:3种背包均按01背包处理
1.01背包还是原来方式处理(无需二进制优化存储)
2.完全背包可将其转换成m(m=背包的总体积/该物品的体积)个背包,并用二进制优化存储
3.多重背包按原来方式处理,并用二进制优化存储
ac代码
include[HTML_REMOVED]
using namespace std;
const int N=10000;
int v[N],w[N],f[1010];
int main()
{
int n,m;
cin>>n>>m;
int ans=1;
for(int i=1;i<=n;i)
{
int a,b,c;
cin>>a>>b>>c;
if(c==-1)
{
v[ans]=a;
w[ans]=b;
}
if(c>=0)
{
int l=m/a; //完全背包情况
if(c>0)l=c; //多重背包情况
int p=1;
while(l>=p) //二进制优化
{
v[ans]=ap;
w[ans]=bp;
l=l-p;
p=2;
}
if(l>0)
{
v[ans]=l*a;
w[ans]=lb;
}
}
}
for(int i=1;i<=ans;i++)
{
for(int j=m;j>=v[i];j–)
{
f[j]=max(f[j],f[j-v[i]]+w[i]);
}
}
cout<<f[m];
return 0;
}
这个较好理解,简单来说就是01背包的升级版,仅供参考