本文正在参与「金石方案 . 瓜分6万现金大奖」

前言

• 上大学那会有门课程叫做【算法与实践】, 算法配上 C++ 那感觉不要提多爽了。现在回想起来算法不局限于言语，只不过每个言语的语法纷歧算了， 可是算法的内涵逻辑都是相通的，今日咱们经过三个案列来了解分析下算法之一 【贪心算法】。

简介

• 贪心算法指的是总是能够完成部分最优解。啥意思呢？便是说在每一步场景下挑选最优解，不考虑大局是否能够达到最优解。

• 贪心算法与动态规划与许多相似之处。贪心算法适用的问题也是最优子结构。贪心算法与动态规划有一个显著的区别，便是贪心算法中，是以自顶向下的方法使用最优子结构的。贪心算法会先做挑选，在其时看起来是最优的挑选，然后再求解一个成果子问题，而不是先寻觅子问题的最优解，然后再做挑选。

• 接下来咱们经过不同场景来分别体会下，动态规划 和 贪心算法 的区别吧。从而愈加深入的了解 贪心 为何物？ 为什么贪心只能完成部分最优解 。

场景

零钱兑换

标题描绘

给你一个整数数组 coins ，表明不同面额的硬币；以及一个整数 amount ，表明总金额。
​
计算并回来能够凑成总金额所需的 最少的硬币个数 。假如没有任何一种硬币组合能组成总金额，回来-1 。
​
你能够认为每种硬币的数量是无限的。

• 翻译一下便是：假定1元、2元、5元、10元、20元、50元、100元的金额分别有c0, c1, c2, c3, c4, c5, c6。现在要用这些钱来支付K元，至少要用多少零钱兑换。

解题思路

• 本题不难发现最好的解法便是 动态规划 。 关于给定的数组中组成K元以来与数组中元素。S(K-1)=1+min(S(k-i))。

例子1：假定

coins = [1, 2, 5], amount = 11 则，当 i==0i==0 时无法用硬币组成，为 0 。当 i<0i<0 时，忽略 F(i)F(i)

F(i) 最小硬币数量 F(0) 0 //金额为0不能由硬币组成 F(1) 1 //F(1)=min(F(1-1),F(1-2),F(1-5))+1=1F(1)=min(F(1−1),F(1−2),F(1−5))+1=1 F(2) 1 //F(2)=min(F(2-1),F(2-2),F(2-5))+1=1F(2)=min(F(2−1),F(2−2),F(2−5))+1=1 F(3) 2 //F(3)=min(F(3-1),F(3-2),F(3-5))+1=2F(3)=min(F(3−1),F(3−2),F(3−5))+1=2 F(4) 2 //F(4)=min(F(4-1),F(4-2),F(4-5))+1=2F(4)=min(F(4−1),F(4−2),F(4−5))+1=2 … … F(11) 3 //F(11)=min(F(11-1),F(11-2),F(11-5))+1=3F(11)=min(F(11−1),F(11−2),F(11−5))+1=3 咱们能够看到问题的答案是经过子问题的最优解得到的。

AC代码

public class Solution {
  public int coinChange(int[] coins, int amount) {
    int max = amount + 1;
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, max);
    dp[0] = 0;
    for (int i = 1; i <= amount; i++) {
      for (int j = 0; j < coins.length; j++) {
        if (coins[j] <= i) {
          dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
         }
       }
     }
    return dp[amount] > amount ? -1 : dp[amount];
   }
}

玩筹码

标题描绘

有n个筹码。第 i 个筹码的方位是position[i]。
​
咱们需求把一切筹码移到同一个方位。在一步中，咱们能够将第 i 个筹码的方位从position[i]改变为:
​
position[i] + 2或position[i] - 2，此刻cost = 0
position[i] + 1或position[i] - 1，此刻cost = 1
回来将一切筹码移动到同一方位上所需求的 最小价值 。

解题思路

