文档章节

回溯法---->背包问题

小强斋太
 小强斋太
发布于 2016/11/09 20:06
字数 480
阅读 1
收藏 0

背包问题

给定n中物品和一个容量为c的背包,物品i的重量为Wi,其价值为Vi,0-1背包问题是如何选择装入背包的物品(物品不可分割),使得装入背包的物品的价值为最大。

限界函数

procedure  BOUND( p , w, k , M)

∥p为当前效益总量; w  为当前背包重量; k 为上次去掉的物品; M  为背包容量; 返回一个新效益值∥

global  n , P( 1∶n ) ,W( 1∶n)

integer  k , i ; real b , c , p , w, M

b←p;  c←w

for  i←k +  1 to n do

c←c +  W( i )

if  c < M then b←b + P( i )

else  return ( b + (1 - ( c - M)/ W( i) ) * P( i ) )

endif

repeat

return  ( b)

end  BOUND

背包问题的回溯法求解

procedure BKNAP1( M, n ,W,  P, fw , fp , X)

∥M 是背包容量。有n 种物品, 其重量与效益分别存在数组W(1∶n) 和P(1∶n) 中; P(i)/W(i)≥P(i+1)/W(i+ 1)。fw 是背包的最后重量, fp 是背包取得的最大效益。X(1∶n) 中每个元素取0或1值。若物品k 没放入背包, 则X(k)=0 ;否则X(k)=1

   integer n , k , Y(1∶n) , i , X(1∶n) ; real M,W( 1∶n) , P(1∶n) , fw , fp , cw , cp;

   cw←cp←0 ; k←1; fp← -1 ∥cw 是背包当前重量;cp 是背包当前取得的效益值∥

   loop

   while k≤ n and cw + W(k) ≤M do ∥将物品k 放入背包∥

   cw←cw + W(k) ; cp←cp + P(k) ;Y(k) ←1; k←  k + 1

   repeat

   if k > n then fp←cp ; fw←cw;k←n;X←Y ∥修改解∥

   else Y( k)←0 ∥超出M, 物品K 不适合∥

   endif

   while BOUND( cp、cw, k , M) ≤fp do ∥上面置了fp 后,BOUND = fp∥

   while k≠0 and Y( k)≠1 do

   k←k - 1 ∥找最后放入背包的物品∥

   repeat

   if k = 0 then return endif ∥算法在此处结束∥

   Y( k) ←0; cw←cw - W( k) ; cp←cp - P( k) ∥移掉第k 项∥

   repeat

   k←k + 1

  repeat

   end BKNAP1

 

本文转载自:http://www.cnblogs.com/xqzt/archive/2013/05/16/5637085.html

共有 人打赏支持
小强斋太
粉丝 0
博文 181
码字总数 0
作品 0
广州
算法设计与分析复习——第五章:回溯法

第五章:回溯法 1,什么是回溯法? 答: 回溯法:是一个既带有系统性又带有跳跃性的搜索算法。这在问题的解空间树中,按深度优先策略,从根结点出发搜索解空间树。算法搜索至解空间树的任一结...

科技小能手
2017/11/12
0
0
常用算法和复杂度总结

一、常用算法和复杂度 算法 名称 复杂度 备注 快速排序 QuickSort(A,p,r) 最坏:O(n2) 平均:O(nlog n) 均衡划分:O(nlog n) 合并排序 MergeSort(A,p,r) O(nlog n) 选最大 FindMax O(n) 选最...

啊莱
2010/01/03
0
0
十大算法之一回溯法—解背包问题-C#代码

1、概念 回溯法实际使用基本枚举的方式来遍历所有的解,是枚举法的一个简单优化。 按照深度优先的策略,从根结点出发搜索解空间树。搜索至解空间树的任一节点时,先判断是否满足求解条件,不...

aiTCR
2017/09/30
0
0
游戏与常用的五大算法---下篇

前言: 心是一个人的翅膀,心有多大,世界就有多大。很多时候限制我们的,不是周遭的环境,也不是他人的言行,而是我们自己!看不开,放不下,忘不了,把自己囚禁在灰暗的记忆里;不敢想,不...

loving_forever_
2017/01/08
0
0
python 回溯法 记录

一直不是太理解回溯法,这几天集中学习了一下,记录如下。 回溯法有“通用的解题法”之称。 1.定义: 也叫试探法,它是一种系统地搜索问题的解的方法。 2.基本思想: 从一条路往前走,能进则...

罗兵
2017/05/29
0
0

没有更多内容

加载失败,请刷新页面

加载更多

java序列化(七) - fst 序列化

java序列化(七) - fst 序列化 github https://github.com/RuedigerMoeller/fast-serialization 实践 https://gitee.com/mengzhang6/serializable-demo.git maven依赖 <!-- https://mvnrepo......

晨猫
3分钟前
0
0
智力问题汇总

南京新建地铁线路,给你2块钱,测出来需要配置多少辆车? 参考答案:根据地铁有固定时间间隔,坐一圈该线路,推算出需要多少辆。 一共50张卡片,上面写着1--50 ,50个数字,藏起来一张,打乱...

职业搬砖20年
7分钟前
0
0
ZFS-自我恢复RAID

ZFS-自我恢复RAID 这个给了我一个简单而又强大的理由,让我立马为之折服,ZFS可以自动的检测发生的错误,而且,可以自我修复这些错误。假设有一个时刻,磁盘阵列中的数据是错误的,不管是什么...

openthings
16分钟前
1
0
从Hash到一致性Hash原理(深度好文)

要讲一致性Hash原理,先从一般性Hash讲起,其实Hash的本质就是一个长度可变的数组,那为什么Hash的时间复杂度是O(1),而其他类型的数据结构查找都是要遍历来,遍历去,即便是树,二叉树,也是要经过几...

算法之名
29分钟前
8
0
软件测试工具书籍与面试题汇总下载(持续更新)

简介 本文是https://github.com/china-testing/python-api-tesing/blob/master/books.md 的节选。 欢迎转载,转载请附带此简介,谢谢! 试题 软件测试综合面试题(高级测试)-试题.pdf 软件测试...

python测试开发人工智能安全
37分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部