明天再讲一篇对于利用贪婪算法解决的题目。
一、金条切割问题
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、测试后果
是不是发现贪婪算法的解法正如上一篇所说，难的在于贪婪策略的提出和证实，代码往往都比较简单，同时在面试时区分度也不是很高。