2022年背包问题的多种解法 .pdf

《2022年背包问题的多种解法 .pdf》由会员分享，可在线阅读，更多相关《2022年背包问题的多种解法 .pdf（4页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、0-1 背包问题的多种解法【摘要】本文主要从动态规划经典背包问题的设计思路出发，结合具体实例，给出了多种解决思路。【关键字】动态规划贪心算法穷举法 0/1背包问题一原型问题从 n 个物品中选取装入背包的物品，每件物品i 的重量为 wi ，价值为 pi , 背包容量为c.求使物品价值最高的选取方法。（每个物品要么不取，要么取一次）二解决方法1. 穷举法： 用穷举法解决0-1 背包问题， 需要考虑给定n 个物品集合的所有子集，找出所有可能的子集（总重量不超过背包重量的子集），计算每个子集的总重量，然后在他们中找到价值最大的子集。由于程序较简单，在这里就不再给出，用实例说明求解过程。下面给出了 4

2、个物品和一个容量为10 的背包，下图就是用穷举法求解0-1 背包问题的过程。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 4 页 - - - - - - - - - 2. 贪心法：贪心准则1：从剩余的物品中，选出可以装入背包的价值最大的物品，利用这种规则，价值最大的物品首先被装入（假设有足够容量） ，然后是下一个价值最大的物品，如此继续下去。这种策略不能保证得到最优解。例如，考虑n=2, w=100,10,10, p =20,15,15, c =105。当利用价值贪婪准

3、则时，获得的解为x= 1,0,0，这种方案的总价值为20。而最优解为0,1,1，其总价值为30。贪心准则2：从剩下的物品中选择可装入背包的重量最小的物品。虽然这种规则对于前面的例子能产生最优解，但在一般情况下则不一定能得到最优解。考虑n= 2 ， w=10,20 p=5,100，c= 2 5 。当利用重量贪婪策略时，获得的解为x =1,0, 比最优解 0 , 1 要差。贪心准则3：价值密度pi /wi 贪婪算法，这种选择准则为：从剩余物品中选择可装入包的pi /wi 值 最 大 的 物 品 ， 但 是 这 种 策 略 也 不 能 保 证 得 到 最 优 解 。 利 用 此 策 略 解n=3 ,

4、w=20,15,15, p=40,25,25, c=30 时的得到的就不是最优解。3. 动态规划法：在 0/1 背包问题中，物体或者被装入背包，或者不被装入背包，只有两种选择。循环变量i ，j 意义：前 i 个物品能够装入载重量为j 的背包中 (n+1)*(m+1) 数组 value 意义： valueij表示前 i 个物品能装入载重量为j 的背包中物品的最大价值若 wij，第i个物品不装入背包否则，若wivaluei-1j，则记录当前最大价值（替换为第i 个物品装入背包后的价值）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - -

5、名师精心整理 - - - - - - - 第 2 页，共 4 页 - - - - - - - - - 计算最大价值的动态规划算法如下：即该段程序完成以下n 个阶段：1：只装入1 个物品，确定在各种不同载重量的背包下，能够得到的最大价值2：装入 2个物品，确定在各种不同载重量的背包下，能够得到的最大价值.n. 以此类推，装入n 个物品，确定在各种不同载重量的背包下，能够得到的最大价值接下来确定装入背包的具体物品，从 valuenm向前逆推：若 valuenmvaluen-1m ，则第 n 个物品被装入背包，且前n-1 个物品被装入载重量为m-wn 的背包中。否则，第n 个物品没有装入背包，且前n

6、-1 个物品被装入载重量为m的背包中以此类推，直到确定第一个物品是否被装入背包为止。逆推代码如下：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 4 页 - - - - - - - - - 三算法效率分析1. 穷举法对于一个有n 个元素的集合， 其子集数量为2 的 n 次个， 所以， 不论生成子集的算法效率有多高，穷举法都会导致一个O（2 的 n 次）的算法。2. 贪心法虽然能以较快的速度得出一个相对较好的解，由于不能准确提供最优解，故此方法并不提倡。3 动态规划法最理想状态下，计算时间复杂性为O （ nc） 。四小结同一个问题会有多种解法，不同的解法会有不同的效率，利用最少的资源实现尽可能好的程序效果，正是算法的魅力所在。软工 1024 吕佳盛201226630407 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 4 页 - - - - - - - - -