贪心算法几个经典例子java
贪心算法是一种常见的算法思想，它在多个领域中都有广泛的应用。本文将从贪心算法的基本原理、贪心算法的经典例子以及贪心算法在Java语言中的实现等多个角度分析贪心算法。
贪心算法的基本原理
贪心算法（Greedy Algorithm）是指每一步都只选择当前状态下的最优解，最终得到全局最优解的策略。贪心算法的核心思想是贪婪，即尽量选取当前最优解，以期达到整体最优解的目的。贪心算法不同于动态规划算法等其他算法，它不考虑后续步骤的结果，只关注当前状态下的最优解。
贪心算法的经典例子
1. 活动安排问题
问题描述：有n个活动，每个活动有一个开始时间和一个结束时间，不同活动之间时间不相交，问最多能安排多少活动。
贪心策略：按照结束时间从小到大排序，每次选择结束时间最早、与前面活动不冲突的活动。
Java代码实现：
public class ActivitySelector {
public static void main(String[] args) {
// 活动按结束时间从小到大排序
int[] str = {1, 3, 0, 5, 3, 5, 6, 8, 8, 2, 12};
int[] end = {4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14};
int n = end.length;
int i = 0, count = 1; // count 记录已安排的活动数
for (int j = 1; j < n; j++) {
if (end[i] <= str[j]) {
count++;
i = j;
}
}
System.out.println("最多可以安排"+count+"个活动。");
}
}
2. 分数背包问题
问题描述：有n件物品，每件物品都有一个重量和一个价值，现在有一个容量为c的背包，求能放进背包的最大价值。
贪心策略：按照物品单位重量的价值从高到低排序，每次优先选择单位重量价值最高的物品。
Java代码实现：
public class KnapsackProblem {
public static void main(String[] args) {
int c = 9; // 背包容量
int[] v = {3, 4, 5}; // 物品价值
int[] w = {2, 3, 4}; // 物品重量
int n = w.length;
double[] r = new double[n]; // 物品单位重量价值
for (int i = 0; i < n; i++) {
r[i] = (double) v[i]/w[i];
}
double profit = 0; // 最大价值
for (int i = 0; i < n; i++) {
int k = -1;
double maxr = 0;
// 找出单位重量价值最大的物品
for (int j = 0; j < n; j++) {
if (w[j] > 0 && r[j] > maxr) {
maxr = r[j];
k = j;
}
}
if (k == -1) break; // 物品已经全部装完
if (w[k] >= c) { // 物品只能部分装入背包
profit += maxr*c;
break;
} else {
profit += v[k];
c -= w[k];
w[k] = 0;
}
}
System.out.println("最大价值为"+profit+"。");
}
}
3. 哈夫曼编码
问题描述：设有n个权值，{w1,w2,…,wn}，构造一棵具有这n个权值的哈夫曼树，哈夫曼编码是将权值较大的字符（或单词）用较短的编码，权值较小的字符用较长的编码，使得编码后的字符总长度最短。
贪心策略：每次选择两个权值最小（即出现频率最高）的节点合并，并增加对应分支的编码前缀。
Java代码实现：
public class HuffmanCoding {
public static void main(String[] args) {
int n = 5;
char[] chars = {'a', 'b', 'c', 'd', 'e'};
int[] freq = {5, 7, 10, 15, 20};
PriorityQueue
for (int i = 0; i < n; i++) {
Node node = new Node(chars[i], freq[i]);
q.offer(node);
}
// 构造哈夫曼树
while (q.size() > 1) {
Node node1 = q.poll();
Node node2 = q.poll();
Node newNode = new Node('_', node1.freq+node2.freq, node1, node2);
q.offer(newNode);
}
Node huffmanTree = q.poll();
// 对哈夫曼树进行编码
ArrayList
String code = "";
getCode(codeList, huffmanTree, code);
// 输出编码结果
for (int i = 0; i < n; i++) {
System.out.println(chars[i]+": "+codeList.get(i));
}
}
private static void getCode(ArrayList
if (node.left == null && node.right == null) {
codeList.add(code);
return;
}
getCode(codeList, node.left, code+"0");
getCode(codeList, node.right, code+"1");
}
}
class Node implements Comparable
char ch;
int freq;
Node left, right;
public Node(char ch, int freq) {
this.ch = ch;
this.freq = freq;
this.left = null;
this.right = null;
}
public Node(char ch, int freq, Node left, Node right) {
this.ch = ch;
this.freq = freq;
this.left = left;
this.right = right;
}
public int compareTo(Node other) {
return this.freq - other.freq;
}
}
贪心算法在Java语言中的实现
Java语言是一种面向对象的语言，它能够很好地将数据结构与算法相结合。在Java中使用贪心算法，可以借助各种数据结构的支持，加快算法的实现。
Java语言提供了PriorityQueue类（优先队列），它可以自动将元素按照某种规则进行排序，每次取出最小或最大元素。这个类可以用来实现活动安排问题和哈夫曼编码等贪心算法。
此外，在Java语言中还可以使用数组等基本数据结构来实现贪心算法。在分数背包问题中，使用数组记录每个物品单位重量的价值，再按照数组中的价值进行排序即可。在实现过程中，还可以使用Arrays.sort()方法进行排序，将代码量进一步简化。
