贪心算法是什么？并不是字面上贪心的意思，而且选出目前最好的结果，这块有个误区，并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。虽然贪心算法不能对所有问题都能得到最优的结果，但对许多问题它能产生某个条件下整体的最优解。如最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的相似或相近结果。
当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。
本篇通过基本思想和实例分析进行贪心算法的了解和认知，“贪心”二字顾名思义，因此其规律特征就是更加注重当前的状态，贪心法做出的选择是对于当前所处状态的最优选择，它的解决问题的视角是微观的“局部”，而不是从全局宏观的角度思考和看待问题，根据这样的性质，要求贪心法解决的问题有“无后效性”——当前的决策不会影响到后续的决策，因为如果问题前后勾连紧密的话，会造成求解过程十分混乱。贪心算法常常用于组合优化问题，它的求解过程是多步判断的过程。
一、贪心算法基本思想
（1）基本概念
1. 最自然智慧的算法；
2. 用一种局部最功利的标准，总是能做出在当前看来是最好的选择；
3. 难点在于证明局部最优解最功利的标准可以得到全局最优解；
4. 对于贪心算法的学习主要是以增加阅历和经验为主。
（2）简介
贪心算法（英语：greedy algorithm），是用计算机来模拟一个“贪心”的人做出决策的过程。这个人十分贪婪，每一步行动总是按某种指标选取最优的操作。而且他目光短浅，总是只看眼前，并不考虑以后可能造成的影响。
可想而知，并不是所有的时候贪心法都能获得最优解，所以一般使用贪心法的时候，都要确保自己能证明其正确性。
二、贪心算法求解思路
（1）标准求解过程
1. 分析业务
2. 根据业务逻辑找到不同的贪心策略
3. 对于能举出反例的策略，直接跳过，不能举出反例的策略要证明有效性，这往往是比较困难的，要求数学能力很高且不具有统一的技巧性
（2）贪心算法解题套路
1. 实现一个不依靠贪心策略的解法X,可以用暴力尝试
2. 脑补出贪心策略A,贪心策略B,贪心策略C…
3. 用解法X和对数器，用实验的方式得知哪个贪心策略正确
4. 不要去纠结贪心策略的证明
（3）常见题型及解题方法
1. 常见题型
“我们将 XXX 按照某某顺序排序，然后按某种顺序（例如从小到大）选择。”
“我们每次都取 XXX 中最大/小的东西，并更新 XXX。”（有时「XXX 中最大/小的东西」可以优化，比如用优先队列维护）
二者的区别在于一种是离线的，先处理后选择；一种是在线的，边处理边选择。
2. 排序解法
用排序法常见的情况是输入一个包含几个（一般一到两个）权值的数组，通过排序然后遍历模拟计算的方法求出最优值。
3. 后悔解法
思路时无论当前的选项是否是最优都接受，然后进行比较，如果选择之后不是最优了，则反悔，舍弃这个选项，否则就正式接受，如此往复。
4. 与动态规划的区别
贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择，不能回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。
三、贪心算法实例讲解
例题一：居民楼路灯问题
给定一个字符串str，只由‘X’和‘.’两中国字符构成。
‘X’表示墙，不能放灯，也不需要点亮，‘.’表示居民点，可以放灯，需要点亮。
如果灯放在i位置，可以让i-1，i和i+1三个位置被点亮，返回如果点亮str中所需要点亮的位置，至少需要几盏灯
例如： X…X…X…X. 需要至少5盏灯
package class09;
import java.util.HashSet;
public class Code02_Light {
// 纯暴力，用来做对数器。点的位置放灯和不放灯全排列
public static int minLight1(String road) {
if (road == null || road.length() == 0) {
return 0;
}
return process(road.toCharArray(), 0, new HashSet<>());
}
// str[index....]位置，自由选择放灯还是不放灯
// str[0..index-1]位置呢？已经做完决定了，那些放了灯的位置，存在lights里
// 要求选出能照亮所有.的方案，并且在这些有效的方案中，返回最少需要几个灯
public static int process(char[] str, int index, HashSet<Integer> lights) {
// index来到结束位置的时候，当前方案准备结束
if (index == str.length) {
// 检查当前方案能否把所有居民楼都照亮
for (int i = 0; i < str.length; i++) {
// 当前位置是点的话
if (str[i] != 'X') {
if (!lights.contains(i - 1)
&& !lights.contains(i)
&& !lights.contains(i + 1)) {
return Integer.MAX_VALUE;
}
}
}
// 经过for循环的检查，任意点的位置都被照亮了，返回当前有效的一种解
return lights.size();
} else { // str还没结束
// i位置不管是 X 或者 . 都可以选择不放灯
int no = process(str, index + 1, lights);
int yes = Integer.MAX_VALUE;
// 只有在i位置是.的时候，才可以选择放灯
if (str[index] == '.') {
lights.add(index);
yes = process(str, index + 1, lights);
lights.remove(index);
}
return Math.min(no, yes);
}
}
// 贪心解法
public static int minLight2(String road) {
char[] str = road.toCharArray();
// index从0出发
int index = 0;
// 当前灯的个数
int light = 0;
while (index < str.length) {
// 当前i位置是X，直接跳到下一个位置做决定
if (str[index] == 'X') {
index++;
// i 位置是 . 不管i+1是X还是.当前区域需要放灯
} else {
light++;
// 接下来没字符了，遍历结束
if (index + 1 == str.length) {
break;
} else {
// 如果i+1位置是X，在i位置放灯，去i+2位置做决定
if (str[index + 1] == 'X') {
index = index + 2;
// i位置是. i+1也是. 那么不管i+2是什么，都在i+1位置放灯，到i+3去做决定
} else {
index = index + 3;
}
}
}
}
return light;
}
// for test
public static String randomString(int len) {
char[] res = new char[(int) (Math.random() * len) + 1];
for (int i = 0; i < res.length; i++) {
res[i] = Math.random() < 0.5 ? 'X' : '.';
}
return String.valueOf(res);
}
public static void main(String[] args) {
int len = 20;
int testTime = 100000;
for (int i = 0; i < testTime; i++) {
String test = randomString(len);
int ans1 = minLight1(test);
int ans2 = minLight2(test);
if (ans1 != ans2) {
System.out.println("oops!");
}
}
System.out.println("finish!");
}
}例题二：哈夫曼树问题
一根金条切成两半，是需要花费和长度值一样的铜板的。
比如长度为20的金条，不管怎么切，都需要花费20个铜板。一群人想整分整块金条，怎么分最省铜板？
例如：给定数组[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个铜板。
输入一个数组，返回分割的最小代价。
package class09;
import java.util.PriorityQueue;
public class Code03_LessMoneySplitGold {
// 暴力解法
public static int lessMoney1(int[] arr) {
if (arr == null || arr.length == 0) {
return 0;
}
return process(arr, 0);
}
public static int process(int[] arr, int pre) {
if (arr.length == 1) {
return pre;
}
int ans = Integer.MAX_VALUE;
// 穷举任意两个结合后的后续
for (int i = 0; i < arr.length; i++) {
for (int j = i + 1; j < arr.length; j++) {
ans = Math.min(ans, process(copyAndMergeTwo(arr, i, j), pre + arr[i] + arr[j]));
}
}
return ans;
}
public static int[] copyAndMergeTwo(int[] arr, int i, int j) {
int[] ans = new int[arr.length - 1];
int ansi = 0;
for (int arri = 0; arri < arr.length; arri++) {
if (arri != i && arri != j) {
ans[ansi++] = arr[arri];
}
}
ans[ansi] = arr[i] + arr[j];
return ans;
}
// 贪心解法，建立一个小根堆，把所有数扔进去
public static int lessMoney2(int[] arr) {
PriorityQueue<Integer> pQ = new PriorityQueue<>();
for (int i = 0; i < arr.length; i++) {
pQ.add(arr[i]);
}
int sum = 0;
int cur = 0;
while (pQ.size() > 1) {
// 每一次弹出两个数，合并成一个数
// 合成的数一定输非叶子节点
cur = pQ.poll() + pQ.poll();
// 把合成的数累加到sum中去
sum += cur;
// 把合成的数加入小根堆中
pQ.add(cur);
}
return sum;
}
// for test
public static int[] generateRandomArray(int maxSize, int maxValue) {
int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
for (int i = 0; i < arr.length; i++) {
arr[i] = (int) (Math.random() * (maxValue + 1));
}
return arr;
}
public static void main(String[] args) {
int testTime = 100000;
int maxSize = 6;
int maxValue = 1000;
for (int i = 0; i < testTime; i++) {
int[] arr = generateRandomArray(maxSize, maxValue);
if (lessMoney1(arr) != lessMoney2(arr)) {
System.out.println("Oops!");
}
}
System.out.println("finish!");
}
}例题三：项目花费和利润问题
输入：正数数组costs，正数数组profits,正数K,正数M
costs[i]表示i号项目的花费，profits[i]表示i号项目在扣除花费之后还能挣到的钱（利润）
K表示你只能串行的最多K个项目，M表示你的初始资金。
说明：每做完一个项目，马上获得收益，可以支持你去做下一个项目。不能并行的做项目。
输出：你最后获得的最大钱数。
package class09;
import java.util.Comparator;
import java.util.PriorityQueue;
public class Code05_IPO {
public static int findMaximizedCapital(int K, int W, int[] Profits, int[] Capital) {
// 由花费组织的小根堆
PriorityQueue<Program> minCostQ = new PriorityQueue<>(new MinCostComparator());
// 由利润组织的大根堆
PriorityQueue<Program> maxProfitQ = new PriorityQueue<>(new MaxProfitComparator());
// 把所有项目加入到由花费组织的小根堆里
for (int i = 0; i < Profits.length; i++) {
minCostQ.add(new Program(Profits[i], Capital[i]));
}
// 做k轮项目
for (int i = 0; i < K; i++) {
// 小根堆不为空，且堆顶的花费被我当前启动资金cover住
while (!minCostQ.isEmpty() && minCostQ.peek().c <= W) {
// 小根堆的堆顶扔到大根堆中去
maxProfitQ.add(minCostQ.poll());
}
// 大根堆没有可以做的项目，直接返回所有钱数
if (maxProfitQ.isEmpty()) {
return W;
}
// 大根堆不为空，堆顶元素的利润直接加到我们的总钱数上
// 大根堆弹出堆顶元素
W += maxProfitQ.poll().p;
}
return W;
}
// 项目实体类
public static class Program {
public int p;
public int c;
public Program(int p, int c) {
this.p = p;
this.c = c;
}
}
// 根据花费组织的小根堆的比较器
public static class MinCostComparator implements Comparator<Program> {
@Override
public int compare(Program o1, Program o2) {
return o1.c - o2.c;
}
}
// 根据利润组织的大根堆的比较器
public static class MaxProfitComparator implements Comparator<Program> {
@Override
public int compare(Program o1, Program o2) {
return o2.p - o1.p;
}
}
}例题四：会议日程安排问题
一些项目要占用一个会议室宣讲，会议室不能同时容纳两个项目宣讲。给你每个项目的开始时间和结束时间，你来安排宣讲的日程，要求会议室进行宣讲的场数最多。
返回最多的宣讲场次。
思路：本题常见的几种贪心策略，一种是按照谁先开始安排谁，第二种按照持续时间短的先安排，第三种按照谁先结束安排谁。
通过验证，无需证明得出第三种贪心策略是正确的
package class09;
import java.util.Arrays;
import java.util.Comparator;
public class Code04_BestArrange {
public static class Program {
public int start;
public int end;
public Program(int start, int end) {
this.start = start;
this.end = end;
}
}
// 暴力穷举法，用来做对数器
public static int bestArrange1(Program[] programs) {
if (programs == null || programs.length == 0) {
return 0;
}
return process(programs, 0, 0);
}
// 还剩什么会议都放在programs里
// done 之前已经安排了多少会议的数量
// timeLine表示目前来到的时间点是多少
// 目前来到timeLine的时间点，已经安排了done多的会议，剩下的会议programs可以自由安排
// 返回能安排的最多会议数量
public static int process(Program[] programs, int done, int timeLine) {
// 没有会议可以安排，返回安排了多少会议的数量
if (programs.length == 0) {
return done;
}
// 还有会议可以选择
int max = done;
// 当前安排的会议是什么会，每一个都枚举
for (int i = 0; i < programs.length; i++) {
if (programs[i].start >= timeLine) {
Program[] next = copyButExcept(programs, i);
max = Math.max(max, process(next, done + 1, programs[i].end));
}
}
return max;
}
public static Program[] copyButExcept(Program[] programs, int i) {
Program[] ans = new Program[programs.length - 1];
int index = 0;
for (int k = 0; k < programs.length; k++) {
if (k != i) {
ans[index++] = programs[k];
}
}
return ans;
}
// 解法2：贪心算法
public static int bestArrange2(Program[] programs) {
Arrays.sort(programs, new ProgramComparator());
// timeline表示来到的时间点
int timeLine = 0;
// result表示安排了多少个会议
int result = 0;
// 由于刚才按照结束时间排序，当前是按照谁结束时间早的顺序遍历
for (int i = 0; i < programs.length; i++) {
if (timeLine <= programs[i].start) {
result++;
timeLine = programs[i].end;
}
}
return result;
}
// 根据谁的结束时间早排序
public static class ProgramComparator implements Comparator<Program> {
@Override
public int compare(Program o1, Program o2) {
return o1.end - o2.end;
}
}
// for test
public static Program[] generatePrograms(int programSize, int timeMax) {
Program[] ans = new Program[(int) (Math.random() * (programSize + 1))];
for (int i = 0; i < ans.length; i++) {
int r1 = (int) (Math.random() * (timeMax + 1));
int r2 = (int) (Math.random() * (timeMax + 1));
if (r1 == r2) {
ans[i] = new Program(r1, r1 + 1);
} else {
ans[i] = new Program(Math.min(r1, r2), Math.max(r1, r2));
}
}
return ans;
}
public static void main(String[] args) {
int programSize = 12;
int timeMax = 20;
int timeTimes = 1000000;
for (int i = 0; i < timeTimes; i++) {
Program[] programs = generatePrograms(programSize, timeMax);
if (bestArrange1(programs) != bestArrange2(programs)) {
System.out.println("Oops!");
}
}
System.out.println("finish!");
}
}| 2092 | 蓝桥杯算法训练VIP-Castles |
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：
一点编程也不会写的：零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码？手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程