AcWing 5. 多重背包问题 II
原题链接
中等
作者:
llll
,
2019-02-15 13:36:35
,
所有人可见
,
阅读 9682
#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;
}
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
##嘿嘿嘿