【数据结构与算法】Greedy Algorithm

1) 贪心例子

称之为贪心算法或贪婪算法，核心思想是

1. 将寻找最优解的问题分为若干个步骤
2. 每一步骤都采用贪心原则，选取当前最优解
3. 因为没有考虑所有可能，局部最优的堆叠不一定让最终解最优

贪心算法是一种在每一步选择中都采取在当前状态下最好或最优(即最有利)的选择，从而希望导致结果是最好或最优的算法。这种算法通常用于求解优化问题，如最小生成树、背包问题等。

贪心算法的应用：

1. 背包问题：给定一组物品和一个背包，每个物品有一定的重量和价值，要求在不超过背包容量的情况下，尽可能多地装入物品。
2. 活动选择问题：在一个活动集合中，每次只能参加一个活动，问如何安排时间以最大化所有活动的收益。
3. 编辑距离问题：给定两个字符串，求它们之间的最小编辑距离(即将一个字符串转换为另一个字符串所需的最少操作次数)。
4. 网络流问题：给定一张有向图和一些起点和终点，求最大流量。
5. 找零问题：给定一定数量的硬币和需要找零的金额，求使用最少的硬币数。

常见问题及解答：

1. 贪心算法一定会找到最优解吗？
   答：不一定。贪心算法只保证在每一步选择中都是最优的，但并不能保证整个问题的最优解。例如，背包问题中的贪心算法可能会导致最后一个物品没有被装入背包。
2. 如何判断一个问题是否适合用贪心算法解决？
   答：一个问题如果可以用递归的方式分解成若干个子问题，且每个子问题都有明确的最优解(即局部最优),那么这个问题就可以用贪心算法解决。
3. 贪心算法的时间复杂度是多少？
   答：贪心算法的时间复杂度取决于问题的规模和具体实现。一般来说，对于规模较小的问题，贪心算法的时间复杂度可以达到O(nlogn)或O(n^{2);对于规模较大的问题，可能需要O(n}3)或更高。

几个贪心的例子

Dijkstra

// ...
while (!list.isEmpty()) {// 选取当前【距离最小】的顶点Vertex curr = chooseMinDistVertex(list);// 更新当前顶点邻居距离updateNeighboursDist(curr);// 移除当前顶点list.remove(curr);// 标记当前顶点已经处理过curr.visited = true;
}

• 没找到最短路径的例子：负边存在时，可能得不到正确解
• 问题出在贪心的原则会认为本次已经找到了该顶点的最短路径，下次不会再处理它（curr.visited = true）
• 与之对比，Bellman-Ford 并没有考虑局部距离最小的顶点，而是每次都处理所有边，所以不会出错，当然效率不如 Dijkstra

Prim

// ...
while (!list.isEmpty()) {// 选取当前【距离最小】的顶点Vertex curr = chooseMinDistVertex(list);// 更新当前顶点邻居距离updateNeighboursDist(curr);// 移除当前顶点list.remove(curr);// 标记当前顶点已经处理过curr.visited = true;
}

Kruskal

// ...
while (list.size() < size - 1) {// 选取当前【距离最短】的边Edge poll = queue.poll();// 判断两个集合是否相交int i = set.find(poll.start);int j = set.find(poll.end);if (i != j) { // 未相交list.add(poll);set.union(i, j); // 相交}
}

其它贪心的例子

• 选择排序、堆排序

• 拓扑排序

• 并查集合中的 union by size 和 union by height

• 哈夫曼编码

• 钱币找零，英文搜索关键字

  • change-making problem
  • find Minimum number of Coins

• 任务编排

• 求复杂问题的近似解

2) 零钱兑换问题

有几个解（零钱兑换 II）Leetcode 518

