广义背包-樊逸杰.pptVIP

广义背包问题算法分析 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),} ... ... 引入中间表q q[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 (遍历所有物品) { // 假设已遍历到物品i for (遍历前一个跳转表p[i-1]) { 计算q[i-1]以及合并p[i-1]与q[i-1]操作 } } 0-1背包： 广义背包： for (遍历所有物品) { // 假设已遍历到物品i for (遍历当前跳转表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) { 输出当前节点编号 double temp = 当前节点重量 - 该编号代表物品重量 while (当前节点编号 != temp) 节点--; } “当前节点编号”初值为最后一个物品跳转表的最后一个 节点（即最优值节点），找出最优解的过程实际是遍历比较 最后一个物品跳转表的过程，当物品重量均为整数时，时间 复杂度为O(c+1) 11.参考 王晓东 著. 算法设计与分析（第二版）. 北京：清华大学出版社，2008 2014/11/23