多重背包模板
2019-01-21 02:36:45来源:博客园 阅读 ()
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
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- C++冒泡排序 (基于函数模板实现) 2020-05-31
- C++ 模板类vector 2020-05-31
- C++ 模板类array 2020-05-31
- C++ 模板类vector 2020-05-30
- 单调队列模板【附例题】 2020-05-05
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash