前言

• 上大学那会有门课程叫做【算法与实践】, 算法配上 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 = 0position[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.只能求满足某些约束条件的可行解的范围