- 1、本文档共11页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
0-1背包问题
给定n个物品和一个背包。物品i的重量为wi ,
价值为vi ,背包容量为c。问如何选择装入背包
中的物品,使得装入背包的物品的价值最大?
在装入背包时,每种物品i只有两种选择,装入
或者不装入,既不能装入多次,也不能只装入
一部分。因此,此问题称为0-1背包问题。
0-1背包问题
如果在装入背包时,物品可以切割,即可以只
装入一部分,这种情况下的问题称为背包问题。
用回溯法解0-1背包问题
类似于旅行售货员问题,用一个数组P[n]存
放目前取得的最优解,用变量V表示其价值;
再用一个数组N[n] 来产生新的解,用变量
NV表示其价值,用变量W表示其重量。如
果新解更优,则替代原来的最优解,否则
就丢弃新解。然后回溯寻找下一个新解。
为此,我们先回顾一下回溯法的一般递归
算法:
用回溯法解0-1背包问题 考察的第考察的第
ss个物品个物品
Try(s){
只需考两种情况,只需考两种情况,
做挑选候选者的准备;
选或不选,即选或不选,即
while (未成功且还有候选者){ for (i=0; i2; i++)for (i=0; i2; i++)
将将ss放入背包放入背包
挑选下一个候选者next ; 物体物体ss可放可放
下个候选就是下个候选就是ii。。
中并修改权重中并修改权重
if (next可接受) { 入背包中;入背包中;
与容量;与容量;
记录next ; “记录”的“记录”的
if (满足成功条件) {成功并输出结果} 这里无论成功这里无论成功
逆操作逆操作
s = = ns = = n
else Try(s+1); 与否都要继续与否都要继续
考察考察
if (不成功) 删去next的记录; }}
return 成功与否}
用回溯法解0-1背包问题
Try(s){
for (i =0; i 2; i++)
(W+w[s]*i = C) {
if (Accept(i)) {
Record(s, i) ;
if (s n) {if ( better ) TakeNewChoice( );
您可能关注的文档
- 2-1递归-递归主要思想.pdf
- 2-2递归-常见的递归形式.pdf
- 2-3 中断计算机应用基础.pdf
- 2-4递归-递归方法小结.pdf
- 3-1分治法-基本思想.pdf
- 3.1二进制编码计算机应用基础.pdf
- 4-1贪心-基本思想.pdf
- 3-11 反置页表计算机应用基础计算机应用基础.pdf
- 3-10 页面调度计算机应用基础.pdf
- 4-2贪心-贪心选择性质.pdf
- 内蒙古巴彦淖尔磴口县诚仁中学九年级化学上册 3.2 原子的构成教案 (新版)新人教版.docx
- 湘艺版音乐五年级下册第八课《童年的回忆》(教案).docx
- 2024秋七年级英语上册 Unit 5 Family and Home Lesson 27 Danny at Home教案 (新版)冀教版.docx
- 河北省新乐市第一中学高中体育 羽毛球反手发球教案.docx
- 2024-2025学年新教材高中语文 第四单元 一 记录家乡的人和物教案(3)部编版必修上册.docx
- 上海市八年级政治下册 第四单元 分清是非 第13课 多一点情趣 多一点高雅 第2框 培养情趣教案 苏教版.docx
- 湘美版五年级下册第2课《同一幅画》教案.docx
- 20.《肥皂泡》 第一课时教案.docx
- 2024年春九年级道德与法治下册 第二单元 世界舞台上的中国 第三课 与世界紧相连 第2框 与世界深度互动教案 新人教版.docx
- (核心素养目标)2.3 测量肺活量 教案设计.docx
文档评论(0)