一、理论基础

  贪心算法,指在对问题求解时,总是做出在当前看来是最好的选择。也就是说不从整体最优上加以考虑,算法得到的结果是在某种意义上的局部最优解。

1.1 适用场景

  可以用贪心算法解决的问题一般有如下特征:
   1>贪心选择性质。一个问题的整体最优解可通过一系列局部的最优解的选择达到,并且每次的选择可以依赖以前作出的选择,但不依赖于后面要作出的选择。这就是贪心选择性质。对于一个具体问题,要确定它是否具有贪心选择性质,必须证明每一步所作的贪心选择最终导致问题的整体最优解。
   2>最优子结构性质。当一个问题的最优解包含其子问题的最优解时,称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用贪心法求解的关键所在。

1.2 使用步骤

  使用贪心算法的基本步骤:
   1>建立数学模型来描述问题 。
   2>把求解的问题分成若干个子问题 。
   3>对每个子问题求解,得到子问题的局部最优解。
   4>把子问题的解局部最优解合成原来解问题的一个解。
  以上都是官方说法。依个人的理解,在贪心选择性质里,其实隐含着一个条件,就是:在使用贪心算法时,待选择的因素是有序的。在该前提下,才可能做出对当前最优的选择。用公式来表示的话,大致如下:

while(约束条件成立){
  选择当前最优解,记录并累积到最后的解中
  if(当前最优解使用完毕)
    当前最优解 = 当前次优解
}

1.3 算法缺陷

  贪心算法也存在如下缺陷:
   1>不能保证解是最佳的。因为贪心算法总是求的局部最优解,并未从整体考虑整体最优解。
   2>贪心算法只能确定某些问题的可行性范围。

缺陷1和缺陷2表示的意思是类似的,就是贪心算法是有局限性的。此处以一个例子来说明:比如钱币找零问题,假如有15元,需要用11、5、1三种面额的钱币来表示,如果用贪心算法来选择的话,会从11开始选择,这样就会选出11+1+1+1+1的方案,用5张钱币来表示,但实际上,用5+5+5的方案,使用的钱币更少,此时贪心方案就选不出全局最优解。

   3>贪心算法一般用来解决求最大或最小解。

该缺陷也好理解,贪心算法是以某种策略选择一个值,而不是遍历出所有解,要遍历出某个问题所有解的话,常常用的是回溯法

1.4 经典例子

  常见例子如下:
   1>活动选择问题
   2>钱币找零问题
   3>再论背包问题
   4>小船过河问题
   5>区间覆盖问题
  接下来将对这些例子进行实现,来探究贪心算法思想的具体使用方法。

二、常见例子

2.1 活动选择问题

  该问题是一般可以用贪心算法和动态规划两种方法解决,此篇文章主要介绍贪心算法实现方式。该类问题的形式一般如下:在某个地方需要举办不同的活动,每个活动要花费不同时间(起止时间不同),问怎样安排,可以安排尽量多的活动?此问题之所以可以用贪心算法解决,是因为下个活动的选择可以只取决于上个活动结束时间,而不必从全局考虑
  我们假设有个已经按结束时间排好序的活动列表,开始时间和结束时间如下:

活动1234567891011
开始时间130535688212
结束时间4567891011121314

  在解决该问题时,需要先对每个活动按结束时间进行排序。也许有人会问,为什么要对活动的结束时间,而不是开始时间进行排序,这样做的原因是当前活动的结束时间会影响到下一个活动的选择,而当前活动的开始时间不会影响下一个活动的选择
  整个的解题思路,大致如下:先把活动按结束时间排序,然后默认选取第一个活动,用变量来标识当前活动的结束日期,作为选择下一个活动的日期的判断标准,具体标准为:下一个选取的活动的开始时间要>=当前活动的结束时间。然后重复此过程,直到遍历完整个数组。
  活动选择问题的迭代解法,示例代码如下:

    private static List<Integer> activityChoice(int[] startTime, int[] endTime){
        List<Integer> list = new ArrayList<Integer>();
        /*因为活动已经按结束时间进行过升序排列,所以要默认选中第一个活动*/
        list.add(0);

        /*当前开始活动的结束时间*/
        int curTime = endTime[0];
        for(int i=1;i<endTime.length;i++){
            /*如果目前的活动的开始时间>=之前选择的活动的结束时间,则选取该活动,更新当前时间*/
            if (startTime[i]>=curTime) {
                list.add(i);
                curTime = endTime[i];
            }
        }
        return list;
    }

  活动选择问题的递归解法,示例代码如下:

	static List<Integer> acivitySelector(int[] startTime, int[] endTime, int i, int n,List<Integer> list) {
		/*因为活动已经按结束时间进行过升序排列,所以要默认选中第一个活动,+1是因为数组下标从0开始,此处是数组下标+1*/
		if(i==0){
			list.add(i+1);
		}

		int j=i+1;
		/*此处的循环是过滤掉不符合要求的活动*/
		while (j<=n && endTime[i]>startTime[j]){
			j++;
		}
		//找到一个满足f[i]<=s[j]的活动,添加到list
		if (j<=n) {
			/*j+1对应活动的编号,也就是数组下标+1*/
			list.add(j+1);
			/*更新一下当前活动j,然后继续向后找满足条件的活动*/
			acivitySelector(startTime, endTime, j, n,list);
		}
		return list;
	}

  完整代码示例如下:

