第05讲0-1背包问题相关问题_第1页
第05讲0-1背包问题相关问题_第2页
第05讲0-1背包问题相关问题_第3页
第05讲0-1背包问题相关问题_第4页
第05讲0-1背包问题相关问题_第5页
已阅读5页，还剩23页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

背包问题的近似算法及相关问题

可行解背包问题的一个可行解

其目标函数值.实例n=2，可以得关键值s=2，可行解：显然最优解：贪婪算法求解松弛问题，得关键项s;当取作为近似解值，即当时，将第一个物品至第s-1物品放入包内；否则将第s个物品放入包内.注：特点

按价值密度顺序将物品放入包内，直到放不下为止，然后再与第s个物品价值进行比较，取较优者为最终结果，这种算法只顾局部最优选择，而不管整体效果，故称贪婪算法.绝对性能比对于一个极小（大）化问题π，I为任意实例。设A是π的近似算法，用A解I得到的解值为A(I)，而I得最优解为OPT(I),记则近似算法A的绝对性能比定义为贪婪算法的绝对性能比定理：

.证明：由关键项定义知，对任意实例I,有最优解又有算法的解值为因此有，从而。

又考虑下面的实例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类物品，引进含

人人文库> 全部分类> 专业文献 > 医学资料

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论