貪心算法是什么？并不是字面上貪心的意思，而且選出目前最好的結(jié)果，這塊有個(gè)誤區(qū)，并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇。雖然貪心算法不能對(duì)所有問(wèn)題都能得到最優(yōu)的結(jié)果，但對(duì)許多問(wèn)題它能產(chǎn)生某個(gè)條件下整體的最優(yōu)解。如最小生成樹(shù)問(wèn)題等。在一些情況下，即使貪心算法不能得到整體最優(yōu)解，其最終結(jié)果卻是最優(yōu)解的相似或相近結(jié)果。

當(dāng)然，希望貪心算法得到的最終結(jié)果也是整體最優(yōu)的。雖然貪心算法不能對(duì)所有問(wèn)題都得到整體最優(yōu)解，但對(duì)許多問(wèn)題它能產(chǎn)生整體最優(yōu)解。如單源最短路經(jīng)問(wèn)題，最小生成樹(shù)問(wèn)題等。在一些情況下，即使貪心算法不能得到整體最優(yōu)解，其最終結(jié)果卻是最優(yōu)解的很好近似。

本篇通過(guò)基本思想和實(shí)例分析進(jìn)行貪心算法的了解和認(rèn)知，“貪心”二字顧名思義，因此其規(guī)律特征就是更加注重當(dāng)前的狀態(tài)，貪心法做出的選擇是對(duì)于當(dāng)前所處狀態(tài)的最優(yōu)選擇，它的解決問(wèn)題的視角是微觀(guān)的“局部”，而不是從全局宏觀(guān)的角度思考和看待問(wèn)題，根據(jù)這樣的性質(zhì)，要求貪心法解決的問(wèn)題有“無(wú)后效性”——當(dāng)前的決策不會(huì)影響到后續(xù)的決策，因?yàn)槿绻麊?wèn)題前后勾連緊密的話(huà)，會(huì)造成求解過(guò)程十分混亂。貪心算法常常用于組合優(yōu)化問(wèn)題，它的求解過(guò)程是多步判斷的過(guò)程。

一、貪心算法基本思想

（1）基本概念

1. 最自然智慧的算法；

2. 用一種局部最功利的標(biāo)準(zhǔn)，總是能做出在當(dāng)前看來(lái)是最好的選擇；

3. 難點(diǎn)在于證明局部最優(yōu)解最功利的標(biāo)準(zhǔn)可以得到全局最優(yōu)解；

4. 對(duì)于貪心算法的學(xué)習(xí)主要是以增加閱歷和經(jīng)驗(yàn)為主。

（2）簡(jiǎn)介

貪心算法（英語(yǔ)：greedy algorithm），是用計(jì)算機(jī)來(lái)模擬一個(gè)“貪心”的人做出決策的過(guò)程。這個(gè)人十分貪婪，每一步行動(dòng)總是按某種指標(biāo)選取最優(yōu)的操作。而且他目光短淺，總是只看眼前，并不考慮以后可能造成的影響。

可想而知，并不是所有的時(shí)候貪心法都能獲得最優(yōu)解，所以一般使用貪心法的時(shí)候，都要確保自己能證明其正確性。

二、貪心算法求解思路

（1）標(biāo)準(zhǔn)求解過(guò)程

1. 分析業(yè)務(wù)

2. 根據(jù)業(yè)務(wù)邏輯找到不同的貪心策略

3. 對(duì)于能舉出反例的策略，直接跳過(guò)，不能舉出反例的策略要證明有效性，這往往是比較困難的，要求數(shù)學(xué)能力很高且不具有統(tǒng)一的技巧性

（2）貪心算法解題套路

1. 實(shí)現(xiàn)一個(gè)不依靠貪心策略的解法X,可以用暴力嘗試

2. 腦補(bǔ)出貪心策略A,貪心策略B,貪心策略C…

3. 用解法X和對(duì)數(shù)器，用實(shí)驗(yàn)的方式得知哪個(gè)貪心策略正確

4. 不要去糾結(jié)貪心策略的證明

（3）常見(jiàn)題型及解題方法

1. 常見(jiàn)題型

“我們將 XXX 按照某某順序排序，然后按某種順序（例如從小到大）選擇?！?/p>

“我們每次都取 XXX 中最大/小的東西，并更新 XXX?！保ㄓ袝r(shí)「XXX 中最大/小的東西」可以?xún)?yōu)化，比如用優(yōu)先隊(duì)列維護(hù)）

二者的區(qū)別在于一種是離線(xiàn)的，先處理后選擇；一種是在線(xiàn)的，邊處理邊選擇。

2. 排序解法

用排序法常見(jiàn)的情況是輸入一個(gè)包含幾個(gè)（一般一到兩個(gè)）權(quán)值的數(shù)組，通過(guò)排序然后遍歷模擬計(jì)算的方法求出最優(yōu)值。

3. 后悔解法

思路時(shí)無(wú)論當(dāng)前的選項(xiàng)是否是最優(yōu)都接受，然后進(jìn)行比較，如果選擇之后不是最優(yōu)了，則反悔，舍棄這個(gè)選項(xiàng)，否則就正式接受，如此往復(fù)。

