文档章节

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

小强斋太
 小强斋太
发布于 2016/11/09 20:06
字数 480
阅读 2
收藏 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
python 回溯法 记录

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

罗兵
2017/05/29
0
0
游戏与常用的五大算法---下篇

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

loving_forever_
2017/01/08
0
0

没有更多内容

加载失败,请刷新页面

加载更多

ORA 各种oraclesql错误

ORA-00001: 违反唯一约束条件 (.) ORA-00017: 请求会话以设置跟踪事件 ORA-00018: 超出最大会话数 ORA-00019: 超出最大会话许可数 ORA-00020: 超出最大进程数 () ORA-00021: 会话附属于其它某...

青峰Jun19er
4分钟前
2
0
没错,老板让我写个 BUG!

前言 标题没有看错,真的是让我写个 bug! 刚接到这个需求时我内心没有丝毫波澜,甚至还有点激动。这可是我特长啊;终于可以光明正大的写 bug 了🙄。 先来看看具体是要干啥吧,其实主要就是...

crossoverJie
17分钟前
1
0
开源软件会被云杀死吗 ?

本文转载云头条,原作者:Michael Stiefel是Reliable Software公司的负责人,是一名软件架构和开发顾问。 文章要点 虽然开源开发不会消失,但商业开源厂商的未来不是很有希望。随着全面管理的...

linuxCool
50分钟前
5
0
OSChina 周三乱弹 —— 谈什么对象?睡什么觉?

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @胖达panda :最肯忘却古人诗,最不屑一顾是相思。分享童丽的单曲《红豆生南国》: 《红豆生南国》- 童丽 手机党少年们想听歌,请使劲儿戳(这...

小小编辑
55分钟前
374
5
stylus

stylus基础教程,stylus实例教程,stylus语法总结

miaojiangmin
今天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部