• 所谓算法其实也是前人总结出来的经验算了。初看毫无条理，再看仍无条理这便是算法的魅力，当咱们知道此题能够经过 贪心 来处理时就有了条理了。

• 首先经过标题描绘咱们能够得处一下结论：

  • 每次仅能移动一个筹码
  • 每次移动规模介于1～2之间
  • 移动2步长，无价值
  • 移动1步长，则付出1价值

• 移动2步无需付出价值，意味着咱们能够将筹码分成两组，组内成员所在方位索引差值皆为 2 。终究只需求考虑哪组需求兼并即可。

• 由于移动两步时无需价值的，则按照上面分组后，组内兼并则是无需付出价值的。兼并后如下

• 到了这儿咱们只需求考虑 A 组移向 B 组 仍是 B 组移动到 A 组 。这个判别根据则是看两组谁数量少。由于咱们还有一个限制便是每次仅移动一枚筹码。所以数量少的一组移动到数量多的一组，换句话说数量少的一组的数量即为整体的移动价值。

AC代码

class Solution {
  public int minCostToMoveChips(int[] position) {
    int even = 0, odd = 0;
    for (int pos : position) {
      if ((pos & 1) != 0) {
        odd++;
       } else {
        even++;
       }
     }
    return Math.min(odd, even);
   }
}

升级扩展

• 上面现已能够满意需求了。可是作为企业开发这么多年，早现已习惯了预留扩展功用了。加入之后咱们引进新的战略，移动三步价值这时候咱们能够这么修改代码

​
public int minCostToMoveChips(int[] position) {
    int step = 2;
    int[] stepArr = new int[step];
    for (int pos : position) {
      int posIndex=pos%step;
      stepArr[posIndex]++;
     }
    int min = stepArr[0];
    for (int i = 1; i < stepArr.length; i++) {
      if (min > stepArr[i]) {
        min = stepArr[i];
       }
     }
    return min;
   }

装箱子

标题描绘

请你将一些箱子装在 一辆卡车 上。给你一个二维数组 boxTypes ，其间 boxTypes[i] = [numberOfBoxesi, numberOfUnitsPerBoxi] ：
​
numberOfBoxesi 是类型 i 的箱子的数量。
numberOfUnitsPerBoxi 是类型 i每个箱子能够装载的单元数量。
整数 truckSize 表明卡车上能够装载 箱子 的 最大数量 。只需箱子数量不超越 truckSize ，你就能够挑选恣意箱子装到卡车上。
​
回来卡车能够装载单元 的 最大 总数。
​

解题思路

• 玩筹码 游戏中能够说是巧妙的运用贪心完成，或许咱们并未完全体会到贪心算法的效果。而 装箱子 则是彻彻底底的贪心算法的思路。 零钱兑换 我使用的是 动态规划 ，他的特点是自下而上的流程。上游的成果取决于下流的成果。
• 而 贪心算法 中则是 自上而下 , 比如本题中装箱子咱们假定 Fx 表明车厢装满X箱子后最大容量。很明显咱们只需求每次都挑选剩下箱子里容量最大的即可。
• 从两者挑选战略上也能够看得出来，贪心算法仅仅是部分最优解。而不是大局最优解。

AC代码

class Solution {
  public int maximumUnits(int[][] boxTypes, int truckSize) {
    Arrays.sort(boxTypes, (a, b) -> b[1] - a[1]);
    int res = 0;
    for (int[] boxType : boxTypes) {
      int numberOfBoxes = boxType[0];
      int numberOfUnitsPerBox = boxType[1];
      if (numberOfBoxes < truckSize) {
        res += numberOfBoxes * numberOfUnitsPerBox;
        truckSize -= numberOfBoxes;
       } else {
        res += truckSize * numberOfUnitsPerBox;
        break;
       }
     }
    return res;
   }
}

总结

1.不能保证求得的最后解是最佳的 2.不能用来求最大值或最小值的问题 3.只能求满意某些约束条件的可行解的规模

本文正在参与「金石方案 . 瓜分6万现金大奖」