4. 與動(dòng)態(tài)規(guī)劃的區(qū)別

貪心算法與動(dòng)態(tài)規(guī)劃的不同在于它對(duì)每個(gè)子問(wèn)題的解決方案都做出選擇，不能回退。動(dòng)態(tài)規(guī)劃則會(huì)保存以前的運(yùn)算結(jié)果，并根據(jù)以前的結(jié)果對(duì)當(dāng)前進(jìn)行選擇，有回退功能。

三、貪心算法實(shí)例講解

例題一：居民樓路燈問(wèn)題

給定一個(gè)字符串str，只由‘X’和‘.’兩中國(guó)字符構(gòu)成。

‘X’表示墻，不能放燈，也不需要點(diǎn)亮，‘.’表示居民點(diǎn)，可以放燈，需要點(diǎn)亮。

如果燈放在i位置，可以讓i-1，i和i+1三個(gè)位置被點(diǎn)亮，返回如果點(diǎn)亮str中所需要點(diǎn)亮的位置，至少需要幾盞燈

例如： X…X…X…X. 需要至少5盞燈

package class09;

import java.util.HashSet;

public class Code02_Light {

        // 純暴力，用來(lái)做對(duì)數(shù)器。點(diǎn)的位置放燈和不放燈全排列
	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]位置呢？已經(jīng)做完決定了，那些放了燈的位置，存在lights里
	// 要求選出能照亮所有.的方案，并且在這些有效的方案中，返回最少需要幾個(gè)燈
	public static int process(char[] str, int index, HashSet<Integer> lights) {
	        // index來(lái)到結(jié)束位置的時(shí)候，當(dāng)前方案準(zhǔn)備結(jié)束
		if (index == str.length) { 
		        // 檢查當(dāng)前方案能否把所有居民樓都照亮
			for (int i = 0; i < str.length; i++) {
			        // 當(dāng)前位置是點(diǎn)的話(huà)
				if (str[i] != 'X') { 
					if (!lights.contains(i - 1) 
							&& !lights.contains(i) 
							&& !lights.contains(i + 1)) {
						return Integer.MAX_VALUE;
					}
				}
			}
			// 經(jīng)過(guò)for循環(huán)的檢查，任意點(diǎn)的位置都被照亮了，返回當(dāng)前有效的一種解
			return lights.size();
		} else { // str還沒(méi)結(jié)束
			// i位置不管是  X 或者 . 都可以選擇不放燈
			int no = process(str, index + 1, lights);
			int yes = Integer.MAX_VALUE;
			// 只有在i位置是.的時(shí)候，才可以選擇放燈
			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出發(fā)
		int index = 0;
		// 當(dāng)前燈的個(gè)數(shù)
		int light = 0;
		while (index < str.length) {
		        // 當(dāng)前i位置是X，直接跳到下一個(gè)位置做決定
			if (str[index] == 'X') {
				index++;
			// i 位置是 . 不管i+1是X還是.當(dāng)前區(qū)域需要放燈
			} else { 
				light++;
				// 接下來(lái)沒(méi)字符了，遍歷結(jié)束
				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!");
	}
}

例題二：哈夫曼樹(shù)問(wèn)題

一根金條切成兩半，是需要花費(fèi)和長(zhǎng)度值一樣的銅板的。

比如長(zhǎng)度為20的金條，不管怎么切，都需要花費(fèi)20個(gè)銅板。一群人想整分整塊金條，怎么分最省銅板？

例如：給定數(shù)組[10,20,30]，代表一共三個(gè)人，整塊金條長(zhǎng)度為60，金條要分成10,20,30三個(gè)部分。

如果先把長(zhǎng)度為60的金條分成10和50，花費(fèi)60；再把長(zhǎng)度為50的金條分成20和30，花費(fèi)50；一共需要花費(fèi)110個(gè)銅板。但是如果先把長(zhǎng)度為60的金條分成30和30，花費(fèi)60;再把30的金條分成10和20,花費(fèi)30；一共花費(fèi)90個(gè)銅板。

輸入一個(gè)數(shù)組，返回分割的最小代價(jià)。

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;
		// 窮舉任意兩個(gè)結(jié)合后的后續(xù)
		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;
	}

        // 貪心解法，建立一個(gè)小根堆，把所有數(shù)扔進(jìn)去
	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) {
		        // 每一次彈出兩個(gè)數(shù)，合并成一個(gè)數(shù)
		        // 合成的數(shù)一定輸非葉子節(jié)點(diǎn)
			cur = pQ.poll() + pQ.poll();
			// 把合成的數(shù)累加到sum中去
			sum += cur;
			// 把合成的數(shù)加入小根堆中
			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!");
	}

}

例題三：項(xiàng)目花費(fèi)和利潤(rùn)問(wèn)題

輸入：正數(shù)數(shù)組costs，正數(shù)數(shù)組profits,正數(shù)K,正數(shù)M

costs[i]表示i號(hào)項(xiàng)目的花費(fèi)，profits[i]表示i號(hào)項(xiàng)目在扣除花費(fèi)之后還能掙到的錢(qián)（利潤(rùn)）