package Greedy;

import java.util.ArrayList;
import java.util.List;

/*贪心算法,活动选择问题*/
public class ChooseActivity {
    public static void main(String[] args) {
        int[] startTime = {1, 3, 0, 5, 3, 5, 6, 8, 8, 2, 12};
        int[] endTime = {4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 };
        /*迭代解法*/
        List<Integer> activityTime=activityChoice(startTime,endTime);
        for (Integer activity: activityTime)
            System.out.print(activity+1+" ");
        System.out.println();
        
        /*递归解法*/
        List<Integer> activityTime2 = new ArrayList<Integer>();
        activityTime2=acivitySelector(startTime,endTime,0,startTime.length-1,activityTime2);
        for (Integer activity: activityTime2)
            System.out.print(activity+" ");
        
    }
    
    /*活动选择问题的迭代解法*/
    private static List<Integer> activityChoice(int[] startTime, int[] endTime){
        List<Integer> list = new ArrayList<Integer>();
        /*因为活动已经按结束时间进行过升序排列,所以要默认选中第一个活动*/
        list.add(0);

        /*当前开始活动的结束时间*/
        int curTime = endTime[0];
        for(int i=1;i<endTime.length;i++){
            /*如果目前的活动的开始时间>=之前选择的活动的结束时间,则选取该活动,更新当前时间*/
            if (startTime[i]>=curTime) {
                list.add(i);
                curTime = endTime[i];
            }
        }
        return list;
    }
    
    /*活动选择问题的递归解法*/
	static List<Integer> acivitySelector(int[] startTime, int[] endTime, int i, int n,List<Integer> list) {
		/*因为活动已经按结束时间进行过升序排列,所以要默认选中第一个活动,+1是因为数组下标从0开始,此处是数组下标+1*/
		if(i==0){
			list.add(i+1);
		}

		int j=i+1;
		/*此处的循环是过滤掉不符合要求的活动*/
		while (j<=n && endTime[i]>startTime[j]){
			j++;
		}
		//找到一个满足f[i]<=s[j]的活动,添加到list
		if (j<=n) {
			/*j+1对应活动的编号,也就是数组下标+1*/
			list.add(j+1);
			/*更新一下当前活动j,然后继续向后找满足条件的活动*/
			acivitySelector(startTime, endTime, j, n,list);
		}
		return list;
	}
}

  测试结果:

1 4 8 11
1 4 8 11

2.2 钱币找零问题

  该问题的一般描述是:假设1元、2元、5元、10元、20元、50元、100元的纸币分别有c0, c1, c2, c3, c4, c5, c6张。现在要用这些钱来支付K元,至少要用多少张纸币?该问题和上个问题有些类似,要解决该问题时,一般也有两个数组,一个表示面额的大小,一个表示不同面额钱币对应的数量,并且表示面额的数组是有序的。
  由于该题目求的是最少的纸币数,所以理所应当要先使用大额纸币,然后依次递减,用较小额的纸币,直到表示完所有钱币。所以该题的解决思路是:优先使用大额钱币,待大额钱币使用完后,再使用次大额的钱币,直到完全表示了K元。同样,该问题也有迭代和递归两种解法。
  迭代解法的示例代码如下:

	private static int[] countMoney(int[] values,int[] counts,int money){
		/*结果数组,用来存放每种面额对应的钱币的数量*/
		int[] result=new int[values.length];
		/*先用大额钱币,所以从后向前遍历values数组*/
		for(int i=values.length-1;i>=0;i--){
			/*使用当前面额钱币时,用到的数量*/
			int num=Math.min(counts[i],money/values[i]);
			/*将结果存储到结果数组*/
			result[i]=num;
			/*钱币总额需要减掉已表示的钱币额度*/
			money=money-num*values[i];
		}
		return result;
	}

  递归解法的示例代码如下:

	/*钱币找零问题的递归解法*/
	private static void countMoney2(int[] values,int[] counts,int money,int position,int[] result){
		if(money>0){
			int num=Math.min(counts[position],money/values[position]);
			result[position]=num;
			countMoney2(values,counts,money-num*values[position],position-1,result);
		}
	}

  完整代码示例如下:

