我的心灵告诫我，它教我不要因一个赞颂而得意，不要因一个责难而忧伤。树木春天开花夏天结果并不企盼赞扬，秋天落叶冬天凋敝并不害怕责难。——纪伯伦
《算法导论》学习笔记
1.前言
类似于动态规划，贪心算法通常用于最优化问题，我们做出一组选择来达到最优解。贪心算法的思想是每步选择都追求局部最优。一个最简单的例子是找零问题，为了最小化找零的硬币数量，我们反复选择不大于剩余金额的最大面额的硬币。贪心算法对很多问题都能够获得最优解，而且速度比动态规划快很多。但是，我们并不能简单的判断贪心算法是否有效。贪心算法并不保证得到最优解，但对很多问题确实可以求的最优解。
2.贪心算法的原理
贪心算法是通过一系列的选择来求出问题的最优解。在每个决策点，他做出在当时看来最佳的选择。这种启发式策略并不保证总是能够找到最优解，但是对于类似于活动选择类的问题非常有效。
贪心算法的过程比较繁琐，如下：
【１】确定问题的最优子结构；
【２】设计一个递归算法；
【３】证明如果我们做出一个贪心选择，则只剩下一个子问题；
【４】证明贪心算法总是安全的。
【５】设计一个递归算法实现贪心策略；
【６】将递归算法转换为迭代算法。
贪心选择的性质：我们可以通过做出局部最优（贪心）选择来构造全局最优解。也就是，当我们进行选择的时候，我们直接最初当前问题中看来最优的选择，而不必考虑子问题的解。这也正是贪心算法与动态规划的区别之处。在动态规划中，每个步骤都要进行一次选择，但是选择通常依赖于子问题的解。
最优子结构：如果一个问题的最优解包含其子问题的最优解，则成此问题具有最优子结构的性质。
3.贪心算法的应用-活动选择
问题描述：现有一组相互竞争的活动，如何调度能够找出一组最大的活动（活动数目最多）使得它们相互兼容？
递归的贪心算法的设计：
//数组s和数组f表示活动的开始和结束时间 下标k表示要求解的子问题sk 以及问题规模n。 假设已经将n个活动按照结束时间的前后进行排序，结束时间相同的可以任意排列。为了使得算法简便，我们添加一个虚拟活动a0,结束时间f0=0;
RecursiveActivitySelector(s,f,k,n){
m=k+1;
while(m<n&&s[m]<f[k]){
m=m+1;
}
if(m<=n){
return {am}+ RecursiveActivitySelector(s,f,m,n);
}else{
return null;
}
}
迭代贪心算法
GreedyActivitySelector(s,f){
n=s.length;
A={a1};
k=1;
for(m=2 to n){
if(s[m]>f[k]){
A=A+{am};
k=m;
}
}
return A;
}活动选择的贪心算法Java实现
package lbz.ch15.greedy.ins1;
/**
* @author LbZhang
* @version 创建时间：2016年3月11日 下午5:42:10
* @description 活动选择
*/
public class ActivitySelect {
public static void main(String[] args) {
System.out.println("测试活动选择");
int[] s = { 0, 1, 3, 0, 5, 3, 5, 6, 8, 8, 2, 12 };
int[] f = { 0, 4, 5, 6, 7, 9, 9, 10, 11, 12, 14, 16 };
System.out.println("递归贪心");
String res = "";
res += RecursiveActivitySelector(s, f, 0, s.length);
System.out.println(res);
System.out.println("迭代贪心");
res="";
res += GreedyActivitySelector(s, f);
System.out.println(res);
}
/**
* 迭代贪心算法设计使用
* @param s
* @param f
* @return
*/
private static String GreedyActivitySelector(int[] s, int[] f) {
int n=s.length;
String A=" a1";
int k=1;
for(int m=2 ;m<n;m++){
if(s[m]>f[k]){
A=A+" a"+m;
k=m;
}
}
return A;
}
/**
* 对结束时间有序的数组进行递归贪心算法的求解最大兼容活动子集
* @param s 开始时间数组
* @param f 结束时间数组
* @param k 起始下标 从0开始
* @param n 当前求解长度
* @return
*/
private static String RecursiveActivitySelector(int[] s, int[] f, int k,
int n) {
int m = k + 1;
while (m < n && s[m] < f[k]) {
m = m + 1;
}
if (m < n) {
return " a" + m + RecursiveActivitySelector(s, f, m, n);
} else {
return "";
}
}
}
4.贪心算法和动态规划的案例比较
由于贪心算法和动态规划都使用了最优子结构的性质。为了说明两者之间的差别，我们研究一个景点最优化问题的两个变形。
0-1背包问题：有N件物品和一个容量为V的背包。第i件物品的重量是w[i]，价值是v[i]。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。
分数背包问题: 这个问题和上面的问题比较相似，唯一不同的就是该问题里面的物品可以进行分割，即可以只选取一个物品ai的一部分。
在分数背包问题中，设定与0-1背包问题是一样的，但是对每一个物品，每次可以取走一部分，而不是只能做出二元选择（0-1）。你可以将一个物品的一部分或者一个物品拿走多次。
两个背包问题都有最优子结构性质。对于0-1背包问题，考虑重量不超过W而价值最高的装包方案。如果我们将物品j从此方案中删除，则剩余的商品必须是重量不超过W-wj的价值最高的方案。虽然两个问题十分相似，但是我们可以使用贪心策略解决分数背包问题，而不能求解0-1背包问题。
解决分数背包问题，我们可以先进行单位价值的计算，然后采用贪心策略来实现问题求解。而对于0-1背包问题，贪心策略是存在问题的，因此我们解决0-1背包问题需要使用动态规划来实现最优。
0-1背包问题Java实现
package lbz.ch15.greedy.ins1;
/**
* @author LbZhang
* @version 创建时间：2016年3月15日 下午8:13:13
* @description 0-1背包问题
*/
public class Knapsack {
public static void main(String[] args) {
int[] w={2,2,6,5,4};
int[] v={6,3,5,4,6};
int c=5;
int[][] m;//动态规划辅助表
int[] x;//构造最优解
m=Knapsack.knapsack(w,v,c);
System.out.println(m[w.length][c]);
x=Knapsack.buildSolution(m,w,c);
System.out.println("格式化输出0-1背包问题的结果");
for(int i=0;i<x.length;i++){
System.out.println("当前物品"+(i+1)+"的选择情况："+ x[i]);
}
}
private static int[] buildSolution(int[][] m, int[] w, int c) {
int i,j=c;
int n=w.length;
int[] x=new int[n];
for(i=n;i>=1;i--){
if(m[i][j]==m[i-1][j]){
x[i-1]=0;
}else{
x[i-1]=1;
j-=w[i-1];
}
}
return x;
}
private static int[][] knapsack(int[] w, int[] v, int c) {
int i,j,n=w.length;
/**
//假设m[i,j]表示前i件物品放入一个容量为j的背包可以获得的最大价值。
//状态转移方程
//m[i,j]=max{m[i-1][j],m[i-1][j-c[i]]+w[i]}
*
* 分析一下：
* 当前的可以支配的空间为j，通过判断 w[i-1]<j 来确定是否需要 进行后面的判断
* if((m[i-1][j-w[i-1]]+v[i-1])>m[i-1][j])
* 进行完判断 就可以实现m[i][j]
* m[i,j]表示前i件物品放入一个容量为j的背包可以获得的最大价值。
*/
int[][] m=new int[n+1][c+1];
for( i=0;i<n+1;i++){
m[i][0]=0;//
}
for( j=0;j<c+1;j++){
m[0][j]=0;
}
int count=0;
for(i=1;i<=n;i++){
for(j=1;j<=c;j++){
m[i][j]=m[i-1][j];//开始赋值
if(w[i-1]<j){//如果第i个物品小于当前的剩余容量
if((m[i-1][j-w[i-1]]+v[i-1])>m[i-1][j]){
//检验保持最优子结构
m[i][j]=m[i-1][j-w[i-1]]+v[i-1];
}
}
count++;
}
}
System.out.println(count);
return m;
}
}
5. 赫夫曼编码
赫夫曼编码可以有效的压缩数据，我们将待压缩数据看作是字符序列。根据出现的频率，赫夫曼贪心算法构造出字符最优二进制表示。
构造赫夫曼编码的算法
HUFFMAN(C){
n=|C|;//获取C字母表的长度
Q=C;//最小二叉堆的构建
for(i=1 to n-1){
allocate a new node z;
z.left=x=Extract-Min(Q);
z.right=y=Extract-Min(Q);
z.freq=x.freq+y.freq;
INSERT(Q,z);
}
return Extract-Min(Q);
}