明天再讲一篇对于利用贪婪算法解决的题目。
一、金条切割问题
1、题目形容
一块金条切成两半，是须要破费和长度数值一样的铜板的。比方长度为20的金条，不管怎么切，都要花费20个铜板。一群人想整分整块金条，怎么分最省铜板？输出一个数组，返回宰割的最小代价。
例如：
给定数组{10,20,30}，代表一共三个人， 整块金条长度为10 + 20 + 30 = 60，金条要分成10, 20, 30三个局部（不思考程序）。
如果先把长度60的金条分成10和50，破费60；再把长度50的金条分成20和30，破费50;一共破费110铜板。
但如果先把长度60的金条分成30和30，破费60；再把长度30金条分成10和20，破费30；一共破费90铜板。
2、思路
（1）筹备一个小根堆。将数组放到这个小根堆里。
（2）每次弹出堆顶的两个数求和为A，将A再放回小根堆里。
（3）始终执行第2步，直到堆只剩一个数。最初，每一次第二步A的累加和即是最初的后果。
例如给定的金条长度为150，要分成10、20、30、40、50的块，最初破费的铜板数量即是上图中蓝色圆圈的和，即150+60+90+30=330。
也就是咱们代码求解的时候是从叶子往根求的，求完后再从根往叶子即是金条的切割程序，最初所有的叶子即是须要切成的块的大小。
3、代码
/** * @author Java和算法学习：周一 */public static int lessMoneySplitGold(int[] arr) { if (arr == null || arr.length == 0) { return 0; } // 筹备一个小根堆 Queue<Integer> queue = new PriorityQueue<>(); // 将所有数放到小根堆中 for (Integer s : arr) { queue.offer(s); } int result = 0; int current; while (queue.size() > 1) { // 每次弹出堆顶两个数求和 current = queue.poll() + queue.poll(); result += current; queue.offer(current); } return result;}蕴含对数器的所有代码地址：https://github.com/monday-pro/algorithm-study/blob/master/src/basic/greedy/LessMoneySplitGold.java
二、点灯问题
1、题目形容
给定一个字符串str，只由 'X' 和 '.' 两种字符形成。'X’ 示意墙，不能放灯，点亮不点亮都可；'.' 示意居民点，能够放灯，须要点亮。如果灯放在i地位，能够让 i-1，i 和 i+1 三个地位被点亮。返回如果点亮str中所有须要点亮的地位，至多须要几盏灯。
2、思路
（1）i 地位是 'X’，不论，来到 i + 1地位
（2）i 地位是 '.' ，i + 1是 'X’，i 地位须要放灯，来到 i + 2地位
（3）i 地位是 '.' ，i + 1是 '.'，i + 2是 '.'，i + 1 地位须要放灯，来到 i + 3地位（此步即是贪婪）
（4）i 地位是 '.' ，i + 1是 '.'，i + 2是 'X’，i 或 i + 1 地位须要放灯，来到 i + 3地位
3、代码
/** * @author Java和算法学习：周一 */public static int light(String light) { char[] lightChars = light.toCharArray(); // 曾经点灯的数量 int result = 0; // 以后来到的地位 int i = 0; while (i < lightChars.length) { // i 地位是 'X’，不论，来到 i + 1地位 if (lightChars[i] == 'X') { i++; } else { // i 地位是 '.' ，不论后续是怎么的，都要点一个灯 result++; if (i + 1 == lightChars.length) { break; } else { // i 地位是 '.' ，i + 1是 'X’，i 地位须要放灯，来到 i + 2地位 if (lightChars[i + 1] == 'X') { i = i + 2; } else { // i 地位是 '.' ，i + 1是 '.'，i + 2是 '.'，i + 1 地位须要放灯，来到 i + 3地位 // i 地位是 '.' ，i + 1是 '.'，i + 2是 'X’，i 或 i + 1 地位须要放灯，来到 i + 3地位 i = i + 3; } } } } return result;}蕴含对数器的所有代码地址：https://github.com/monday-pro/algorithm-study/blob/master/src/basic/greedy/Light.java
三、IPO问题
1、题目形容
链接：https://leetcode-cn.com/probl...
假如 力扣（LeetCode）行将开始 IPO 。为了以更高的价格将股票卖给风险投资公司，力扣心愿在 IPO 之前发展一些我的项目以减少其资本。因为资源无限，它只能在 IPO 之前实现最多 k 个不同的我的项目（串行做我的项目）。帮忙力扣设计实现最多 k 个不同我的项目后失去最大总资本的形式。
给你 n 个我的项目。对于每个我的项目 i ，它都有一个纯利润 profits[i] ，和启动该我的项目须要的最小资本 capital[i] 。
最后，你的资本为 w 。当你实现一个我的项目时，你将取得纯利润，且利润将被增加到你的总资本中。
总而言之，从给定我的项目中抉择 最多 k 个不同我的项目的列表，以最大化最终资本 ，并输入最终可取得的最多资本。
示例：
输出：k = 2, w = 0, profits = [1,2,3], capital = [0,1,1]
输入：4
解释：
因为你的初始资本为 0，你仅能够从 0 号我的项目开始。
在实现后，你将取得 1 的利润，你的总资本将变为 1。
此时你能够抉择开始 1 号或 2 号我的项目。
因为你最多能够抉择两个我的项目，所以你须要实现 2 号我的项目以取得最大的资本。
因而，输入最初最大化的资本，为 0 + 1 + 3 = 4。
2、思路
（1）筹备一个小根堆，以启动我的项目须要的资本为规范，将所有我的项目放到小根堆里
（2）筹备一个大根堆，把此时能做的我的项目从小根堆弹出来（领有的资本 >= 我的项目启动资本），以利润为规范将我的项目放到大根堆中，弹出大根堆中的堆顶我的项目A，k加1，w加A的利润
（3）始终执行第2步，直到达到k个我的项目，最初返回w。
和游戏中的打怪降级很像，每次都在本人打得过的怪中找到收益最大的，始终打，本人越来越强同时保障不会被战胜。
3、代码
/** * @author Java和算法学习：周一 */public static int findMaximizedCapital(int k, int w, int[] profits, int[] capital) { // 筹备一个小根堆 Queue<Program> capitalSmallQueue = new PriorityQueue<>((a, b) -> a.capital - b.capital); // 以启动我的项目须要的资本为规范，将所有我的项目放到小根堆中 for (int i = 0; i < profits.length; i++) { capitalSmallQueue.offer(new Program(profits[i], capital[i])); } // 筹备一个大根堆 // 放入的我的项目按我的项目的利润为规范 Queue<Program> profitsBigQueue = new PriorityQueue<>((a, b) -> b.profit - a.profit); for (int i = 0; i < k; i++) { // 以后领有的资本 >= 我的项目的启动资本，将我的项目从小根堆中弹出放到大根堆中 while (!capitalSmallQueue.isEmpty() && w >= capitalSmallQueue.peek().capital) { profitsBigQueue.offer(capitalSmallQueue.poll()); } // 可能资本有余，造成当初还能做我的项目然而大根堆没有我的项目给你做了 if (profitsBigQueue.isEmpty()) { return w; } w += profitsBigQueue.poll().profit; } return w;}public static class Program { public int profit; public int capital; public Program(int profit, int capital) { this.profit = profit; this.capital = capital; }}本题能够间接在LeetCode上测试，所以就不须要对数器来验证了。
4、测试后果
是不是发现贪婪算法的解法正如上一篇所说，难的在于贪婪策略的提出和证实，代码往往都比较简单，同时在面试时区分度也不是很高。