package Greedy;

/*
 * 假设1元、2元、5元、10元、20元、50元、100元的纸币分别有c0, c1, c2,
 *  c3, c4, c5, c6张。现在要用这些钱来支付K元,至少要用多少张纸币?
 */
public class Coin {
	public static void main(String[] args) {
        /*人民币面额集合*/
        int[] values = {1,2,5,10,20,50,100};
        /*各种面额对应数量集合*/
        int[] counts = {3,1,2,1,1,3,5};
        /*结果数组,用来存放每种面额对应的钱币的数量*/
        int[] result = countMoney(values,counts,365);
        for(int i=0;i<result.length;i++){
        	/*当对应面额的钱币数量为0时,没必要打印*/
        	if(result[i]!=0)
        		System.out.println("需要用面额"+values[i]+"元的钱币"+result[i]+"张");
        }
        
        int[] result2= new int[values.length];
        countMoney2(values,counts,365,values.length-1,result2);
        for(int i=0;i<result2.length;i++){
        	if(result2[i]!=0)
        		System.out.println("需要用面额"+values[i]+"元的钱币"+result2[i]+"张");
        }
        
	}
	
	/*钱币找零问题的迭代解法*/
	private static int[] countMoney(int[] values,int[] counts,int money){
		/*结果数组,用来存放每种面额对应的钱币的数量*/
		int[] result=new int[values.length];
		/*先用大额钱币,所以从后向前遍历values数组*/
		for(int i=values.length-1;i>=0;i--){
			/*使用当前面额钱币时,用到的数量*/
			int num=Math.min(counts[i],money/values[i]);
			/*将结果存储到结果数组*/
			result[i]=num;
			/*钱币总额需要减掉已表示的钱币额度*/
			money=money-num*values[i];
		}
		return result;
	}
	
	/*钱币找零问题的递归解法*/
	private static void countMoney2(int[] values,int[] counts,int money,int position,int[] result){
		if(money>0){
			int num=Math.min(counts[position],money/values[position]);
			result[position]=num;
			countMoney2(values,counts,money-num*values[position],position-1,result);
		}
	}	
}

  测试结果:

需要用面额5元的钱币1张
需要用面额10元的钱币1张
需要用面额50元的钱币1张
需要用面额100元的钱币3张
需要用面额5元的钱币1张
需要用面额10元的钱币1张
需要用面额50元的钱币1张
需要用面额100元的钱币3张

2.3 背包问题

  此问题常见的描述是:给定n种物品,1个背包,背包容量为c,每个物品i的价值为vi,重量为wi,如何选择装入物品能使背包的总价值最大?此处的背包问题指的是部分背包,不是像0-1背包问题中的某个物品不能拆开,此处的物品可以拆开,选取一部分放入背包中
  从贪心算法的角度看, 要保证背包中的物品总价值最大,就是要确保放入的每件物品的单个价值尽量大。也就是说,步骤如下:
   1>需要将物品按照单位重量价值进行排序。
   2>将尽可能多的单位重量价值最高的物品装入背包,若最大单位重量价值的物品全部装入背包后,背包还有多余容量,则选择单位重量价值次高的并尽可能多地装入背包。
   3>如果最后一件物品无法全部装入,则计算可以装入的比例,然后按比例装入。
  此处用迭代方式实现,示例代码如下:

package Greedy;

/*
 * 给定n种物品,1个背包,背包容量为c,每个物品i的价值为vi,重量为wi,如何选择装入物品能使背包的总价值最大?
 */
