贪心算法几个经典例子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 q = new 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 codeList = new 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 codeList, Node node, String code) {

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()方法进行排序，将代码量进一步简化。