实验3. 贪心算法
一、 实验目的
1. 理解贪心算法的基本思想。 2. 运用贪心算法解决实际问题。
二、 实验环境与地点
1. 实验环境：Windows7,Eclipse 2. 实验地点：网络工程实验室
三、 实验内容与步骤
编写程序完成下列题目，上机调试并运行成功。 1. 活动安排问题。
问题：有n个活动的集合A={1,2,…,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。
求解：安排尽量多项活动在该场地进行，即求A的最大相容子集。
设待安排的11个活动的开始时间和结束时间按结束时间的升序排列如下：
i s[i] f[i] 1 1 4 2 3 5 3 0 6 4 5 7 5 3 8 6 5 9 7 6 10 8 8 11 9 8 12 10 2 13 11 12 14
将此表数据作为实现该算法的测试数据。 （1）给出算法基本思想；
（2）给出用java语言实现程序的代码; 算法：
public static int greedySelector(int[] s, int[] f, boolean a[]) { int n = s.length - 1; a[1] = true; int j = 1; int count = 1; for (int i = 2; i <= n; i++) { if (s[i] >= f[j]) { a[i] = true; j = i; count++; } else a[i] = false; } return count; }
2. 哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。统计字符串中各个字符
出现的频率，求各个字符的哈夫曼编码方案。
输入：good good study,day day up 输出：各字符的哈夫曼编码。
算法：
算法中用到的类Huffman定义为：
private static class Huffman implements Comparable { Bintree tree; float weight;// 权值 private Huffman(Bintree tt, float ww) { tree = tt; weight = ww; } public int compareTo(Object x) { float xw = ((Huffman) x).weight; if (weight < xw) return -1; if (weight == xw) return 0; return 1; } }
算法huffmanTree描述如下:
public static Bintree huffmanTree(float[] f) { // 生成单结点树 int n = f.length; Huffman[] w = new Huffman[n + 1]; Bintree zero = new Bintree(); for (int i = 0; i < n; i++) { Bintree x = new Bintree(); x.makeTree(new MyInteger(i), zero, zero); w[i + 1] = new Huffman(x, f[i]); } // 建优先队列 MinHeap H = new MinHeap(); H.initialize(w, n); // 反复合并最小频率树 for (int i = 1; i < n; i++) { Huffman x = (Huffman) H.removeMin(); Huffman y = (Huffman) H.removeMin(); Bintree z = new Bintree();
z.makeTree(null, x.tree, y.tree); Huffman t = new Huffman(z, x.weight + y.weight); H.put(t); } return ((Huffman) H.removeMin()).tree; }
提示：统计一个字符串中每个字符出现的次数思路： 1.创建一个map key:出现的字符 value:出现的次数 2.获取字符串中的每一个字符
3.查看字符是否在Map中作为key存在否，若存在，说明已经统计过则value+1 不存在：value=1 代码如下：
public class CountString { public static void main(String[] args) { String str = \; Map
四、 实验总结与分析
参考代码：
1. ActivityArrangement
public class AvtivityArrangement {
public static int[] s= { 0,1, 3, 0, 5, 3, 5, 6, 8, 8, 2, 12}; public static int[] f= { 0,4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14}; public static boolean[] a=new boolean[s.length];
public static int greedySelector(int[] s, int[] f, boolean[] a) { int n = s.length - 1; a[1] = true; int j = 1;
实验3. 贪心算法
