当前位置:首页 >> 工学 >>

Pascal经典算法-背包问题析


经典算法问题解析---背包问题

前言
背包问题是程序设计中一个很经典的 问题,很多题目都是在该问题上延伸开来的, 对与背包问题我们有多种解题方法(算法), 其中最常用的是贪心,搜索,递归,动态规划 等,它们各有千秋,我们还将从算法的角度 来分析这些算法的原理和它的正确性质和 执行效率。

0-1背包问题
?所谓的背包问题,可以描述如下: ?一个小偷打劫一个保险箱,发现柜子里有N 个不同大小与价值的物品,但小偷只有一 个容积为M的背包来装东西,背包问题就是 要找出一个小偷选择所偷物品的组合,以 使偷走的物品总价值最大。我们标识每个 物品的价为VI,大小是ZI

算法描述
?对于0/1背包相关的问题我们有多种方法可 以解决 ⑴贪心法 ⑵搜索法(回溯) (3)递归 ⑷动态规划

⑴ 贪心法
?贪心算法描述: ?总是对当前的问题作最好的选择,也就是局 部寻优。最后得到整体最优。 ?应用: ?1:该问题可以通过“局部寻优”逐步过渡 到“整体最优”。但是这种思路是否可以解 决问题 ?2:最优子结构性质:某个问题的整体最优 解包含了“子”问题的最优解。

该题设计的贪心算法
? 利用贪心算法的定义,我们定义一个数组变量 A[I]:=V[I]/Z[I]来表示每件物品的单位体积的价 值,然后按照单位体积的价值进行从大到小的排序, 小偷取东西的时候的策略先取单位体积价值最高 的物品,一直到背包不能再放物品为止; ? 该算法的分析: 该算法简单,而且执行效率比较高但是也有一个致 命的缺陷.我们利用贪心法可以解决部分问题,但 是我们不能解决所有问题.我想大家在”采药”这 一题中应该有清醒的认识!

参考程序段
For i:=1 to n do A[I]:=V[I]/Z[I]//求单位价值 For i:=1 to n-1 do for j:=i+1 to n do If a[i]<a[j] then begin v[i]<->v[j];z[i]<->z[j];A[I]<->A[J];end; //按照单位价值的从大到小排列; i:=1;v:=0; While m>a[i] do Begin V:=v+v[i]; M:=m-z[i]; i:=i+1;end; //按照单位价值从大到小取物品 Writeln(‘the total value is’,v); //上面的题目存在什么问题,该怎么去解决它

⑵搜索法
?搜索算法介绍: ?经过对题目的分析我们可以的出下列结论, 对于每个物品来说我们只有两中状态取或 者不取,也就是一个背包的解就是一个长 小于N的决策序列,这个序列是有(0,1) 组成,所以我们可以利用回溯的原理将所 有的背包的所有可能列举出来,然后在所 有的可能性中找到最优的解;

一:回溯的概念
? 从问题的某种可能情况出发,搜索所有能到达的 可能情况,然后以其中一种可能的情况为新的出 发点,继续向下探索,当所有可能情况都探索过 且都无法到达目标的时候,再回退到上一个出发 点,继续探索另一个可能情况,这种不断回头寻 找目标的方法称为“回溯法”。 ? 回溯算法是一种有条不紊的搜索问题答案的方法, 是一种能避免不必要搜索的穷举式的搜索算法, 其基本思想就是穷举搜索。常用于查找问题的解 集或符合某些限制条件的最佳解集。

二、回溯的通用描述算法

