版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、基础问题:01背包有N件物品和一个容量为V的背包。第i 件物品的费用是ci,价值是wi。求解将哪些物品装入背包可使价值总和最大。特点是:每种物品仅有一件,可以选择放或不放。状态转移方程fiv=maxfi-1v,fi-1v-ci+wi初始化:(1) 不要求背包放满forv=0Vf0v=0;(2)要求背包放满f00为0其它f01.V均设为-时间和空间复杂度均为O(VN)优化空间复杂度(二维转一维)for i=1.Nfor v=V.0 (不是)fv=maxfv,fv-ci+wi;在每次主循环中fv保存着fi-1v的值由于费用为cost的物品不会影响状态f0.cos1,因为装不下。void ZeroO
2、ne(int cost,int weight)/处理一个物品int v; for(v=V;v=cost;v-)fv=max(fv,fv-cost+weight);for(i=1;i=n;i+)/处理所有物品ZeroOne(ci,wi);完全背包问题每种物品都有无限件可用方程:fiv=maxfi-1v-ci+k*wi|0=k*ci=v每件物品并非取或不取两种,而是有取0件、取1件、取2件等很多种。求解状态fiv的时间是O(v/ci),总的复杂度可以认为是O(V*(V/ci),需要优化一个简单有效的优化若两件物品i、j满足ci=wj,则将物品j去掉,不用考虑。需要O(N2)的时间另一个思路:转化为
3、01背包问题求解即:将一种物品拆成多件物品。更高效的转化方法把第i种物品拆成费用为ci*2k、价值为wi*2k的若干件物品, 其中k满足ci*2k=V。但我们有更优的O(VN)的算法。for i=1.N for v=0.Vfv=maxfv,fv-cost+weight这个伪代码与01背包的伪代码只有v的循环次序相反而已第i次循环中fv保存了i物品已成为入选可能时最大状态值得一提的是,上面的伪代码中两层for循环的次序可以颠倒。这个结论有可能会带来算法时间常数上的优化。void Complete(int cost,int weight) )/处理一个物品int v;for(v=cost;v=V;
4、v+)(cost理由同01) fv=max(fv,fv-cost+weight);for(i=1;i=n;i+)/处理所有物品Complete (ci,wi);多重背包问题第i种物品最多有ni件可用基本算法:和完全背包问题很类似。对于第i种物品有ni+1种策略:取0件,取1件取ni件。状态转移方程:fiv=maxfi-1v-k*ci+k*wi|0=k0的最大整数。例如,如果ni为13,就将这种物品分成系数分别为1,2,4,6的四件物品。这样就将第i种物品分成了O(log ni)种物品将原问题转化为了复杂度为O(V*log ni)的01背包问题,伪代码:处理一个物品MultiplePack(co
5、st,weight,amount) if cost*amount=VComplete (cost,weight)elsek=1while k=V)Complete(cost,weight);else int k=1;while(kamount)ZeroOne(cost*k,weight*k); amount-=k;k*=2;ZeroOne(cost*amount,weight*amount);for(i=1;i=n;i+) Multiple(ci,ci,amounti);看一道题Poj 1276有一台ATM机,有N种钞票,第k 种钞票有Dk张,每张nk元。给一个数cash,问由这些钞票组合最多能达到多少元(不超过cash)这是一道标准的多重背包问题套用Multiple()函数N次,即可。一个小小的思考:每个物品cost 是什么,weight是什么背包还有很多变化混合三种背包问题二
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 职业卫生监护管理检查表
- 写心情的日记(23篇)
- 学生检讨书(11篇)
- 元宇宙技术发展与创新动态分析
- 专项治理自查报告
- 数字经济与可持续发展的关系
- 农药制剂生产线项目经营管理方案
- 加工制造业行业趋势展望
- 固体饮料生产项目运营管理
- 2024年年学校总结感悟篇
- 2-ISO27001 2022版内审检查表
- 2024年新高考作文押题7(漫画):别人爬到山顶很厉害但你从深渊爬到地面一样很厉害
- 企业音乐年会方案
- 2024年江苏省徐州市中考二模语文试题
- 2024-2030年中国城市公交行业十四五发展分析及投资前景与战略规划研究报告
- 六年级下册道德与法治第三单元《多样文明 多彩生活》测试卷及答案(典优)
- 第13课 资本主义世界殖民体系的建立与亚非拉民族独立运动(教学课件)-【中职专用】《世界历史》(高教版2023•基础模块)
- 寓思于影光影之旅智慧树知到期末考试答案章节答案2024年湘潭大学
- 中华传统文化与公务员素质建设智慧树知到期末考试答案2024年
- 通信工程分包协议书格式
- 危险化学品经营单位应急预案.doc
评论
0/150
提交评论