专栏首页技术圈贪心算法举例分析

贪心算法举例分析

版权声明:本文为博主原创文章,遵循 CC 4.0 by-sa 版权协议,转载请附上原文出处链接和本声明。

本文链接:https://blog.csdn.net/qq_27717921/article/details/52946572

贪心算法和动态规划的不同之处

在动态规划方法中每个步骤都要进行一次选择,但选择通常依赖于子问题的解。因此,我们通常以一种自底向上的方式求解动态规划问题,先求解较小的子问题,然后是较大的子问题。我们也可以自顶向下的求解,但需要备忘机制,当然,即使算法是自顶向下进行计算,我们仍然需要的先求解子问题在进行选择。

在贪心算法中,我们总是做出当时看来最佳的选择然后求解生下的唯一的子问题。贪心算法进行选择时可能依赖之前做出的选择但不依赖任何将来的选择或者是子问题的解。因此,与动态规划先求解子问题才能进行第一次选择不同,贪心算法在进行第一次选择之前不求解任何的子问题。

贪心算法在每一步都做出当时看起来最佳的选择,也就是说它总是做出局部最优的选择,希望这样的选择能导致全局最优,但是并不能保证得到最优解。最小生成树算法、单源最短路径的Dijkstra算法都是贪心算法策略设计的算法。

活动选择问题。每个任务都有一个开始时间Si和一个结束时间Fi,其中对单个的活动来说,它的结束时间要大于开始时间。如果两个活动ai和aj满足[si,fi],[sj,fj]不重叠则说明它们是兼容的。也就是说si>=fj或者是sj>=fi,则说明这两个活动是兼容的。下面这些活动已经按照结束时间的先后顺讯进行排序。

i 1 2 3 4 5 6 7 8 9 10 11

si 1 3 0 5 3 5 6 8 8 2 12

fi 4 5 6 7 9 9 10 11 12 14 16

选择一个最大兼容活动集,而对于每一步所要做出的贪心选择就是选择最早结束的活动,结束越早的活动说明结束这个活动之后的资源越能尽可能让更多的活动所利用,才能达到我们的目标使得活动兼容集尽可能额大。假设我们设置一个虚拟活动为a0,他的开始时间和结束时间都为0,那么在这个活动结束后最先开始的活动ai会被考虑进来,同理说,在活动ai结束后最先开始的活动也应该考虑,这样层层迭代就能得到最大兼容活动集,只有在某一个最先活动结束后最先开始的活动才能最先结束并且把资源空出来。

粘代码~~~

package Greedy;

import java.util.ArrayList;

public class Activity_Selector {

	//递归贪心算法
	public static String recursive_activity_Selector(int[] s,int[] f,int k,int n){
		int m=k+1;//所有的活动结束时间已经从小到大进行排序
		//在当前活动后的活动中找到时间上吻合的活动,也就是在当前活动结束后开始的活动,才能满足兼容的性质
		while(m<=n&&s[m]<f[k]){
			m++;
		}
		//找到第一个和活动k满足兼容性质的活动,找到后加入本集合,重复此问题
		if(m<=n){
			/*activityList.add("a"+m);*/
			
			if(recursive_activity_Selector(s,f,m,n)!=""){
				return "a"+m+"+"+recursive_activity_Selector(s,f,m,n);
			}
			return "a"+m;
		}
		return "";
		
	}
	//迭代贪心算法
	public static String greedy_activity_Selector(int[] s,int[] f){
		//采用非递归的形式就可以
	   int length = f.length;
	  
	   int k=1;
	   String str ="a"+k;
	   for(int i=2;i<length;i++){
		   if(s[i]>=f[k]){
			  str+="a"+i;
			  k=i;
		   }
	   }
	   return str;
		
		
	}
	public static void main(String[] args) {
		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.print(recursive_activity_Selector(s,f,0,11));*/
		System.out.print(greedy_activity_Selector(s,f));
	
	}

}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 动态规划算法举例解析(最大收益和最小损失选择)

    版权声明:本文为博主原创文章,遵循 CC 4.0 by-sa 版权协议,转载请附上原文出处链接和本声明。

    张凝可
  • 基于分治和DP的算法设计

    发现下面的策略都是比较糟糕的,这里提及一下分治和动态规划的区别,动态规划避免了分治方法的重复计算,下面的基本上是用了最朴素的动态规划方案,接下来会用自底向上的方...

    张凝可
  • 面试题目集(一)

    版权声明:本文为博主原创文章,遵循 CC 4.0 by-sa 版权协议,转载请附上原文出处链接和本声明。

    张凝可
  • 763. Partition Labels

    思路: 很暴力,直接找可以Partition的位置,如果不能Partition,继续向后搜索直到找到第一个可以Partition的位置为止,这样剩余问题就是...

    用户1147447
  • POJ 刷题系列:1068. Parencodings

    题意: 给出一组P-Sequence,每个数代表当前右括号之前的所有左括号数,求W-Sequence,表示当前右括号与它对应的左括号之间的左括号数。还是看例子...

    用户1147447
  • poj3264

    Description 在每天挤奶的时候,农民约翰的N头牛(1≤n≤50000)总是排成一列。有一天,约翰决定与他的牛们一起玩一个极限飞盘游戏。为了简单起见,他...

    attack
  • HDU 1527 取石子游戏(威佐夫博弈)

    Problem Description 有两堆石子,数量任意,可以不同。游戏开始由两个人轮流取石子。游戏规定,每次有两种不同的取法,一是可以在任意的一堆中取...

    attack
  • 挑战程序竞赛系列(79):4.3 2-SAT(3)

    挑战程序竞赛系列(79):4.3 2-SAT(3) 传送门:POJ 2723: Get Luffy Out 题意: 题目意思有点坑,实际上给出每一对钥匙,如...

    用户1147447
  • 多线程之策略模式

    今天给各位分享一种Java23种设计模式中最常见的设计模式--策略模式。为什么将策略模式和多线程绑在一起呢,不知道各位有没有注意过我们在进行多线程编程的时候,创...

    赵小忠
  • 【leetcode刷题】T34-只出现一次的数字 II

    Given a non-empty array of integers, every element appears three times except fo...

    木又AI帮

扫码关注云+社区

领取腾讯云代金券