多重背包模板

2019-01-21 02:36:45来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

2019-01-19

多重背包:每种东西有多个,因此可以把它拆分成多个01背包

优化:二进制拆分(拆成1+2+4+8+16+...,分别表示2的n次幂)

比如18=1+2+4+8+3,可以证明18以内的任何数都可以用这几个数的和或差表示(每个数只能用一次)(0时则背包为空),

所以就把2个,4个....绑定为一个物品,和一个一个的效果是一样的

这样就减少了拆分出来的物品的数量。(从n到log n)

代码

 1 #include<cstdio>
 2 using namespace std;
 3 const int maxn = 200005;
 4 int n,m,a,b,c,cnt,ans,f[maxn],v[maxn],w[maxn];
 5 int main() {
 6     scanf("%d%d",&n,&m);
 7     for(int i = 1;i <= n;i++){
 8         scanf("%d%d%d",&a,&b,&c);
 9         for(int j = 1;j <= c;j *= 2){
10             c -= j;
11             v[++cnt] = a*j;//区分++cnt和cnt++ 
12             w[cnt] = b*j;
13         }
14         if(c){
15             v[++cnt] = a*c;
16             w[cnt] = b*c;
17         }
18     }
19     for(int i = 1;i <= cnt;i++) 
20         for(int j = m;j >= w[i];j--){
21             f[j] = max(f[j],f[j-w[i]]+v[i]);
22             ans = max(f[j],ans);
23         }
24     printf("%d",ans);
25     return 0;
26 }

 


原文链接:https://www.cnblogs.com/zhanlurenzhe/p/10293183.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:重载操作符 &#39;operator&#39;

下一篇:51nod——1174 区间中最大的数(ST)