贪心算法 Greedy Algroithm
贪心算法简介
贪心算法是一种在每一步选择中都采取在当前看来最好选择的算法。它的基本思想是从问题的某个初始解出发,通过一步步地进行,根据某个优化测度,每一步都要确保能获得局部最优解。贪心算法的特点是一步一步地进行,常以当前情况为基础根据某个优化测度做最优选择,而不考虑各种可能的整体情况,省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪心算法采用自顶向下的方法,以迭代的方式做出相继贪心的选择,可得到问题的一个最优解。虽然每一步上都要保证能获得局部最优解,但由此产生的全局解不一定是最优的,所以贪心算法不要回溯。
贪心算法的应用场景
贪心算法的应用非常广泛,包括但不限于最短路径问题、单位密度问题。这些问题的共同特点是可以通过贪婪选择属性与最优子结构属性,利用贪心算法解决。贪婪选择属性指的是通过在每个步骤中选择最优选择,可以得到一个全局(总体)最优解。
贪心算法的经典例子
1.找零钱问题(Greedy Chang-Making Problem)
假设有一定面值的纸币和硬币,当要找零钱时,贪心算法会选择最大面值的纸币和硬币,当要找零钱时,贪心算法会选择最大面值的纸币或硬币,直到零钱找完。
import java.util.Arrays; public class GreedyAlgorithm { public static void main(String[] args) { int totalAmount = 16; int[] coins = {1, 2, 5, 10}; int[] change = getChange(totalAmount, coins); System.out.println("Change: " + Arrays.toString(change)); } public static int[] getChange(int totalAmount, int[] coins) { int[] change = new int[coins.length]; int remainingAmount = totalAmount; for (int i = coins.length - 1; i >= 0; i--) { int numCoins = remainingAmount / coins[i]; change[i] = numCoins; remainingAmount -= numCoins * coins[i]; } return change; } }
2.区间调度问题(Interval Scheduling Problem)
假设有一系列的任务需要在特定时间完成,每个任务都有一个开始时间和结束时间,贪心算法会优先选择结束时间最早的任务,然后选择下一个结束时间最早的任务,一次类推。
区间调度问题是指给定一组区间,找到能够完全覆盖这些区间的最少的区间数。这个问题可以使用贪心算法来解决。
贪心算法的思路是,先按照区间的结束时间进行排序,然后从第一个区间开始遍历,依次选取结束时间最早的区间,并且这个区间的开始时间要晚于前一个区间的结束时间。这样就可以保证选取的区间数最少。
下面是用Java实现的代码:
import java.util.Arrays; import java.util.Comparator; public class IntervalSchedule { public static int intervalSchedule(int[][] intervals) { //按结束时间对区间进行排序 Arrays.sort(intervals, Comparator.comparingInt(a -> a[1])); int count = 1; //选取的区间数 int end = intervals[0][1]; //当前选择的区间的结束时间 for (int i = 1; i = end) { //如果当前区间的开始时间晚于前一个区间的结束时间,可以选择这个区间 count++; end = intervals[i][1]; } } return count; } public static void main(String[] args) { int[][] intervals = {{1, 3}, {2, 4}, {3, 6}, {4, 7}, {5, 8}}; int result = intervalSchedule(intervals); System.out.println("最少的区间数为:" + result); } }
运行结果为:
最少的区间数为:3
注意,这里假设输入的区间数组是已经合法的,即每个区间的开始时间都小于结束时间。如果区间数组未按照开始时间进行排序,可以先进行排序再使用贪心算法。
3.分数背包问题(Fractional Knapsack Problem)
假设有一系列物品和一个背包,每个物品有自己的重量和价值,贪心算法会先选择性价比最高的物品放入背包,直到背包装满或者物品用完。
import java.util.ArrayList; import java.util.Comparator; import java.util.List; class Item { int weight; int value; public Item(int weight, int value) { this.weight = weight; this.value = value; } } class FractionalKnapsack { public static double getMaxValue(List items, int capacity) { // 排序,按照单位价值从高到低排序 items.sort(Comparator.comparingDouble(o -> (double) o.value / o.weight)); double totalValue = 0; for (Item item : items) { if (capacity >= item.weight) { // 如果背包容量可以装下当前物品,则装入整个物品 totalValue += item.value; capacity -= item.weight; } else { // 否则,计算当前物品的单位价值,装入剩余容量的物品 totalValue += item.value * ((double) capacity / item.weight); break; } } return totalValue; } public static void main(String[] args) { List items = new ArrayList(); items.add(new Item(10, 60)); items.add(new Item(20, 100)); items.add(new Item(30, 120)); int capacity = 50; double maxValue = getMaxValue(items, capacity); System.out.println("最大价值为:" + maxValue); } }
4.最小生成树问题(Minimum Spanning Tree Problem)
假设有一张图,贪心算法会先选择连接两个点之间最短的边,然后选择下一个最短的边,直到所有的点都被连接。
贪心算法解决最小生成树问题的一种实现方式是使用Prim算法。以下是一个使用Java语言实现的Prim算法示例代码:
import java.util.*; class PrimMST { private int V; // 图的顶点数 private int[][] graph; // 图的邻接矩阵表示 public PrimMST(int v, int[][] graph) { V = v; this.graph = graph; } // 寻找最小生成树 public void findMST() { boolean[] visited = new boolean[V]; // 记录顶点是否访问过 int[] parent = new int[V]; // 记录最小生成树的父节点 int[] key = new int[V]; // 记录顶点到最小生成树的最小权值 // 初始化key数组 Arrays.fill(key, Integer.MAX_VALUE); // 第一个顶点作为最小生成树的根节点 key[0] = 0; parent[0] = -1; for (int i = 0; i这是一个简单的Prim算法实现,假设图的顶点数为5,使用邻接矩阵表示图的连接关系。在findMST()方法中,我们使用一个visited数组来记录顶点是否已经访问过,使用parent数组来记录最小生成树的父节点,使用key数组来记录顶点到最小生成树的最小权值。在每次循环找到key值最小的顶点后,我们将其标记为已访问,并更新其相邻顶点的key值和parent值。最后,输出最小生成树的边和权值。
在main()方法中,我们使用一个邻接矩阵来表示图,并创建一个PrimMST对象来求解最小生成树。运行代码后,将输出最小生成树的边和权值。
5.哈夫曼编码问题(Huffman Coding Problem)
假设有一系列的字符和它们对应的频率,在使用最少的比特数来编码字符的同时,贪心算法会优先选择频率最高的字符编码长度最短。
下面是用Java实现贪心算法哈夫曼编码的示例代码:
import java.util.PriorityQueue; class HuffmanTreeNode implements Comparable { int frequency; char data; HuffmanTreeNode left, right; public HuffmanTreeNode(char data, int frequency) { this.data = data; this.frequency = frequency; } @Override public int compareTo(HuffmanTreeNode node) { return this.frequency - node.frequency; } } public class HuffmanEncoding { public static void main(String[] args) { String input = "Hello, world!"; HuffmanTreeNode root = buildHuffmanTree(input); String encodedString = encode(input, root); String decodedString = decode(encodedString, root); System.out.println("Input: " + input); System.out.println("Encoded String: " + encodedString); System.out.println("Decoded String: " + decodedString); } public static HuffmanTreeNode buildHuffmanTree(String input) { int[] frequencyTable = new int[256]; for (char c : input.toCharArray()) { frequencyTable[c]++; } PriorityQueue priorityQueue = new PriorityQueue(); for (int i = 0; i 0) { priorityQueue.add(new HuffmanTreeNode((char) i, frequencyTable[i])); } } while (priorityQueue.size() > 1) { HuffmanTreeNode leftNode = priorityQueue.poll(); HuffmanTreeNode rightNode = priorityQueue.poll(); HuffmanTreeNode newNode = new HuffmanTreeNode('\0', leftNode.frequency + rightNode.frequency); newNode.left = leftNode; newNode.right = rightNode; priorityQueue.add(newNode); } return priorityQueue.poll(); } public static String encode(String input, HuffmanTreeNode root) { StringBuilder sb = new StringBuilder(); for (char c : input.toCharArray()) { sb.append(getEncodedString(c, root)); } return sb.toString(); } private static String getEncodedString(char c, HuffmanTreeNode root) { if (root == null) { return ""; } if (root.data == c) { return ""; } String left = getEncodedString(c, root.left); if (left != null) { return "0" + left; } String right = getEncodedString(c, root.right); if (right != null) { return "1" + right; } return null; } public static String decode(String encodedString, HuffmanTreeNode root) { StringBuilder sb = new StringBuilder(); HuffmanTreeNode currentNode = root; for (char c : encodedString.toCharArray()) { if (c == '0') { currentNode = currentNode.left; } else if (c == '1') { currentNode = currentNode.right; } if (currentNode.data != '\0') { sb.append(currentNode.data); currentNode = root; } } return sb.toString(); } }此代码实现了一个HuffmanEncoding类,其中buildHuffmanTree方法用于构建Huffman树,encode方法用于将字符串编码为Huffman编码,decode方法用于将Huffman编码解码为原始字符串。
在main方法中,我们首先创建一个HuffmanEncoding对象,并将要编码的字符串作为输入进行编码。然后,我们将编码后的字符串进行解码,并将结果打印出来。