广义背包-樊逸杰

广义背包问题算法分析1.广义背包问题描述给定载重量为M的背包和n种物品，每种物品有一定的重量和价值，现在需要设计算法，在不超过背包载重量的前提下，巧妙选择物品，使得装入背包的物品的总价值最大化。规则是，每种物品均可装入背包多次或不装入（但不能仅装入物品的一部分）。2.动态规划解题保存已解决的子问题的答案，在需要时找出已求得的答案，以避免大量的重复计算。动态规划基本思想：动态规划解题步骤：（1）根据最优解的性质，递归地定义最优值。（2）以自底向上的方式计算出最优值。（3）根据最优值构造最优解。3.最优值递归定义0-1背包：广义背包：4.最优值函数m(i,j)0-1背包：广义背包：5.0-1背包算法p[0]={(0,0)}p[1]={(0,0),(2,6),}p[2]={(0,0),(2,6),(4,9),}p[3]={(0,0),(2,6),(4,9),(8,11),(10,14)}......跳转点(j,m(i,j))6.0-1背包算法拓展p[0]={(0,0)}p[1]={(0,0),(2,6),}p[2]={(0,0),(2,6),(4,9),}......引入中间表qq[0]=p[0]⊕(2,6)q[1]=p[1]⊕(2,3)q[2]=p[2]⊕(6,5)p[1]=p[0]∪q[0]p[2]=p[1]∪q[1]（排除受控点）7.算法实现for(遍历所有物品){//假设已遍历到物品ifor(遍历前一个跳转表p[i-1]){计算q[i-1]以及合并p[i-1]与q[i-1]操作}}0-1背包：广义背包：for(遍历所有物品){//假设已遍历到物品ifor(遍历当前跳转表p[i]){计算q[i-1]以及合并p[i-1]与q[i-1]操作}}8.广义背包算法举例p[i-1]:(0,0),(1.5,2),(3.3,4),(5,7),(8,10)q[i-1]:设：物品i重量w=3,价值v=4,背包容量c=8：p[i]:(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.标记函数时间复杂度标记函数的主要计算量在于计算跳转表。当物品重量均为整数时，对于任意跳转表p[i]至多包含c+1个节点（包括节点(0,0)），计算跳转表p[i]需要遍历p[i]与p[i-1]耗时2(c+1)。对于有n个物品的广义背包问题，时间复杂度为O(2n(c+1))10.计算最优解while(当前节点编号!=0){输出当前节点编号doubletemp=当前节点重量-该编号代表物品重量while(当前节点编号!=temp)节点--;}“当前节点编号”初值为最后一个物品跳转表的最后一个节点（即最优值节点），找出最优解的过程实际是遍历比较最后一个物品跳转表的过程，当物品重量均为整数时，时间复杂度为O(c+1)11.参考王晓东著.算法设计与分析（第二版）.北京：清华大学出版社，20082014/11/23