K表示你只能串行的最多K個(gè)項(xiàng)目，M表示你的初始資金。

說(shuō)明：每做完一個(gè)項(xiàng)目，馬上獲得收益，可以支持你去做下一個(gè)項(xiàng)目。不能并行的做項(xiàng)目。

輸出：你最后獲得的最大錢(qián)數(shù)。

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) {
	        // 由花費(fèi)組織的小根堆
		PriorityQueue<Program> minCostQ = new PriorityQueue<>(new MinCostComparator());
		// 由利潤(rùn)組織的大根堆
		PriorityQueue<Program> maxProfitQ = new PriorityQueue<>(new MaxProfitComparator());
		
		// 把所有項(xiàng)目加入到由花費(fèi)組織的小根堆里
		for (int i = 0; i < Profits.length; i++) {
			minCostQ.add(new Program(Profits[i], Capital[i]));
		}
		// 做k輪項(xiàng)目
		for (int i = 0; i < K; i++) {
		        // 小根堆不為空，且堆頂?shù)幕ㄙM(fèi)被我當(dāng)前啟動(dòng)資金cover住
			while (!minCostQ.isEmpty() && minCostQ.peek().c <= W) {
			// 小根堆的堆頂扔到大根堆中去
			maxProfitQ.add(minCostQ.poll());
			}
			// 大根堆沒(méi)有可以做的項(xiàng)目，直接返回所有錢(qián)數(shù)
			if (maxProfitQ.isEmpty()) {
				return W;
			}
			// 大根堆不為空，堆頂元素的利潤(rùn)直接加到我們的總錢(qián)數(shù)上
			// 大根堆彈出堆頂元素
			W += maxProfitQ.poll().p;
		}
		return W;
	}

        // 項(xiàng)目實(shí)體類(lèi)
	public static class Program {
		public int p;
		public int c;

		public Program(int p, int c) {
			this.p = p;
			this.c = c;
		}
	}

        // 根據(jù)花費(fèi)組織的小根堆的比較器
	public static class MinCostComparator implements Comparator<Program> {

		@Override
		public int compare(Program o1, Program o2) {
			return o1.c - o2.c;
		}

	}

        // 根據(jù)利潤(rùn)組織的大根堆的比較器
	public static class MaxProfitComparator implements Comparator<Program> {

		@Override
		public int compare(Program o1, Program o2) {
			return o2.p - o1.p;
		}

	}

}

例題四：會(huì)議日程安排問(wèn)題

一些項(xiàng)目要占用一個(gè)會(huì)議室宣講，會(huì)議室不能同時(shí)容納兩個(gè)項(xiàng)目宣講。給你每個(gè)項(xiàng)目的開(kāi)始時(shí)間和結(jié)束時(shí)間，你來(lái)安排宣講的日程，要求會(huì)議室進(jìn)行宣講的場(chǎng)數(shù)最多。

返回最多的宣講場(chǎng)次。

思路：本題常見(jiàn)的幾種貪心策略，一種是按照誰(shuí)先開(kāi)始安排誰(shuí)，第二種按照持續(xù)時(shí)間短的先安排，第三種按照誰(shuí)先結(jié)束安排誰(shuí)。

通過(guò)驗(yàn)證，無(wú)需證明得出第三種貪心策略是正確的

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;
		}
	}

        // 暴力窮舉法，用來(lái)做對(duì)數(shù)器
	public static int bestArrange1(Program[] programs) {
		if (programs == null || programs.length == 0) {
			return 0;
		}
		return process(programs, 0, 0);
	}

	// 還剩什么會(huì)議都放在programs里
	// done 之前已經(jīng)安排了多少會(huì)議的數(shù)量
	// timeLine表示目前來(lái)到的時(shí)間點(diǎn)是多少
	
	// 目前來(lái)到timeLine的時(shí)間點(diǎn)，已經(jīng)安排了done多的會(huì)議，剩下的會(huì)議programs可以自由安排
	// 返回能安排的最多會(huì)議數(shù)量
	public static int process(Program[] programs, int done, int timeLine) {
	        // 沒(méi)有會(huì)議可以安排，返回安排了多少會(huì)議的數(shù)量
		if (programs.length == 0) {
			return done;
		}
		// 還有會(huì)議可以選擇
		int max = done;
		// 當(dāng)前安排的會(huì)議是什么會(huì)，每一個(gè)都枚舉
		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表示來(lái)到的時(shí)間點(diǎn)
		int timeLine = 0;
		// result表示安排了多少個(gè)會(huì)議
		int result = 0;
		// 由于剛才按照結(jié)束時(shí)間排序，當(dāng)前是按照誰(shuí)結(jié)束時(shí)間早的順序遍歷
		for (int i = 0; i < programs.length; i++) {
			if (timeLine <= programs[i].start) {
				result++;
				timeLine = programs[i].end;
			}
		}
		return result;
	}

        // 根據(jù)誰(shuí)的結(jié)束時(shí)間早排序
	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!");
	}

}