贪心算法的几种经典例题

什么是贪心算法

贪心算法是一种在解决问题的过程中追求局部最优的算法，对于一个有多种属性的事物来说，贪心算法会优先满足某种条件，追求局部最优的同时希望达到整体最优的效果。以背包问题为例，可以放在背包中的物体有它的重量和价值两种属性，背包的容量也是有限的，我们希望得到一种价值最大的物品摆放方式，如果我们倾向于重量贪心，那么在摆放物品的时候会优先放重量小的，但这和我们追求的价值最优没有关系，自然不能采用；如果倾向于价值贪心，而忽略了物品的重量，可能会导致摆放物品的数量不多，总价值很小；如果是以价值和重量的比值设计贪心算法求解，便可以实现最优的方案。下面我们举一些例子来说明在实际运用中如何实践贪心算法。

例题1：钱币找零问题

 / * 贪心算法1：钱币找零问题 */ public void greedy1(){ 
    //面额 int[] values = { 
    1, 2, 5, 10, 20, 50, 100 }; //数量 int[] counts = { 
    3, 3, 2, 1, 1, 3, 3 }; //获取需要各种面值多少张 int[] result = getNumber1(446, values, counts); System.out.println("各币值的数量："+Arrays.toString(result)); } / * 贪心算法1：钱币找零问题 * @param sum * @param values * @param counts * @return */ public int[] getNumber1(int sum , int[] values, int[] counts) { 
    int[] result = new int[7]; int add=0; //当前凑的金额 for(int i=values.length-1;i>=0;i--) { 
    int num = (sum-add)/values[i]; if(num>counts[i]) { 
    num=counts[i]; } add=add+num*values[i]; result[i]=num; } return result; } 

例题2：活动选择问题

 / * 贪心算法2：活动选择问题 */ public void greedy2(){ 
    int [] st = { 
   1,5,0,5,3,3,6,8,8,2,12}; int [] et = { 
   4,9,6,7,8,5,10,12,11,13,14}; int num = getNumber2(st,et); System.out.println("活动数量："+num); } / * 贪心算法2：活动选择问题 * @param a * @param b * @return */ public int getNumber2(int[] a , int[] b) //优先选择结束时间早的 { 
    int num=0; int tempa=0; int tempb=0; int endTime=0; int j=0; for(int i=1;i<b.length;i++)//如果顺序混乱，则调整为结束时间从小到大的顺序,直接插入排序 { 
    tempb=b[i]; tempa=a[i]; for(j=i-1;j>=0&&tempb<b[j];j--) { 
    b[j+1]=b[j]; a[j+1]=a[j]; if(j==0) { 
    j--; break; } } b[j+1]=tempb; a[j+1]=tempa; } System.out.println(Arrays.toString(a)); System.out.println(Arrays.toString(b)); num++; endTime=b[0]; for(int k=1;k<b.length;k++) { 
    if(a[k]>endTime) { 
    num++; endTime=b[k]; } } return num; } } 

例题3：背包问题

 / * 贪心算法3：背包问题 */ public void greedy3(){ 
    float M=50; //背包所能容纳的重量  float[] w={ 
   0,10,30,20,5}; //每种物品的重量  float[] v={ 
   0,200,400,450,20}; //每种物品的价值  float num = getNumber3(M,w,v); System.out.println("物品数量："+num); } / * 贪心算法3：背包问题 * @return */ public float getNumber3(float M,float[] w ,float[] v) { 
    float num=0; int i=0; float max=0; float weight=0; for(i=0;i<w.length;i++) { 
    if(v[i]/w[i]>max) { 
    max=v[i]/w[i]; weight=w[i]; } } num=M/weight; return num; } 

例题4：多机调度问题

 / * 贪心算法4：多机调度问题 */ public void greedy4() { 
    int[] time= { 
   9,7,8,4,2,1,3}; int number = 3; int Sumtime = getNumber4(time,number); System.out.println("花费的最小总时间："+Sumtime); } / * 贪心算法4：多机调度问题 * @param time * @param number * @return */ public int getNumber4(int[] time, int number) { 
    int usedTime=0; //最长时间为总时间 int[] fin = new int[number]; //单机处理时间  for(int k=0;k<number;k++) //初始时间清零 { 
    fin[k]=0; } if(number>time.length) return time[0]; else { 
    for( int i=0 ; i<time.length-1 ;i++) { 
    for( int j=0;j<time.length-i-1;j++) //冒泡选出任务时间最大的 { 
    if(time[j]>time[j+1]) { 
    int temp = time[j+1]; time[j+1]=time[j]; time[j]=temp; } } int min=0;; int value=100; for(int k=0;k<fin.length;k++) //选出当前累计工时最小的机子 { 
    if(fin[k]<value) { 
    min=k; value=fin[k]; } } fin[min]+=time[time.length-1-i]; } int min=0;; int value=100; for(int k=0;k<fin.length;k++) //选出当前累计工时最小的机子 { 
    if(fin[k]<value) { 
    min=k; value=fin[k]; } } fin[min]+=time[0]; for( int n=0;n<fin.length;n++) { 
    if(fin[n]>usedTime) { 
    usedTime=fin[n]; } } return usedTime; } } 

贪心算法5：小船过河问题

 / * 贪心算法5：小船过河问题 */ public void greedy5() { 
    int[] v = { 
   1,3,4,8,4,3,9}; //按照不同的人的速度过河所需的时间 int timeSum=getNumber5(v); System.out.println("过河总时间："+timeSum); } / * 贪心算法5：小船过河问题 */ public int getNumber5(int[] v) { 
    int time =0;; Arrays.sort(v);//降序排列 int N = v.length; //N表示当前人数 while(N>3) { 
    if(2*v[0]+v[N-1]+v[N-2]>2*v[1]+v[0]+v[N-1]) time+=2*v[1]+v[0]+v[N-1]; else time+=2*v[0]+v[N-1]+v[N-2]; N-=2; } else if(N==3) //处理边界 { 
    time+=v[2]+v[0]+v[1]; } else if(N==2) { 
    time+=v[1]; } else if(N==1) { 
    time+=v[0]; } return time; } 

总结

贪心算法追求局部最优，拿到问题之后先分析我们需要达到什么目标，是否适合采用贪心算法，并且使得什么最优以及实现的方法。