贪心算法算是我系统性接触的第一个算法，在学习的过程中页也看了一些书籍和示例，接下来介绍贪心的概念以及一个例子：
贪心算法主要的思想是局部最优解。贪心算法在目前已有的信息上做出局部最优解，同时做出了选择之后，不管将来有什么结果，选择都不会有所改变，同时，贪心策略的选择对于算法的好坏有着直接的影响。
贪心算法的特性（满足后可使用）：
1：贪心选择
指原问题的整体最优解可以通过一系列的局部最优解得出，应用同一规则，将原问题转化为一个相似但规模更小的子问题，而后每一步都是当前最佳的选择。这种选择依赖于已做出的选择。同时，贪心策略无回溯过程。
2：最优子结构
当一个问题的最优解包含其子问题的最优解时，称此问题为最优子结构性质。这个性质是该问题能否用贪心解决的关键。
贪心算法的使用步骤：
1：制定贪心策略选择一个当前看上去最好的方案（方案的选择尤为重要）。
2：根据贪心策略一步一步获得局部最优解。
3：将所有的局部最优解和成为原来问题的一个最优解。
接下来介绍两个示例：
1：最优装载问题：
问题描述：有一艘船，载重量为C，有i件古董，重量分别为Wi，如何尽可能多的装载古董？
解题思路：将古董重量由大到小排序，然后将其依次装入船中，当大于船的重量时停止，最终返回转载的数量。
题目数据：C：30，W：4，10，7，11，3，5，14，2
1 public int Solution1() { 2 int C = 30; 3 int[] W = new int[]{4, 10, 7, 11, 3, 5, 14, 2}; 4 Arrays.sort(W); 5 int tmp = 0; 6 int i = 0; 7 while (tmp <C){ 8 tmp+=W[i]; 9 i++; 10 } 11 return i-1; 12 }//最优装载问题解法
最后返回值为5，时间复杂度O(n+nlogn)
2：背包问题：
问题描述：山中有一个山洞，洞中n种宝物，每种宝物有一定的重量W和价值V，只能运走M重量的宝物，一种拿一样，宝物可分割，如何使宝物价值最大？
解题思路：选择贪心策略单位价值最大宝物，然后从性价比由高到低选择，最终输出宝物最大价值。
题目数据：W:4,2,9,5,5,8,5,4,5,5；V:3,8,18,6,8,20,5,6,7,15；M:30
1 public float Solution2(){ 2 int M=30; 3 int[] W=new int[]{4,2,9,5,5,8,5,4,5,5}; 4 int[] V=new int[]{3,8,18,6,8,20,5,6,7,15}; 5 Item[] items=new Item[W.length]; 6 for(int i=0;i<W.length;i++){ 7 items[i]=new Item(W[i],V[i]); 8 }//计算单位重量的价值,并将其存为一个数组 9 Arrays.sort(items); 10 Item[] item =new Item[items.length]; 11 for(int i=0;i<10;i++){ 12 item[i]=items[9-i]; 13 }//数组翻转 14 float Value=0; 15 int count=0; 16 int tmp=0;//装载的重量 17 while(tmp<M){ 18 if(tmp+item[count].getW()>M || tmp+item[count].getW()==M){ 19 break; 20 }else{ 21 tmp+=item[count].getW(); 22 Value+=item[count].getV(); 23 count++;} 24 } 25 int m=M-tmp;//剩下的重量 26 Value+=m*item[count].getV1();//拿走分割后的部分 27 return Value; 28 } 29 public class Item implements Comparable<Item>{ 30 private int W;//重量 31 private int V;//价值 32 private float V1;//单位价值 33 public Item(int i1,int i2){ 34 this.W=i1; 35 this.V=i2; 36 this.V1=((float) i2)/i1; 37 } 38 39 public float getV1() { 40 return V1; 41 } 42 43 public int getV() { 44 return V; 45 } 46 47 public int getW() { 48 return W; 49 } 50 51 public int compareTo(Item i){ 52 if (this.V1>i.getV1()){ 53 return 1; 54 55 }else if(this.V1==i.getV1()){ 56 return 0; 57 }else if(this.V1<i.getV1()){ 58 return -1; 59 } 60 return 0; 61 } 62 }
最后返回值为70.5，时间复杂度O(n+nlogn)
在这道题的解题思路中，如果java有c++中的结构体会使后面的代码不那么冗余，在java中需要实现comparable接口实现对象比较，稍微麻烦了些，但总体解题思路是一样的。