likes
comments
collection

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

作者站长头像
站长
· 阅读数 11

本文正在参加「金石计划 . 瓜分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万现金大奖」