public class Leetcode518 {public int change(int[] coins, int amount) {return rec(0, coins, amount, new LinkedList<>(), true);}/*** 求凑成剩余金额的解的个数** @param index     当前硬币索引* @param coins     硬币面值数组* @param remainder 剩余金额* @param stack     -* @param first     -* @return 解的个数*/public int rec(int index, int[] coins, int remainder, LinkedList<Integer> stack, boolean first) {if(!first) {stack.push(coins[index]);}// 情况1：剩余金额 < 0 - 无解int count = 0;if (remainder < 0) {print("无解：", stack);}// 情况2：剩余金额 == 0 - 有解else if (remainder == 0) {print("有解：", stack);count = 1;}// 情况3：剩余金额 > 0 - 继续递归else {for (int i = index; i < coins.length; i++) {count += rec(i, coins, remainder - coins[i], stack, false);}}if (!stack.isEmpty()) {stack.pop();}return count;}private static void print(String prompt, LinkedList<Integer> stack) {ArrayList<Integer> print = new ArrayList<>();ListIterator<Integer> iterator = stack.listIterator(stack.size());while (iterator.hasPrevious()) {print.add(iterator.previous());}System.out.println(prompt + print);}public static void main(String[] args) {Leetcode518 leetcode = new Leetcode518();
//        int count = leetcode.coinChange(new int[]{1, 5, 10, 25}, 41);
//        int count = leetcode.coinChange(new int[]{25, 10, 5, 1}, 41);
//        int count = leetcode.coinChange(new int[]{5, 2, 1}, 5);
//        int count = leetcode.coinChange(new int[]{1, 2, 5}, 5);int count = leetcode.change(new int[]{15, 10, 1}, 21);System.out.println(count);}}

最优解（零钱兑换）- 穷举法 Leetcode 322

public class Leetcode322 {static int min = -1; // 需要的最少硬币数  2 3public int coinChange(int[] coins, int amount) {rec(0, coins, amount, new AtomicInteger(-1), new LinkedList<>(), true);return min;}// count 代表某一组合 钱币的总数public void rec(int index, int[] coins, int remainder, AtomicInteger count, LinkedList<Integer> stack, boolean first) {if (!first) {stack.push(coins[index]);}count.incrementAndGet(); // count++if (remainder == 0) {System.out.println(stack);if (min == -1) {min = count.get();} else {min = Integer.min(min, count.get());}} else if (remainder > 0) {for (int i = index; i < coins.length; i++) {rec(i, coins, remainder - coins[i], count, stack, false);}}count.decrementAndGet(); // count--if (!stack.isEmpty()) {stack.pop();}}public static void main(String[] args) {Leetcode322 leetcode = new Leetcode322();
//        int count = leetcode.coinChange(new int[]{5, 2, 1}, 5);int count = leetcode.coinChange(new int[]{25, 10, 5, 1}, 41);
//        int count = leetcode.coinChange(new int[]{2}, 3);
//        int count = leetcode.coinChange(new int[]{15, 10, 1}, 21);System.out.println(count);}
}

最优解（零钱兑换）- 贪心法 Leetcode 322

public class Leetcode322 {public int coinChange(int[] coins, int amount) {int remainder = amount;int count = 0;for (int coin : coins) {while (remainder - coin > 0) {remainder -= coin;count++;}if (remainder - coin == 0) {remainder = 0;count++;break;}}if (remainder > 0) {return -1;} else {return count;}}public static void main(String[] args) {Leetcode322 leetcode = new Leetcode322();int count = leetcode.coinChange(new int[]{5, 2, 1}, 5);
//        int count = leetcode.coinChange(new int[]{25, 10, 5, 1}, 41);
//        int count = leetcode.coinChange(new int[]{2}, 3);// 问题1 没有回头，导致找到更差的解
//        int count = leetcode.coinChange(new int[]{15, 10, 1}, 21);  // 问题2 没有回头，导致无解
//        int count = leetcode.coinChange(new int[]{15, 10}, 20);  System.out.println(count);}
}

3) Huffman 编码问题

问题引入

什么是编码？

简单说就是建立【字符】到【数字】的对应关系，如下面大家熟知的 ASC II 编码表，例如，可以查表得知字符【a】对应的数字是十六进制数【0x61】

\	00	01	02	03	04	05	06	07	08	09	0a	0b	0c	0d	0e	0f
0000	00	01	02	03	04	05	06	07	08	09	0a	0b	0c	0d	0e	0f
0010	10	11	12	13	14	15	16	17	18	19	1a	1b	1c	1d	1e	1f
0020	20	!	"	#	$	%	&	’	(	)	*	+	,	-	.	/
0030	0	1	2	3	4	5	6	7	8	9	:	;	<	=	>	?
0040	@	A	B	C	D	E	F	G	H	I	J	K	L	M	N	O
0050	P	Q	R	S	T	U	V	W	X	Y	Z	[	\	]	^	_
0060	`	a	b	c	d	e	f	g	h	i	j	k	l	m	n	o
0070	p	q	r	s	t	u	v	w	x	y	z	{	|	}	~	7f

注：一些直接以十六进制数字标识的是那些不可打印字符

传输时的编码

• java 中每个 char 对应的数字会占用固定长度 2 个字节
• 如果在传输中仍采用上述规则，传递 abbccccccc 这 10 个字符
  • 实际的字节为 0061006200620063006300630063006300630063（16进制表示）
  • 总共 20 个字节，不经济

现在希望找到一种最节省字节的传输方式，怎么办？

假设传输的字符中只包含 a，b，c 这 3 个字符，有同学重新设计一张二进制编码表，见下图

• 0 表示 a
• 1 表示 b
• 10 表示 c

现在还是传递 abbccccccc 这 10 个字符

• 实际的字节为 01110101010101010 （二进制表示）
• 总共需要 17 bits，也就是 2 个字节多一点，行不行？

不行，因为解码会出现问题，因为 10 会被错误的解码成 ba，而不是 c

• 解码后结果为 abbbababababababa，是错误的

怎么解决？必须保证编码后的二进制数字，要能区分它们的前缀（prefix-free）

用满二叉树结构编码，可以确保前缀不重复

• 向左走 0，向右走 1
• 走到叶子字符，累计起来的 0 和 1 就是该字符的二进制编码

再来试一遍

• a 的编码 0
• b 的编码 10
• c 的编码 11

现在还是传递 abbccccccc 这 10 个字符

• 实际的字节为 0101011111111111111（二进制表示）
• 总共需要 19 bits，也是 2 个字节多一点，并且解码没有问题了，行不行？

这回解码没问题了，但并非最少字节，因为 c 的出现频率高（7 次）a 的出现频率低（1 次），因此出现频率高的字符编码成短数字更经济

考察下面的树

• 00 表示 a
• 01 表示 b
• 1 表示 c

现在还是传递 abbccccccc 这 10 个字符

• 实际的字节为 000101 1111111 （二进制表示）
• 总共需要 13 bits，这棵树就称之为 Huffman 树
• 根据 Huffman 树对字符和数字进行编解码，就是 Huffman 编解码

Huffman 树

public class HuffmanTree {/*Huffman 树的构建过程1. 将统计了出现频率的字符，放入优先级队列2. 每次出队两个频次最低的元素，给它俩找个爹3. 把爹重新放入队列，重复 2~34. 当队列只剩一个元素时，Huffman 树构建完成*/static class Node {Character ch; // 字符int freq;     // 频次Node left;Node right;String code;  // 编码public Node(Character ch) {this.ch = ch;}public Node(int freq, Node left, Node right) {this.freq = freq;this.left = left;this.right = right;}int freq() {return freq;}boolean isLeaf() {return left == null;}@Overridepublic String toString() {return "Node{" +"ch=" + ch +", freq=" + freq +'}';}}String str;Map<Character, Node> map = new HashMap<>();public HuffmanTree(String str) {this.str = str;// 功能1：统计频率char[] chars = str.toCharArray();for (char c : chars) {/*if (!map.containsKey(c)) {map.put(c, new Node(c));}Node node = map.get(c);node.freq++;*/Node node = map.computeIfAbsent(c, Node::new);node.freq++;}// 功能2: 构造树PriorityQueue<Node> queue = new PriorityQueue<>(Comparator.comparingInt(Node::freq));queue.addAll(map.values());while (queue.size() >= 2) {Node x = queue.poll();Node y = queue.poll();int freq = x.freq + y.freq;queue.offer(new Node(freq, x, y));}Node root = queue.poll();// 功能3：计算每个字符的编码, 功能4：字符串编码后占用 bitsint sum = dfs(root, new StringBuilder());for (Node node : map.values()) {System.out.println(node + " " + node.code);}System.out.println("总共会占用 bits:" + sum);}private int dfs(Node node, StringBuilder code) {int sum = 0;if (node.isLeaf()) {node.code = code.toString();sum = node.freq * code.length();} else {sum += dfs(node.left, code.append("0"));sum += dfs(node.right, code.append("1"));}if (code.length() > 0) {code.deleteCharAt(code.length() - 1);}return sum;}public static void main(String[] args) {new HuffmanTree("abbccccccc");}
}

注意

• Node::new 是一个 Function，根据 key（即字符）生成 Node 对象
• 对应的是 public Node(Character ch) 有参构造

Huffman 编解码

补充两个方法，注意为了简单期间用了编解码都用字符串演示，实际应该按 bits 编解码

public class HuffmanTree {// ...// 编码public String encode() {char[] chars = str.toCharArray();StringBuilder sb = new StringBuilder();for (char c : chars) {sb.append(map.get(c).code);}return sb.toString();}// 解码public String decode(String str) {/*从根节点，寻找数字对应的字符数字是 0 向左走数字是 1 向右走如果没走到头，每走一步数字的索引 i++走到头就可以找到解码字符，再将 node 重置为根节点*/char[] chars = str.toCharArray();int i = 0;StringBuilder sb = new StringBuilder();Node node = root;while (i < chars.length) {if (!node.isLeaf()) { // 非叶子if(chars[i] == '0') { // 向左走node = node.left;} else if(chars[i] == '1') { // 向右走node = node.right;}i++;}if (node.isLeaf()) {sb.append(node.ch);node = root;}}return sb.toString();}@SuppressWarnings("all")public static void main(String[] args) {HuffmanTree tree = new HuffmanTree("abbccccccc");String encoded = tree.encode();System.out.println(encoded);System.out.println(tree.decode(encoded));}
}

注意

• 循环中非叶子节点 i 要自增，但叶子节点 i 暂不自增
• 第一个非叶子的 if 判断结束后，仍需要第二个叶子的 if 判断，因为在第一个 if 内 node 发生了变化

相关题目

题目编号	题目标题	算法思路
1167（Plus 题目）	连接棒材的最低费用	Huffman 树、贪心

参考解答

/*** <h3>连接棒材的最低费用</h3>* <p>为了装修新房，你需要加工一些长度为正整数的棒材。如果要将长度分别为 X 和 Y 的两根棒材连接在一起，你需要支付 X + Y 的费用。 返回讲所有棒材连成一根所需要的最低费用。</p>*/
public class Leetcode1167 {/*举例 棒材为 [1,8,3,5]如果以如下顺序连接(非最优)- 1+8=9- 9+3=12- 12+5=17总费用为 9+12+17=38如果以如下顺序连接(最优)- 1+3=4- 4+5=9- 8+9=17总费用为 4+9+17=30*/int connectSticks(int[] sticks) {PriorityQueue<Integer> queue = new PriorityQueue<>();for (int stick : sticks) {queue.offer(stick);}int sum = 0;while (queue.size() >= 2) {Integer x = queue.poll();Integer y = queue.poll();int c = x + y;sum += c;queue.offer(c);}return sum;}public static void main(String[] args) {Leetcode1167 leetcode = new Leetcode1167();System.out.println(leetcode.connectSticks(new int[]{1, 8, 3, 5})); // 30System.out.println(leetcode.connectSticks(new int[]{2, 4, 3})); // 14}
}

4) 活动选择问题

public class ActivitySelectionProblem {/*要在一个会议室举办 n 个活动- 每个活动有它们各自的起始和结束时间- 找出在时间上互不冲突的活动组合，能够最充分利用会议室（举办的活动次数最多）例10   1   2   3   4   5   6   7   8   9|-------)|-------)|-------)例20   1   2   3   4   5   6   7   8   9|---)|---)|-----------------------)|-------)|---)|---------------)几种贪心策略1. 优先选择持续时间最短的活动0   1   2   3   4   5   6   7   8   9|---------------)|-------)|---------------)2. 优先选择冲突最少的活动0   1   2   3   4   5   6   7   8   9|-------)                                       3|-------)                                   4|-------)                                   4|-------)                                   4|-------)                               4|-------)                           2|-----------)                   4|-------)               4|-------)               4|-------)               4|-------)           33. 优先选择最先开始的活动0   1   2   3   4   5   6   7   8   9|-----------------------------------)|---)|---)|---)4. 优先选择最后结束的活动*/static class Activity {int index;int start;int finish;public Activity(int index, int start, int finish) {this.index = index;this.start = start;this.finish = finish;}@Overridepublic String toString() {return "Activity(" + index + ")";}}public static void main(String[] args) {Activity[] activities = new Activity[]{new Activity(0, 1, 3),new Activity(1, 2, 4),new Activity(2, 3, 5)};
//        Activity[] activities = new Activity[]{
//                new Activity(0, 1, 2),
//                new Activity(1, 3, 4),
//                new Activity(2, 0, 6),
//                new Activity(3, 5, 7),
//                new Activity(4, 8, 9),
//                new Activity(5, 5, 9)
//        };select(activities, activities.length);}public static void select(Activity[] activities, int n) {List<Activity> result = new ArrayList<>();int i, j;i = 0;result.add(activities[i]);for (j = 1; j < n; j++) {if (activities[j].start >= activities[i].finish) {result.add(activities[j]);i = j;}}System.out.println(result);}
}

无重叠区间-Leetcode 435

题目编号	题目标题	算法思路
435	无重叠区间	贪心

参考解答

// 下面代码为 Leetcode 435 题解
public int eraseOverlapIntervals(int[][] intervals) {Arrays.sort(intervals, Comparator.comparingInt(a -> a[1]));int i, j;i = 0;int count = 1;for (j = 1; j < intervals.length; j++) {if (intervals[j][0] >= intervals[i][1]) {i = j;count++;}}return intervals.length - count;
}

• 找到不重叠的最多的活动数（count），即活动选择问题原始需求
• 在此基础上，活动总数 - count，就是题目要的排除数量

5) 分数背包问题

贪心法

public class FractionalKnapsackProblem {/*1. n个物品都是液体，有重量和价值2. 现在你要取走 10升 的液体3. 每次可以不拿，全拿，或拿一部分，问最高价值是多少编号 重量(升) 价值0   4       24      水1   8       160     牛奶       选中 7/82   2       4000    五粮液     选中3   6       108     可乐4   1       4000    茅台       选中8140简化起见，给出的数据都是【价值/重量】能够整除，避免计算结果中出现小数，增加心算难度*/static class Item {int index;int weight;int value;public Item(int index, int weight, int value) {this.index = index;this.weight = weight;this.value = value;}int unitPrice() {return value / weight;}@Overridepublic String toString() {return "Item(" + index + ")";}}public static void main(String[] args) {Item[] items = new Item[]{new Item(0, 4, 24),new Item(1, 8, 160),new Item(2, 2, 4000),new Item(3, 6, 108),new Item(4, 1, 4000),};select(items, 10);}static void select(Item[] items, int total) {Arrays.sort(items, Comparator.comparingInt(Item::unitPrice).reversed());int remainder = total;int max = 0;for (Item item : items) {if (remainder - item.weight > 0) {max += item.value;remainder -= item.weight;} else {max += remainder * item.unitPrice();break;}}System.out.println("最高价值为：" + max);}}

6) 0-1 背包问题

贪心法

可能得不到最优解

public class KnapsackProblem {/*1. n个物品都是固体，有重量和价值2. 现在你要取走不超过 10克 的物品3. 每次可以不拿或全拿，问最高价值是多少编号 重量(g)  价值(元)0   1       1_000_000      钻戒一枚1   4       1600           黄金一块2   8       2400           红宝石戒指一枚3   5       30             白银一块*/static class Item {int index;int weight;int value;public Item(int index, int weight, int value) {this.index = index;this.weight = weight;this.value = value;}public int unitValue() {return value / weight;}@Overridepublic String toString() {return "Item(" + index + ")";}}public static void main(String[] args) {Item[] items = new Item[]{new Item(0, 1, 1_000_000),new Item(1, 4, 1600),new Item(2, 8, 2400),new Item(3, 5, 30)};select(items, 10);}static void select(Item[] items, int total) {Arrays.sort(items, Comparator.comparingInt(Item::unitValue).reversed());int max = 0; // 最大价值for (Item item : items) {System.out.println(item);if (total >= item.weight) { // 可以拿完total -= item.weight;max += item.value;} else { // 拿不完
//                max += total * item.unitValue();
//                break;}}System.out.println("最大价值是:" + max);}
}

贪心算法的局限

问题名称	是否能用贪心得到最优解	替换解法
Dijkstra(不存在负边)	✔️
Dijkstra(存在负边)	❌	Bellman-Ford
Prim	✔️
Kruskal	✔️
零钱兑换	❌	动态规划
Huffman 树	✔️
活动选择问题	✔️
分数背包问题	✔️
0-1 背包问题	❌	动态规划

7) Set cover problem

集合覆盖问题

本文，已收录于，我的技术网站 pottercoding.cn，有大厂完整面经，工作技术，架构师成长之路，等经验分享!