文档章节

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

小强斋太
 小强斋太
发布于 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
python 回溯法 记录

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

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

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

loving_forever_
2017/01/08
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

java并发备忘

不安全的“先检查后执行”,代码形式如下: if(条件满足){ //这里容易出现线程安全问题//doSomething}else{//doOther} 读取-修改-写入 原子操作:使用CAS技术,即首先从V中读取...

Funcy1122
今天
0
0
SpringBoot2.0 停机

最近新建了个SpringBoot2.0的项目,因为原来一直使用的是传统的Tomcat部署war包的形式,所以这次SpringBoot内置Tomcat部署jar包的时候遇到了很多问题。其中一个就是因为没有外置的Tomcat容器...

Canaan_
昨天
0
1
Confluence 6 外部参考

一个外部参考的意思是任何站点链接到你 Confluence 的实例。任何时候当 Confluence 的用户单击这个外部链接的时候,Confluence 可以记录这次单击为参考。 在默认的情况下,外部链接的参考链接...

honeymose
昨天
0
0
Android中的设计模式之抽象工厂模式

参考 《设计模式解析》 第十一章 Abstract Factory模式 《设计模式:可复用面向对象软件的基础 》3.1 Abstract Factory 抽象工厂 对象创建型模式 《Android源码设计模式解析与实战》第6章 创...

newtrek
昨天
0
0
Redis | 地理空间(GEO)的一个坑

Redis的地理空间(Geo)是个好东西,轻轻松松的就可以把地图描点的问题处理了, 最近却遇到一个坑...Redis采用的Msater-Slave模式, 运用GEORADIUS在salve读取对应的数据,新增了从节点但是从不返...

云迹
昨天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部