public class Package {
	public static void main(String[] args) {
		/*每件物品的重量*/
		int[] weights={10,30,20};
		/*每件物品的价值*/
		int[] values={60,120,100};
		/*背包的容量限制*/
		int packNum=50;
		maxPackageValue(weights,values,packNum);
		
	}
	
	private static void maxPackageValue(int[] weights,int[] values,int packNum){
		/*单位重量价值比*/
		double[] univalent=new double[values.length];
		/*最后背包中存储的总价值*/
		double allValue=0.0;
		for(int i=0;i<univalent.length;i++){
			univalent[i]=(double)values[i]/weights[i];
		}
		
		/*1.使用冒泡排序,按单位价值进行升序排序*/
        for(int i=0;i<univalent.length-1;i++){
            for(int j=0;j<univalent.length-1-i;j++){
                if(univalent[j]>univalent[j+1]){
                	/*对单位价值排序*/
                    double temp=univalent[j];
                    univalent[j]=univalent[j+1];
                    univalent[j+1]=temp;
                    /*对wights排序*/
                    int tempWeight=weights[j];
                    weights[j]=weights[j+1];
                    weights[j+1]=tempWeight; 
                    /*对values排序*/
                    int tempValue=values[j];
                    values[j]=values[j+1];
                    values[j+1]=tempValue; 
                }
            }
        }
        
        /*此数组用来表示每种物品是否已经被放入背包*/
        int[] packFlag=new int[univalent.length];
        for(int i=0;i<packFlag.length;i++){
        	/*代表还没放入背包*/
        	packFlag[i]=0;
        }
        
        /*2.将可以完整存放的物品装入背包*/
        for(int i=univalent.length-1;i>=0;i--){
        	/*代表可以装的下*/
        	if(weights[i]<packNum){
        		packNum=packNum-weights[i];
        		packFlag[i]=1;
        		allValue=allValue+values[i];
        		System.out.println("重量为:"+weights[i]+",价值为:"+values[i]+"的物品可以被完全装入");
        	}
        }
        
        for(int i=0;i<packFlag.length;i++){
        	/*3.该物品不能被完全放入背包,需要放入部分*/
        	if(packFlag[i]==0){
        		/*该物品可以放入的比例*/
        		double rate=(double)packNum/weights[i];
        		allValue=allValue+values[i]*rate;
        		System.out.println("重量为:"+weights[i]+",价值为:"+values[i]+"的物品可以被装入的比例是:"+rate);
        	}
        }
        System.out.println("背包中可以存放的总价值是:"+allValue);
	}
}

  测试结果:

重量为:10,价值为:60的物品可以被完全装入
重量为:20,价值为:100的物品可以被完全装入
重量为:30,价值为:120的物品可以被装入的比例是:0.6666666666666666
背包中可以存放的总价值是:240.0

2.4 小船过河问题

  该问题的常见描述是:有n个人需要过河,只有一艘船,最多能乘2人,船的运行速度为2人中较慢一人的速度,过去后还需一个人把船划回来,把n个人运到对岸,最少需要多久。
  假设这些人所花费的时间都存储在一个数组time中,升序排列,也就是由快到慢,每个人所花费的时间为time[0],time[1]…time[n-2],time[n-1]。
  在人数>=4时,该问题的解决思路常常有两种:
   1>最快的和次快的过河,然后最快的将船划回来;次慢的和最慢的过河,然后次快的将船划回来。此时我们可以计算一下这个过程所花费的时间(至于为什么要计算这个过程所花费的时间,因为当人数>=4时,一直将这个过程重复下去即可),过程如下:
      
  从上图看出,该类方式所花费时间为:time[0]+2time[1]+time[n-1]。
   2>最快的和最慢的过河,然后最快的将船划回来,最快的和次慢的过河,然后最快的将船划回来。过程如下:
     
  从上图看出,该类方式所花费时间为:2time[0]+time[n-2]+time[n-1]。
  上面讨论了当过河的人大于等于四个人的情况。每次送两个人过河的方式共有两种,在具体使用时可以比较一下用哪种方式比较快,再决定使用的方式。接下来还要看一下过河时人数小于等于三个的情况:
   1>当过河人数为三个时,此固定用时time[0]+time[1]+time[2]。
   2>当过河人数为二个时,也许有人会问过河人数为三时,不是包含了这个情况吗?确实是包含了,此处指的初始的人数就是两个,固定用时time[1]。
   3>当过河人数为一个时,固定用时time[0]。
  接下来就是代码实现,示例代码如下:

