第四章-贪心算法.pptVIP

算法设计与分析 适用专业： 计算机科学与技术（本科） 理论学时： 54 实践学时： 18 贪心算法 顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。 贪心算法 找零钱问题 假设有4种硬币，面值分别为25分、10分、5分和1分，现要找给顾客6角三分钱，很自然的要拿出2个25分、一个10分和3个1分来找给顾客，这里就是运用了方法就是贪心算法。 贪心算法 4.1 活动安排问题 问题描述： 设有n个活动的集合E={1,2,…,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si fi 。如果选择了活动i，则它在半开时间区间[si, fi)内占用资源。若区间[si, fi)与区间[sj, fj)不相交，则称活动i与活动j是相容的。也就是说，当si≥fj或sj≥fi时，活动i与活动j相容。 4.1 活动安排问题 贪心选择的目标： 使剩余的可安排的时间段最大化，以便安排尽可能多的相容活动。 4.1 活动安排问题 关键问题： 如何选择第一个要开始的活动？在剩余活动中，满足什么条件的活动应该首先安排？ 4.1 活动安排问题 数据组织： 表示所有活动的开始时间和结束时间，活动是否被安排的标志。 贪心算法描述 在下面所给出的解活动安排问题的贪心算法greedySelector : public static int greedySelector(int [] s, int [] f, boolean a[]) { int n=s.length-1; a[1]=true; int j=1; int count=1; for (int i=2;i=n;i++) { if (s[i]=f[j]) { a[i]=true; j=i; count++; } else a[i]=false; } return count; } 一个实例 例：设待安排的11个活动的开始时间和结束时间按结束时间的非减序排列如下： 图示 算法greedySelector 的计算过程如右图所示。图中每行相应于算法的一次迭代。阴影长条表示的活动是已选入集合A的活动，而空白长条表示的活动是当前正在检查相容性的活动。 贪心算法的基本要素 从许多可以用贪心算法求解的问题中看到这类问题一般具有2个重要的性质：贪心选择性质和最优子结构性质。 贪心算法与动态规划算法的差异 贪心算法和动态规划算法都要求问题具有最优子结构性质，这是2类算法的一个共同点。但是，对于具有最优子结构的问题应该选用贪心算法还是动态规划算法求解?是否能用动态规划算法求解的问题也能用贪心算法求解?下面研究2个经典的组合优化问题，并以此说明贪心算法与动态规划算法的主要差别。 0-1背包问题 背包问题 0-1背包问题与背包问题 0-1背包问题： 给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大？ 在选择装入背包的物品时，对每种物品i只有2种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。 背包问题: 与0-1背包问题类似，所不同的是在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，1≤i≤n。 这2类问题都具有最优子结构性质，极为相似，但背包问题可以用贪心算法求解，而0-1背包问题却不能用贪心算法求解。 用贪心算法解背包问题的基本步骤 首先计算每种物品单位重量的价值Vi/Wi，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。 具体算法可描述如下： void Knapsack(int n,float M,float v[],float w[],float x[]) { Sort(n,v,w); v/w高低有序 int i; for (i=1;i=n;i++) x[i]=0; float c=M; for