用贪心算法解决背包问题.ppt

2010. 12. 20 组员: 王丹 魏蕾 魏晓卡 李丹 背包问题的贪心算法 * 1 问题描述 内容提要 2 3 实验及结果 4 实验总结 算法思想及分析 * 已知有n种物品和一个可容纳c重量的背包，每种物品i的重量为wi。假定物品i的一部分放入背包会得到vixi的效益。其中0≤xi≤1,vi0 . 采用怎样的装包方法才会使装入背包物品的总效益最大呢？即求解 (4.2.1) (4.2.2) (4.2.3) 其中（4.2.1）是目标函数，（4.2.2）及（4.2.3）是约束条件。满足约束条件的任一集合(x1,…,xn) 一个可行解，使目标函数取最大值的可行解是最优解。 问题描述： * 贪心算法 算法思想及分析 对于一个具体的问题，怎么知道是否可用贪心算法解此问题，以及能否得到问题的最优解呢?这个问题很难给予肯定的回答。 但是，从许多可以用贪心算法求解的问题中看到这类问题一般具有2个重要的性质：贪心选择性质和最优子结构性质。 --- 选取最优的量度标准实为用贪心方法求解问题的核心. * 4.3 贪心算法的基本要素 1.贪心选择性质 所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。 动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。  对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。 * 4.3 贪心算法的基本要素 2.最优子结构性质 当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。 * 考虑下列情况下的背包问题: n＝3,c＝20, (v1,v2,v3)=(25,24,15),(w1,w2,w3)=(18,15,10) 其中的四个可行解是 ①（1/2, 1/3, 1/4） 16.5 24.25 ②（1, 2/15, 0） 20 28.2 ③（0, 2/3, 1） 20 31 ④（0, 1, 1/2） 20 31.5 先检验这四个为可行解*,即满足约束条件(4.2.2),(4.2.3).再比较目标函数值,∑vixi .知④组解效益值最大.该组解是背包问题的最优解。(见定理4.2） 问题分析 可行解有无穷多. * 例4.4 考虑下列情况下的背包问题: n＝3,c＝20, (v1,v2,v3)=(25,24,15),(w1,w2,w3)=(18,15,10) 其中的四个可行解是 ①（1/2, 1/3, 1/4） 16.5 24.25 ②（1, 2/15, 0） 20 28.2 ③（0, 2/3, 1） 20 31 ④（0, 1, 1/2） 20 31.5 先检验这四个为可行解*,即满足约束条件(4.2.2),(4.2.3).再比较目标函数值,∑vixi .知④组解效益值最大.该组解是背包问题的最优解。 可行解有无穷多. * 算法思想及分析 假设N=（V，{E}）是一个连通网，节点数为L（V），边 数为L（E），且L（E）不能小于L（V）。T=（V，{E’}）（ E‘∈E）是目标生成树，开始假设有m个点，n条边，先在所 有边中找出权最小的边，将它加入最小生成树中并输出，然后 把此条边的权改为无穷大，相继添加不与已经选择的边形成简 单回路的权最小的边，当选择了n-1条边时停止，则这n-1条边 组成的即为最小生成树。 Kruskal算法 * （1）取目标函数作为量度标准，即每次选择利润最大的物品装包，使背包获得最大可能的效益值增量。在此量度标准下贪心方法就是按效益值的非增次序，将物品一一装包