package Greedy;

/*
 * 有n个人需要过河,只有一艘船,最多能乘2人,船的运行速度为2人中较慢一人的速度,
 * 过去后还需一个人把船划回来,把n个人运到对岸,最少需要多久。
 */
public class River {
    public static void main(String[] args) {
    	int[] times={1,2,4,5,8};
    	int result=crossRiver(times);
    	System.out.println("所花时间为:"+result);
    }
    
    private static int crossRiver(int[] times){
    	/*n表示还未过河的人数,初始化为所有人*/
    	int n=times.length;
    	int result=0;
    	while(n>0){
    		if(n==1){
    			result=result+times[0];
    			break;
    		}else if(n==2){
    			result=result+times[0]+times[1];
    			break;
    		}else if(n==3){
    			result=result+times[0]+times[1]+times[2];
    			break;
    		}else{
    			/*在每次过河时,在两种方式上进行比较,选择耗时更少的那个*/
    			result=result+Math.min(times[1]+times[0]+times[n-1]+times[1],times[n-1]+times[0]+times[n-2]+times[0]);
    			/*无论采取哪种方式,最后的结果都是讲最慢的和次慢的运送过河,也就是数组的最后两位,所以此处可简单地将数组长度-2*/
    			n=n-2;
    		}
    	}
    	return result;
    }
}

  测试结果:

所花时间为:20

2.5 区间覆盖问题

  此问题的描述是:给定一个长度为m的区间,再给出n条线段的起点和终点(闭区间),求最少使用多少条线段可以将整个区间完全覆盖。要解此题的完整步骤如下:
   1>在所有待选择的区间里,剔除起点和终点在所求范围之外的区间。
   2>将所有区间按起点进行排序。
   3>默认选中第一个点,然后在挑选点的过程中,需要遵循以下原则:1、新区间的起点要小于等于当前区间的终点;2、新区间的终点要大于当前区间的起点。
   4>循环重复步骤3,直到当前区间的终点值>=预期的终点值,结束寻找区间的过程。
  此处省略步骤1,重点关注后3步,示例代码如下:

package Greedy;

/*
 * 数轴上有n个闭区间[ai, bi],选择尽量少的区间覆盖一条指定线段[s, t]。
 */
public class CoverSection {
	public static void main(String[] args) {
		int[][] ections={{1,4},{2,4},{2,6},{3,5},{3,6},{3,7},{6,8}};
		/*此处假设的是求[1,8区间,所需的最少区间数,因为起点是从1开始的,
		 * 所以1不作为参数传入,只将终点值8作为参数传入即可]*/
		int count =overSection(ections,8);
		System.out.println("最少需要"+count+"个区间");
	}
	
	private static int overSection(int[][] ections,int length){
		/*默认选中第一个*/
	    int count=1;
	    System.out.println(ections[0][0]+","+ections[0][1]);
	    /*初始化终点,默认为第一个区间的终点*/
	    int end=ections[0][1];
	    boolean stopFlag=false;
	    for(int i=1; i<ections.length; i++){
	    	/*要挑出的新区间,条件有2个:
	    	 *1、开头要小于等于上一个挑选的区间的终点
	    	 *2、终点要大于上一个挑选的区间的终点*/
	        if(ections[i][0]<=end && ections[i][1]>end){
	        	/*终点更新为当前区间的终点*/
	        	end=ections[i][1];
	        	for(int j=i+1;j<ections.length;j++){
	        		/*在开头满足条件时,终点选最大的那个*/
	        		if(ections[j][1]>end){
	        			/*更新终点,元素个数+1*/
	        			end=ections[j][1];
	        			count++;
	        			System.out.println(ections[j][0]+","+ections[j][1]);
	        			/*如果当前区间>=length,代表可以结束循环*/
	        			if(end>=length){
	        				stopFlag=true;
	        			}
	        		}
	        	}
	        }
	        /*结束循环*/
	        if(stopFlag)
	        	break;
	    }
	    return count;
	}
}

  测试结果:

1,4
3,7
6,8
最少需要3个区间

Logo

开放原子开发者工作坊旨在鼓励更多人参与开源活动,与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动,如meetup、训练营等,主打技术交流,干货满满,真诚地邀请各位开发者共同参与!

更多推荐