ascal经典算法-背包问题析.ppt

经典算法问题解析-背包问题 前言 背包问题是程序设计中一个很经典的 问题,很多题目都是在该问题上延伸开来的 ,对与背包问题我们有多种解题方法(算法 ),其中最常用的是贪心,搜索,递归,动态规 划等,它们各有千秋,我们还将从算法的角 度来分析这些算法的原理和它的正确性质 和执行效率。 0-1背包问题 l所谓的背包问题，可以描述如下： l一个小偷打劫一个保险箱，发现柜子里有N 个不同大小与价值的物品，但小偷只有一 个容积为M的背包来装东西，背包问题就是 要找出一个小偷选择所偷物品的组合，以 使偷走的物品总价值最大。我们标识每个 物品的价为I,大小是ZI 算法描述 l对于0/1背包相关的问题我们有多种方法可 以解决 贪心法 搜索法(回溯) (3)递归 动态规划 贪心法 l贪心算法描述: l总是对当前的问题作最好的选择，也就是局 部寻优。最后得到整体最优。 l应用： l1：该问题可以通过“局部寻优”逐步过渡到“ 整体最优”。但是这种思路是否可以解决问题 l2：最优子结构性质：某个问题的整体最优 解包含了“子”问题的最优解。 该题设计的贪心算法 l利用贪心算法的定义，我们定义一个数组变量 AI:=VI/ZI来表示每件物品的单位体积的价 值,然后按照单位体积的价值进行从大到小的排序 ,小偷取东西的时候的策略先取单位体积价值最高 的物品,一直到背包不能再放物品为止; l该算法的分析: 该算法简单,而且执行效率比较高但是也有一个致 命的缺陷.我们利用贪心法可以解决部分问题,但 是我们不能解决所有问题.我想大家在”采药”这 一题中应该有清醒的认识! 参考程序段 For i:=1 to n do AI:=VI/ZI/求单位价值 For i:=1 to n-1 do for j:=i+1 to n do If aivj;zizj;AIAJ;end; /按照单位价值的从大到小排列； i:=1;v:=0; While mai do Begin V:=v+vi; M:=m-zi; i:=i+1;end; /按照单位价值从大到小取物品 Writeln(the total value is,v); / /上面的题目存在什么问题上面的题目存在什么问题, ,该怎么去解决它该怎么去解决它 搜索法 l搜索算法介绍： l经过对题目的分析我们可以的出下列结论 ，对于每个物品来说我们只有两中状态取 或者不取，也就是一个背包的解就是一个 长小于的决策序列，这个序列是有（ ,1)组成，所以我们可以利用回溯的原理将 所有的背包的所有可能列举出来，然后在 所有的可能性中找到最优的解； 一：回溯的概念 l从问题的某种可能情况出发，搜索所有能到达的 可能情况，然后以其中一种可能的情况为新的出 发点，继续向下探索，当所有可能情况都探索过 且都无法到达目标的时候，再回退到上一个出发 点，继续探索另一个可能情况，这种不断回头寻 找目标的方法称为“回溯法”。 l回溯算法是一种有条不紊的搜索问题答案的方法 ，是一种能避免不必要搜索的穷举式的搜索算法 ，其基本思想就是穷举搜索。常用于查找问题的 解集或符合某些限制条件的最佳解集。 二、回溯的通用描述算法 program 程序名； const maxdepth=xxx; type statetype=*; 状态类型定义 var stack:array1maxdepth of statetype; 存当前路径 total:integer; 路径数 procedure make(k:integer); 递归搜索以stackk为初始接点的所有路径 var i:integer; 子节点个数 begin if stackk-1是目标状态 then begin total:=total+1; 输出当前路径stack1stackk-1; exit; 回溯（如果只需要一条路径，则exit改为halt即可） end; for i:=算符最小值 to 算符最大值 do begin 算符i作用于生成stackk-1产生子状态stackk; if stackk满足约束条件 then make(k+1);若不满足，则通过for循环换一个算符扩展；递归返回该处时，系统自动恢复调用前的栈指针和算符；在通过for 循环换一个算符 扩展。注：若在扩展stackk.state时使用过全局变量，则应插入若干条语句，恢复这些全局变量在递归前的值 end; end; 0/1背包问题的分析 l该背包问题的目的在于求最优解，所以我们要用 回溯的方法将所有的解求出来，逐一比较求最优 秀的解； l对于每个节点的扩展只有两种类可能要不取，要 不不取，所以该搜索树为一个N层的二叉树。 l解空间的长度是N then t:=max(total(n),t);/产生一个解，和当前的最优解比较 for j:=0 to1 do/对每个物品有取和不取两种情况 Begin /使用a:array1nof 01表示每个物品的状态 If mzi*j then/如果包中还有空间 begin ai:=j;/标识该物品的状态 m:=m-ai*j;/剩余空间变化 tryi+1;/下一个物体选择 m:=m-ai*j;/剩余空间变化 ai:=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 then ChI,j:=max(vi+chi-1,j-vi,chi-1,j) 它的时间复杂度为N*M 另一种背包问题 l一个小偷打劫一个保险箱，发现柜子里有N 种类不同大小与价值的物品，但小偷只有 一个容积为M的背包来装东西，背包问题就 是要找出一个小偷选择所偷物品的组合， 以使偷走的物品总价值最大。我们标识每 个物品的价为I,大小是ZI 课后习题：垃圾陷阱 卡门农夫约翰极其珍视的一条Holsteins奶牛已经落了到“垃圾井”中。“垃 圾井”是农夫们扔垃圾的地方，它的深度为D (2 = D = 100)英尺。 卡门想把垃圾堆起来，等到堆得与井同样高时，她就能逃出井外了。另外，卡门可 以通过吃一些垃圾来维持自己的生命。 每个垃圾都可以用来吃或堆放，并且堆放垃圾不用花费卡门的时间。 假设卡门预先知道了每个垃圾扔下的时间t(0t=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)，该垃圾能垫高的高度。 输出 如果卡门可以爬出陷阱，输出一个整表示最早什么时候可以爬出；否则输出卡门最 长可以存活多长时间。 lWELL.IN