program 程序名; const maxdepth=xxx; type statetype=****; {状态类型定义} var stack:array[1..maxdepth] of statetype; {存当前路径} total:integer; {路径数} procedure make(k:integer); {递归搜索以stack[k]为初始接点的所有路径} var i:integer; {子节点个数} begin if stack[k-1]是目标状态 then begin total:=total+1; 输出当前路径stack[1]..stack[k-1]; exit; {回溯(如果只需要一条路径,则exit改为halt即可)}} end; for i:=算符最小值 to 算符最大值 do begin 算符i作用于生成stack[k-1]产生子状态stack[k]; if stack[k]满足约束条件 then make(k+1);{若不满足,则通过for循环换一个算符扩 扩展。注:若在扩展stack[k].state时使用过全局变量,则应插入若干条语句,恢复这些全局 end; end;

0/1背包问题的分析
? 该背包问题的目的在于求最优解,所以我们要用 回溯的方法将所有的解求出来,逐一比较求最优 秀的解; ? 对于每个节点的扩展只有两种类可能要不取,要 不不取,所以该搜索树为一个N层的二叉树。 ? 解空间的长度是<=n。 ? 解空间的组织形式是一棵2叉树,一个可行的解就 是从根节点到叶子节点的一条路径。每个解为一 个长度不超过N的0/1代码序列 ? 控制策略则是前面的选择没有超过背包的容量。

程序基本部分
Procedure Try(I:integer);{搜索第到I个物品} var j:integer; Begin If i>N then t:=max(total(n),t);//产生一个解,和当前的最优解比较 for j:=0 to1 do//对每个物品有取和不取两种情况 Begin //使用a:array[1..n]of 0..1表示每个物品的状态 If m>z[i]*j then//如果包中还有空间 begin a[i]:=j;//标识该物品的状态 m:=m-a[i]*j;//剩余空间变化 try[i+1];//下一个物体选择 m:=m-a[i]*j;//剩余空间变化 a[i]:=0; end; End.

递归概念
我们可以用choose(I,z)来表示后i个物品在只剩下v个体积的空间中取的最 大价值 那么choose(n,z)=max(v1+choose(n-1,z-z1),choose(n-1,z)); 边界条件choose(I,0)=0; choose(0,z)=0

程序框架
Function ans(I,j:integer):integer; Begin If (i<=0) or( j<=0) then ans:=0 else ans(n,z)=max(v1+choose(n-1,zz1),choose(n-1,z)); End. //使用递归结构清晰明了,但是我们都知道低的执行效率并不 高,特别是递归层次过多

进一步分析,举例
Z V 3 4 4 5 7 10 8 11 9 13

分析如果假设要求choose(5,20),那么我们根据公式 得choose(5,20)=max(4+choose(4,20-3),choose(4,20)) 其中 choose(4,17)=max(5+choose(3,13),choose(3,17)); choose(4,20)=max(5+choose(3,16),choose(3,20)); 要调用choose(3,13), choose(3,16), choose(3,17), choose(3,20) 又其中 choose(3,13)=max(10+choose(2,6),choose(2,13); choose(3,16)=max(10+choose(2,9),choose(2,16); choose(3,17)=max(10+choose(2,10),choose(2,17); choose(3,20)=max(10+choose(2,13),choose(2,20); 又要调用 choose(2,6)=max(11+choose(1,-2

动态规划概念
? F[I,j]为前i个物品中选择若干个放入使其体积正好为j的标志,为布尔 型。 实现:将最优化问题转化为判定性问题 F[I,j]=f[i-1,j-w[i]] (w[I]< =j< =v) 边界:f[0,0]:=true. For I:=1 to n do For j:=w[I] to v do F[I,j]:=f[I-1,j-w[I]]; 优化:当前状态只与前一阶段状态有关,可降至一维。 F[0]:=true; For I:=1 to n do begin F1:=f; For j:=w[I] to v do If f[j-w[I]] then f1[j]:=true; F:=f1; End;

动态规划的基本思想
通过分析我们推导公式: choose(n,z)=max(v1+choose(n-1,z-z1),choose(n-1,z)); 边界条件choose(I,0)=0; choose(0,z)=0 而在函数调用的过程中我们经常要调用相同的子程序所以我们设想用数 组将所有的中间环节存储下来 而我们推倒则使用从底向上推倒的方式 “从顶向下分析,从底向上推倒” For i:=0 to m do ch[0,i]:=0; For i:=1 to n do for j:=1 to m do If j-v[i]>=0 then Ch[I,j]:=max(v[i]+ch[i-1,j-v[i]],ch[i-1,j]) 它的时间复杂度为N*M

另一种背包问题
?一个小偷打劫一个保险箱,发现柜子里有N 种类不同大小与价值的物品,但小偷只有 一个容积为M的背包来装东西,背包问题就 是要找出一个小偷选择所偷物品的组合, 以使偷走的物品总价值最大。我们标识每 个物品的价为VI,大小是ZI

课后习题:垃圾陷阱
卡门——农夫约翰极其珍视的一条Holsteins奶牛——已经落了到“垃圾井”中。 “垃圾井”是农夫们扔垃圾的地方,它的深度为D (2 <= D <= 100)英尺。 卡门想把垃圾堆起来,等到堆得与井同样高时,她就能逃出井外了。另外,卡门可 以通过吃一些垃圾来维持自己的生命。 每个垃圾都可以用来吃或堆放,并且堆放垃圾不用花费卡门的时间。 假设卡门预先知道了每个垃圾扔下的时间t(0<t<=1000),以及每个垃圾堆放的高度 h(1<=h<=25)和吃进该垃圾能维持生命的时间f(1<=f<=30),要求出卡门最早能 逃出井外的时间,假设卡门当前体内有足够持续10小时的能量,如果卡门10小 时内没有进食,卡门就将饿死。 输入 第一行为2个整数,D 和 G (1 <= G <= 100),G为被投入井的垃圾的数量。 第二到第G+1行每行包括3个整数:T (0 < T <= 1000),表示垃圾被投进井中的时 间;F (1 <= F <= 30),表示该垃圾能维持卡门生命的时间;和 H (1 <= H <= 25),该垃圾能垫高的高度。 输出 如果卡门可以爬出陷阱,输出一个整表示最早什么时候可以爬出;否则输出卡门最 长可以存活多长时间。

? ? ? ? ? ? ? ? ? ? ? ? ?

WELL.IN 20 4 549 932 12 6 10 13 1 1 WELL.OUT 13 [样例说明] 卡门堆放她收到的第一个垃圾:height=9; 卡门吃掉她收到的第二个垃圾,使她的生命从10小时延伸到13小时; 卡门堆放第3个垃圾,height=19; 卡门堆放第4个垃圾,height=20。


相关文章:
Pascal经典算法-背包问题析_图文.ppt
Pascal经典算法-背包问题析 - 经典算法问题解析---背包问题 前言 背包
-背包问题-算法设计及分析.pdf
-背包问题-算法设计及分析 - 于淼:“背包问题算法设计及分析 “背包问题算法设计及分析 于 (辽宁鞍山气象局 淼 辽宁鞍山 114004) 摘要:“背包问题”是一个...
0-1背包问题的各种算法分析.doc
Shanxi University of Finance and Economics 本科毕业论文 题目: 0-1 背包问题的各种算法分析 学专学姓 院: 业: 号: 名: 应用数学学院 信息与计算科学 指导...
Pascal经典算法-背包问题析_图文.ppt
Pascal经典算法-背包问题析 - 经典算法问题解析---背包问题 前言 背包
算法设计-01背包问题的分析.doc
算法设计-01背包问题的分析_工学_高等教育_教育专区。个人对于01背包问题的一个简单认识 算法设计与分析 ---0/1 背包问题实例研究 班级:090402 学号:20091236...
0-1背包问题的递归算法.pdf
0-1背包问题的递归算法 - 第 19 卷 6 期 Vol . 18 No. 6 第益阳师专 ...... 了背包问题的求解最佳解的经典算法 , 提出了一种求解 0 - 1 背包问题的...
必背经典算法(pascal).doc
必背经典算法(pascal)_电脑基础知识_IT/计算机_专业资料。一、数论算法 1.求...三、背包问题 *部分背包问题可有贪心法求解:计算 Pi/Wi 数据结构: w:第 i ...
0-1背包问题的求解算法设计与分析_论文.pdf
0-1背包问题的求解算法设计与分析 - 0-1背包问题在信息密码学和数论研究中有着极其重要的应用。首先对背包问题作了简要描述,然后对0-1背包问题的两种经典算法:...
算法设计与分析--01背包问题(动态规划法解决)_图文.pdf
算法设计与分--01背包问题(动态规划法解决)_电子/电路_工程科技_专业资料
freepascal 贪心算法_图文.ppt
freepascal 贪心算法_IT/计算机_专业资料。LOGO 贪心算法 LOGO 在现实生活中,...依次类推 对于部分背包问题,先对每件物品计算其每磅价值Vi/Wi,然后按每磅价值...
0-1背包问题算法分析与研究_图文.pdf
0-1背包问题算法分析与研究 - 兰 O1一 背包 问题 算法 与研 究
第9章 动态规划(背包问题).ppt
第9章 动态规划(背包问题)_物理_自然科学_专业资料。PASCAL语言第二部分 基础算法 第九章 动态规划(背包问题)第九章 动态规划 (背包问题) PASCAL语言基础算法 ...
0-1背包问题算法分析与研究_图文.pdf
0-1背包问题算法分析与研究 - 竺兰竺 O一1背包问题算法分析与研究 周斌1
Pascal高级教程-算法篇_图文.ppt
Pascal高级教程-算法篇_计算机软件及应用_IT/计算机_...(树形动规) 0/1背包问题背包问题(Knapsack problem...
0_1背包问题算法分析与研究.pdf
0_1背包问题算法分析与研究 - ? ? 周摘 研究与开发 0-1 背包问题算法分析与研究 斌1 ,张莹2 , 黄志军 1 (1. 中南民族大学,武汉 430074 ; 2. 华中科学...
01背包问题.doc
Pascal动态规划全接触 背包问题动态规划详解动态规划是...能确定某些问题的可行解的范围,特别是给搜索算法提供...经典的01背包问题 16页 免费 01背包 17页 免费 ...
01背包问题不同算法设计、分析与对比.doc
01背包问题不同算法设计、分析与对比 - 实践动态规划、贪心、回溯以及分支限界算法程序设计
算法设计--普通背包问题与棋盘覆盖问题分析.doc
算法设计--普通背包问题与棋盘覆盖问题分析 - 目 录 一、问题描述......
算法设计和分析实验四:贪心算法求解背包问题.doc
算法设计和分析实验四:贪心算法求解背包问题_工学_高等教育_教育专区。计算机学院 算法设计和分析课程实验 背包问题 实验五:贪心算法求解背包问题实验内容应用贪心算法...
_背包问题_算法设计及分析_孙劲光.pdf
因此, “背包问题”求解也是算法设计及验证的一个热点,本文分别采用了 优先策略、动态规划及递归三种不同方法对“背包问题”进行求解、算法设计及验证,文中较详细的...
更多相关标签: