五大常用算法——贪心算法详解及经典例子

        贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。

基本思路：

⒈ 建立数学模型来描述问题。

⒉ 把求解的问题分成若干个子问题。

⒊ 对每一子问题求解，得到子问题的局部最优解。

⒋ 把子问题的解局部最优解合成原来解问题的一个解。

该算法存在问题：

 1. 不能保证求得的最后解是最佳的；

 2. 不能用来求最大或最小解问题；

 3. 只能求满足某些约束条件的可行解的范围。

实现该算法的过程：

   从问题的某一初始解出发;

    while 能朝给定总目标前进一步 do

    求出可行解的一个解元素;

    由所有解元素组合成问题的一个可行解。

贪心选择性质： 

    所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，换句话说，当考虑做何种选择的时候，我们只考虑对当前问题最佳的选择而不考虑子问题的结果。这是贪心算法可行的第一个基本要素。贪心算法以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。

最优子结构性质：

/ * 活动时间安排 */ @Test public void testArrangeActivity() { int[] start = { 
  1, 3, 0, 5, 3, 5, 6, 8, 8, 2, 12}; int[] end = { 
  4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14}; List 
  
    results = arrangeActivity(start, end); 
   for ( 
   int i = 
   0; i < results.size(); i++) { 
   int index = results.get(i); System.out.println( 
   "开始时间:" + start[index] + 
   ",结束时间:" + end[index]); } } 
   / * 活动安排 * * @param s 开始时间 * @param e 结束时间 * @return */ 
   public List 
    
    arrangeActivity( 
    int[] s, 
    int[] e) { 
    int total = s.length; 
    int endFlag = e[ 
    0]; List 
    
      results = 
     new ArrayList<>(); results.add( 
     0); 
     for ( 
     int i = 
     0; i < total; i++) { 
     if (s[i] > endFlag) { results.add(i); endFlag = e[i]; } } 
     return results; } 
     
    
  

[找零钱问题]假如老板要找给我99分钱，他有上面的面值分别为25，10，5，1的硬币数，为了找给我最少的硬币数，那么他是不是该这样找呢，先看看该找多少个25分的，诶99／25＝3，好像是3个，要是4个的话，我们还得再给老板一个1分的，我不干，那么老板只能给我3个25分的拉，由于还少给我24，所以还得给我2个10分的和4个1分。

@Test public void testGiveMoney() { //找零钱 int[] m = { 
  25, 10, 5, 1}; int target = 99; int[] results = giveMoney(m, target); System.out.println(target + "的找钱方案:"); for (int i = 0; i < results.length; i++) { System.out.println(results[i] + "枚" + m[i] + "面值"); } } public int[] giveMoney(int[] m, int target) { int k = m.length; int[] num = new int[k]; for (int i = 0; i < k; i++) { num[i] = target / m[i]; target = target % m[i]; } return num; }

[背包问题]有一个背包，背包容量是M=150。有7个物品，物品可以分割成任意大小。 
要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。 
物品 A B C D E F G 
重量 35 30 60 50 40 10 25 
价值 10 40 30 50 35 40 30 
记得当时学算法的时候，就是这个例子，可以说很经典。 
分析： 
目标函数： ∑pi最大 
约束条件是装入的物品总重量不超过背包容量，即∑wi<=M( M=150) 
（1）根据贪心的策略，每次挑选价值最大的物品装入背包，得到的结果是否最优？ 
（2）每次挑选所占重量最小的物品装入是否能得到最优解？ 
（3）每次选取单位重量价值最大的物品，成为解本题的策略? 
贪心算法是很常见的算法之一，这是由于它简单易行，构造贪心策略简单。但是，它需要证明后才能真正运用到题目的算法中。一般来说，贪心算法的证明围绕着整个问题的最优解一定由在贪心策略中存在的子问题的最优解得来的。 
对于本例题中的3种贪心策略，都无法成立，即无法被证明，解释如下： 
（1）贪心策略：选取价值最大者。反例： 
W=30 
物品：A B C 
重量：28 12 12 
价值：30 20 20 
根据策略，首先选取物品A，接下来就无法再选取了，可是，选取B、C则更好。 
（2）贪心策略：选取重量最小。它的反例与第一种策略的反例差不多。 
（3）贪心策略：选取单位重量价值最大的物品。反例： 
W=30 
物品：A B C 
重量：28 20 10 
价值：28 20 10 
根据策略，三种物品单位重量价值一样，程序无法依据现有策略作出判断，如果选择A，则答案错误。 
值得注意的是，贪心算法并不是完全不可以使用，贪心策略一旦经过证明成立后，它就是一种高效的算法。比如，求最小生成树的Prim算法和Kruskal算法都是漂亮的贪心算法。 

@Test public void testMoveCard() { //总共4堆 int heap = 4; // int[] cards = {9, 8, 17, 6}; int[] cards = { 
  10, 10, 20, 0}; int count = moveCards(cards, heap); System.out.println("移动次数:" + count); for (int i = 0; i < cards.length; i++) { System.out.println("第" + (i + 1) + "堆牌数:" + cards[i]); } } / * 均分纸牌 * @param cards * @param heap * @return */ public int moveCards(int[] cards, int heap) { //总牌数 int sum = 0; for (int i = 0; i < cards.length; i++) { sum += cards[i]; } //每堆平均牌数 int avg = sum / heap; //移动次数 int count = 0; for (int i = 0; i < cards.length; i++) { if(cards[i] != avg) { int moveCards = cards[i] - avg; cards[i] -= moveCards; cards[i + 1] += moveCards; count++; } } return count; }

• 利用贪心算法解题，需要解决两个问题： 

［最大整数］设有n个正整数，将它们连接成一排，组成一个最大的多位整数。 
例如：n=3时，3个整数13，312，343，连成的最大整数为。 
又如：n=4时，4个整数7，13，4，246，连成的最大整数为。 
输入：n 
N个数 
输出：连成的多位数 
算法分析：此题很容易想到使用贪心法，在考试时有很多同学把整数按从大到小的顺序连接起来，测试题目的例子也都符合，但最后测试的结果却不全对。按这种标准，我们很容易找到反例：12，121应该组成12121而非12112，那么是不是相互包含的时候就从小到大呢？也不一定，如12，123就是12312而非12123，这种情况就有很多种了。是不是此题不能用贪心法呢？ 
其实此题可以用贪心法来求解，只是刚才的标准不对，正确的标准是：先把整数转换成字符串，然后在比较a+b和b+a，如果a+b>=b+a，就把a排在b的前面，反之则把a排在b的后面。

@Test public void testMaxNum() { //有n个正整数，将它们连接成一排，组成一个最大的多位整数 //12112错误 //12121正解 // int[] nums = {12, 121}; int[] nums = { 
  12, 123}; String result = maxNum(nums); System.out.println("组成最大整数:" + result); } / * 根据给定的整数组成最大的多位数 * @param nums */ public String maxNum(int[] nums) { String result = ""; for (int i = 0; i < nums.length; i++) { String num1 = nums[i] + ""; for (int j = 1; j < nums.length; j++) { String num2 = nums[j] + ""; if ((num1 + num2).compareTo(num2 + num1) < 0) { int temp = nums[j]; nums[j] = nums[i]; nums[i] = temp; } } } for (int i = 0; i < nums.length; i++) { result += nums[i]; } return result; }

贪心算法所作的选择可以依赖于以往所作过的选择，但决不依赖于将来的选择，也不依赖于子问题的解，因此贪心算法与其他算法相比具有一定的速度优势。如果一个问题可以同时用几种方法解决，贪心算法应该是最好的选择之一。