01背包
2018-06-17 23:52:06来源:未知 阅读 ()
以前在acm课上也讲过一些关于背包的题,不过那些比较简单,就是简单的贪心问题,先排个序再处理就完了,而01背包,感觉就是比那个上了一个难度的问题,这个需要遍历然后找其中合适的,简单原理就是这样。
例如:现在有容量为m的背包,还有重量为w,价值为v的k个不同的商品,问怎样买才能使价值最大化?
思路:如果是贪心问题就是直接将商品按价格从大到小排序,然后依次买,显然这样是错的,我们要在容量范围内尽量买价值高的,有时候是买到恰好容量满,这时候价值最大化。
直接dp遍历找:
memset(d,0,sizeof(d)); /初始化为0.
for(int i=0;i<k;i++) /共k个商品
for(int j=m;j>=w[i];j--)/d[j]表示容量为j时,背包的最大价值为d[j]
d[j]=max(d[j],d[j-w[i]]+v[i]); /进行比较选择买和不买时造成的价值
cout<<d[m]<<endl; /输出容量为m时的最大价值
简单的01背包模板就是上边的,碰到类似的这类题改改就好了
这个模板是递推型的,还有递归的,然而那个比较长,一般都用递推的这个。
学姐给的练习题有些是先进行排序处理的,有些是需要你自己把题意转化为01背包的问题,就如那个抢银行概率问题。
练习题网址:
01背包练习题链接http://acm.hust.edu.cn/vjudge/contest/126172#overview
待续……
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:哲学家就餐问题(CPP)
下一篇:Lexer的设计--下(5)
- HDU-2955-Robberies(0-1背包) 2020-03-30
- ACM | 算法 | 快速幂 2019-12-04
- 多重背包问题 2019-11-04
- 统计字符的个数,能够组成几个acmicpc 2019-10-16
- NOIP模拟day1-T1(完全背包) 2019-10-12
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