算法起步之贪心算法

原文:算法起步之贪心算法

       我们前面介绍的动态规划算法是求解最优化问题的一种通用方法，但是对于很多的最优化问题是用动态规划有点小题大做了，我们可以使用贪心算法，贪心算法相比动态规划更简单，也更高效。它总是做出局部最优选择，希望这样可以得到全局的最有选择。所以这种方法不能保证得到最优解，但是很多问题却都可以用这种方法。我们先看一个活动选择的例子。

       假设我们有n个活动，只有一个教室，求在这个教室中一天最多可以举办多少活动（同一时间只能举办一个活动）。下面给出的是活动的开始时间跟结束时间。

       动态规划解法：

       本来想这个用动态规划很简单，看了一下算法导论写的，只写了一个递归的算法，但是递归的效率太低，于是就想写自底向上的，写了一个简单的确发现自己想错了，于是在网上找了很多动态规划解活动选择的问题，都不太满意，都不是按照我想的那样，很多写的算法时间复杂度达到了n的三次方。今天又看了一遍题目，突然写了出来，虽然耽误了很多时间，但是我觉得这比网上其他给的答案还要快一点。

public class DPActity {
	public void actity(){
		Scanner sc=new Scanner(System.in);
		int[][] map=new int[25][25];
		for (int i = 0; i < 11; i++) {
			map[sc.nextInt()][sc.nextInt()]=1;
		}

		for(int i=1;i<map.length;i++){
			for(int j=0;j<=i;j++){
				if(map[j][i]==1){
					map[0][i]=max(map[0][i-1], 1+map[0][j]);
				}else{
					map[0][i]=max(map[0][i-1],map[0][i]);
				}
			}
		}
		System.out.println(map[0][24]);
	}
	public int max(int a,int b){
		if(a>b){
			return a;
		}else{
			return b;
		}
	}

	public static void main(String[] args) {
		new DPActity().actity();
	}

}

          虽然这样写的感觉代码也不多，但是如果我们用贪心的做法你会发现非常简单，而且好理解。因为我们的数值倒是按照结束时间排序的，所以一直选择结束时间最短的则获得最优解。在这里选择结束时间最早的活动就是我们的决策点。而贪心算法关键就是在选择决策点上。顺便一提像01背包问题不能用贪心算法来解但是分数背包可以解决。

public void greedy(int[]s,int[]f){
		int n=s.length;
		int k=1;
		for (int i = 2; i < n; i++) {
			if (s[i]>=f[k]) {
				k=i;
			}
		}
		System.out.println(k);
	}

友情提示：转载请注明出处【作者：idlear  博客：http://blog.csdn.net/idlear】