《广义背包樊逸杰ppt课件.ppt》由会员分享，可在线阅读，更多相关《广义背包樊逸杰ppt课件.ppt（12页珍藏版）》请在三一办公上搜索。
1、广义背包问题算法分析,1.广义背包问题描述,给定载重量为M的背包和n种物品，每种物品有一定的重量和价值，现在需要设计算法，在不超过背包载重量的前提下，巧妙选择物品，使得装入背包的物品的总价值最大化。规则是，每种物品均可装入背包多次或不装入（但不能仅装入物品的一部分）。,2.动态规划解题,保存已解决的子问题的答案，在需要时找出已求得的答案，以避免大量的重复计算。,动态规划基本思想：,动态规划解题步骤：,（1）根据最优解的性质，递归地定义最优值。（2）以自底向上的方式计算出最优值。（3）根据最优值构造最优解。,3.最优值递归定义,0-1背包：,广义背包：,4.最优值函数m(i,j),0-1背包：,
2、广义背包：,5.0-1背包算法,p0=(0,0)p1=(0,0),(2,6),p2=(0,0),(2,6),(4,9),p3=(0,0),(2,6),(4,9),(8,11),(10,14).,跳转点(j,m(i,j),6.0-1背包算法拓展,p0=(0,0)p1=(0,0),(2,6),p2=(0,0),(2,6),(4,9),.,引入中间表q,q0=p0(2,6),q1=p1(2,3),q2=p2(6,5),p1=p0q0,p2=p1q1,（排除受控点）,7.算法实现,for(遍历所有物品)/假设已遍历到物品ifor(遍历前一个跳转表pi-1)计算qi-1以及合并pi-1与qi-1操作,0
3、-1背包：,广义背包：,for(遍历所有物品)/假设已遍历到物品ifor(遍历当前跳转表pi)计算qi-1以及合并pi-1与qi-1操作,8.广义背包算法举例,pi-1:(0,0),(1.5,2),(3.3,4),(5,7),(8,10),qi-1:,设：物品i重量w=3,价值v=4,背包容量c=8：,pi:(0,0),(3,4),(1.5,2),(3,4),(4.5,6),(4.5,6),(6,8),(5,7),(6,8),(7.5,10),(7.5,10),(8,11),(8,11),9.标记函数时间复杂度,标记函数的主要计算量在于计算跳转表。当物品重量均为整数时，对于任意跳转表pi至多包
4、含c+1个节点（包括节点(0,0)），计算跳转表pi需要遍历pi与pi-1耗时2(c+1)。对于有n个物品的广义背包问题，时间复杂度为O(2n(c+1),10.计算最优解,while(当前节点编号!=0)输出当前节点编号double temp=当前节点重量-该编号代表物品重量while(当前节点编号!=temp)节点-;,“当前节点编号”初值为最后一个物品跳转表的最后一个节点（即最优值节点），找出最优解的过程实际是遍历比较最后一个物品跳转表的过程，当物品重量均为整数时，时间复杂度为O(c+1),11.参考,王晓东 著.算法设计与分析（第二版）.北京：清华大学出版社，2008,2014/11/23,
