贪心算法+动态规划｜眼光不同决定深度不同

你的名字 2023-10-03 21:35 27阅读 0赞

## 前言 ##

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

## 简介 ##

*  贪心算法指的是总是能够实现局部最优解。啥意思呢？就是说在每一步场景下选择最优解，不考虑全局是否能够达成最优解。

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

*  接下来我们通过不同场景来分别体会下，`动态规划` 和 `贪心算法` 的区别吧。从而更加深刻的理解 `贪心` 为何物？ 为什么贪心只能实现`局部最优解` 。

## 场景 ##

### [零钱兑换][Link 1] ###

#### 题目描述 ####

给你一个整数数组 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))。

![format_png][]

> > 例子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
     返回将所有筹码移动到同一位置上所需要的 最小代价 。
    复制代码

![format_png 1][]

#### 解题思路 ####

*  所谓算法其实也是前人总结出来的经验罢了。初看毫无头绪，再看仍无头绪这就是算法的魅力，当我们知道此题可以通过 `贪心` 来解决时就有了头绪了。
 *  首先通过题目描述我们能够得处一下结论：
    
     *  每次仅能移动一个筹码
     *  每次移动范围介于1～2之间
     *  移动2步长，无代价
     *  移动1步长，则付出1代价
 *  移动2步无需付出代价，意味着我们可以将筹码分成两组，组内成员所在位置索引差值皆为 `2` 。最终只需要考虑哪组需要合并即可。

![format_png 2][]

*  因为移动两步时无需代价的，则按照上面分组后，组内合并则是无需付出代价的。合并后如下

![format_png 3][]

*  到了这里我们只需要考虑 `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;
         }
    复制代码

![format_png 4][]

### 装箱子 ###

#### 题目描述 ####

请你将一些箱子装在 一辆卡车 上。给你一个二维数组 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.**只能求满足某些约束条件的可行解的范围**

[Link 1]: https://link.juejin.cn?target=https%3A%2F%2Fleetcode.cn%2Fproblems%2Fcoin-change%2F
[format_png]: https://img-blog.csdnimg.cn/img_convert/00a9eddc51188fc36cd1fd538720160d.webp?x-oss-process=image/format,png
[format_png 1]: https://img-blog.csdnimg.cn/img_convert/56b4f2ee156d9ba0fb2b97139559c808.webp?x-oss-process=image/format,png
[format_png 2]: https://img-blog.csdnimg.cn/img_convert/61b143736ee47825d37a147f8a9077a7.webp?x-oss-process=image/format,png
[format_png 3]: https://img-blog.csdnimg.cn/img_convert/f661c0c1bdc6d0652cf872c59999b9f6.webp?x-oss-process=image/format,png
[format_png 4]: https://img-blog.csdnimg.cn/img_convert/cd8de6708baf9902e39c9a48dd99c232.webp?x-oss-process=image/format,png