第05讲01背包问题相关问题.ppt

背包问题的近似算法及相关问题 可行解 背包问题的一个可行解 其目标函数值 . 实例 n = 2 ， 可以得关键值s=2， 可行解： 显然最优解： 贪婪算法 求解松弛问题，得关键项s; 当取 作为近似解值，即 当 时，将第一个物品至第s-1物品放入包内； 否则将第s个物品放入包内. 注： 特点 按价值密度顺序将物品放入包内，直到放不下为止， 然后再与第s个物品价值进行比较，取较优者为最终结 果，这种算法只顾局部最优选择，而不管整体效果，故 称贪婪算法. 又考虑下面的实例I： 则算法 是将物品1，2放入包内，而最优解是将物品2，3放入包内，所以有 从而有 贪婪算法 将物品按照价值密度从大到小的顺序放入包内，直到 放不下为止； 将1中所得到得解值与物品的最大价值比较，取优者为输出 定理： 多项式时间近似算法 对于任意满足 的子集M，先将M中的物品放入包内，然后再用算法 贪婪算法或者求解子背包问题：物品集为 , 其中背包容量为 ，将得到的解与M的并作为 原背包问题的近似解。 找遍所有满足上述条件所有的M,并求得相应的近似 解，取其中最好的一个作为最终的近似解。 算法 的时间复杂度: 找不超过k个物品的子集至多 ，算法 至多 运算 次，而贪婪算法的时间复杂度为O(n)，所以 此算法的时间复杂度为 。 算法 的绝对性能比 定理 ： 。 练习 定理：如果P≠NP，那么背包问题不存在满足下述性质 的多项式时间近似算法A：存在固定的正整数K，使得 对任意实例I ，有 |A( I ) －OPT( I )|≤K 背包问题的其它算法 动态规划法 蚁群算法 遗传算法 模拟退火算法… 算法比较 算法名称 时间复杂度 优点 缺点 分枝定界法 最优解 速度慢 贪婪算法 速度快 不一定为最优解 动态规划 最优解 速度慢 遗传算法 近似最优解 速度较慢，局部最优解 有界背包问题（BKP） (多重背包问题) 无界背包问题 完全背包问题 因为背包容量有限，所以这里的 ，无界背包问题可 以转化为有界背包问题。 有界背包问题转化为0-1背包问题 将有界背包问题的第j类物品，引进含 项的新物品序列，其前 k-1 个物品的价值与重量依次为， 最后一个物品补足所缺的价值和重量，即为 那么总共有不同的 个新物品，而且每个物品最多出现一次，从而得到一 个0-1背包问题。这个转化算法的时间复杂度为 。 练习 将有界背包问题转化为0-1背包问题 子集和问题 当 得到如下定义的子集和问题（SSP） 相应算法 贪婪算法：按任意顺序将物品逐个放入包内，只要包内剩余容量足够大，然后将上述结果与最大重量的物品比较，取较好的作为输出结果。 该算法的绝对性能比为2,时间复杂度为 近似算法MTGS：将上述贪婪算法分别用于物品集{1,2,…,n},{2,3,…,n},{3,…n},…{n-1,n}, {n},取最好者作为输出。这里假定重量由大到小排序。 该算法的绝对性能比为4/3,时间复杂度为 多项式时间近似方案： （1）选取一个k, 记，求出物品集为L,包容量为C的最优解，设解值为z’,及C’=C-z’,S=N-L. （2）将S中物品由大到小排序，并按照上述的贪婪算法进行求解. 该算法的绝对性能比为1+1/k,时间复杂度为 练习 用上面几种算法解决下述子集和问题 作业