#include<bits/stdc++.h>
using namespace std;
int main()
{
int N,V,v[1001],w[1001],dp[2001],s[1001]
int a[25000],b[25000]; //2的12次方大于2000，也就是说一个数最多可以拆成12个，故数组容量乘12
cin>>N>>V;
memset(dp,0,sizeof(dp));
for(int i=0;i<N;i++)
cin>>v[i]>>w[i]>>s[i];
int total=0;
for(int i=0;i<N;i++)
{
for(int j=1;j<s[i];j<<=1)//二进制拆分
{
a[total]=j*w[i];//存价值
b[total++]=j*v[i];//存容量
s[i]-=j;
}
if(s[i])//当s[i]>0;
{
a[total]=s[i]*w[i];
b[total++]=s[i]*v[i];
}
}
for(int i=0;i<total;i++)//01背包
for(int j=V;j>=b[i];j--)
dp[j]=max(dp[j],dp[j-b[i]]+a[i]);
cout<<dp[V];
return 0;
}
AcWing 5. 多重背包问题 II 原题链接 中等
作者：
llll
,
2019-02-15 13:36:35
,
所有人可见
,
阅读 9704
llll
,
2019-02-15 13:36:35
,
所有人可见
,
阅读 9704
2^11=2048 不是应该开11倍吗？
数组a，b，和dp的大小为啥开那个大小呢 n最大等于1000，数组应开12倍，那数组不应该开12010那么大吗 为啥dp数组开2000呢
如果是二维dp的话，确实是你说的这样应该二维dp数组的第一维开12010，但是这儿直接写的是一维dp，一维dp数组开的大小之和背包容量有关啦。
您好，我想问一下dp[][]用二维数组怎么写呢？ （能简单说一下吗）
看我题解
感觉这个方法为背包问题量身定做的啊
p_q码风一致
n最大等于1000，数组应开12倍，那数组不应该开12010那么大么？
是的
开11倍
直到今天我才发现原来多重背包的二进制拆分其实就是倍增，233333
这个也不是倍增吧，就只是二进制拆分
喵喵喵QAQ
将数量为 s的物体，扩展为 1个，2个，4个....的物体，作为一个新的背包问题解决
听你这句话终于懂了！感谢！
暖风机奥委会vreqjgoijrioejferqjferoqjprrhnqgoi11vjfeiosng11册及哦啊不急tgbgrbvrgbtrgtbgtgg干部不规范古ui1h1h1h1j1j11h1h1就就就就就就就看1了了看看见好换个个发给个好就看1破i1i
哥？您在说啥？
##*￥#@##@￥
#%￥￥#%……Q%&&$*
Iam#@$%#@$%$#^$%your$@#$@$@father
##嘿嘿嘿