`
endual
  • 浏览: 3566289 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

贪心算法的一些感悟

 
阅读更多

每一个贪心算法的背后,总有一个动态规划在默默的陪着。

                                                               ----------Endual 

    这句话的意思是贪心算法和动态规划有密切的关系,用树上的话来说,贪心算法在一些问题上比动态规划好,提高了效率,

比动态规划解决起来要好的多。

    首先我们来看一个例子:

 

 

      我们来看一个实例:

      我们有100个活动要进行,每个活动都有一个开始时间和一个结束时间。而这些活动又要共同的占有资源来进行活动,比如这些活动都只能在A教室中进行的。一个活动在进行的时候,其他的活动是不能够来进行活动的。我们要求解的是:怎样配合才能够在100个。

 

 

      我们先来看贪心算法的选择性特点:

 

 

贪心选择的性质

       第一个关键特定是贪心选择性质:一个全局最优解可以通过局部最优选择来达到。换句话说,某次选择以后,我们来解决剩余的集合的同样的问题,解出来的答案可以和我们选择出来的答案进行不修改的合并。那么,我们当考虑做什么选择的时候,我们只考虑对当前问题最佳的选择,而不考虑子问题的结果了。

贪心算法的最优子结构的问题

 

 

     我们来看最优子结构

     最优子结构的,我们把这个100活动分成两个部分,那么A部分的最后结束时间是小于B部分的最早开始时间的,这两个子问题的答案可以  经过简单的相加就可以得到我们原来问题的答案了。

 

 

贪心算法和动态规划的区别

 

以上两点是用我自己的话来说的。

   下面是算法导论的话:

     这一点是贪心算法和动态规划不一样的地方。

                      在动态规划中,每一步都要做出选择,这些选择依赖于子问题的解。因此,解动态规划问题的时候

          一般都是从子问题开始解答的,一般都是从自底向顶的方法进行解答的,从小子问题处理到大子问题。

                      在贪心算法中,我们所做的总是当前看似最佳的选择,然后再去解决选择之后所出现的子问题。贪心算法所做的当前选择可能要

                      依赖于已经做出的所有的选择,但是不会以依赖于有待于做出的选择或者子问题的解。因此,不像动态规划那样自底向上的解决子问题

                      贪心算法通常是自顶向下的做的,一个一个的做出贪心选择,不断的将给定的问题实例规约为更小的子问题中。   

 

 

贪心算法的一些性质:

 

   选择性的特定:我觉得这个贪心算法的第一点应去看这个选择性问题。我们在把原来的问题分成子问题的过程中,考虑这个问题:我们把原来的问题的数据选择一部分出去以后,剩余的数据集合中(剩余数据形成的子问题)解答出来的答案就是我们可以直接使用的。子问题的解是直接可以用,不会影响到选择出去的数据形成的子问题的解的。

 

 

 

 

     ------------当然了,问题解答有更好的文字说明,在算法导论中,或者中java版的王晓明的算法设计与分析的课本上。并且还给出来了详细的

     伪代码和思路。      

 

 

public class Main {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

		int[] s = {0,1,3,0,5,3,5,6,8,8,2,12} ;
		int[] f = {0,4,5,6,7,8,9,10,11,12,13,14} ;
		boolean[] a = {false,false,false,false,false,false,false ,false ,false ,false,false,false} ;
		int count = greedySelector(s, f, a) ;
		System.out.println(count);
	}

	// 贪心算法的活动安排代码
	// 输入的是活动已经安排好顺序了的,从最早结束的为标志排序排序好的
	/**
	 * 
	 * @param s 开始的时间的集合,这个是按照最迟结束的时间排序好的
	 * @param f 结束的时间的集合,已经按照时间排序排序好了
	 * @param a 是否已经完成的标志
	 * @return 返回的是最大的活动数
	 */
	public static int greedySelector(int[] s, int[] f, boolean a[]) {
		
		int n = s.length - 1; //有多少活动 
		a[1] = true; //第一个活动已经完成了
		int j = 1;   //当前最近结束的活动的序号
		int count = 1; //总的活动个数已经有一个了
		for (int i = 2; i <= n; i++) { //从第二个开始,当第n个结束了
			
			if (s[i] >= f[j]) { //第i个项目的开始的时间,比第j个项目的结束时间要早要大于或者等于
				
				a[i] = true;    //那么已经完成了
				j = i;
				count++; //数量要加一个	
			}
			else {	
		       a[i] = false; //否则是没有完成的
			}
		}
		for(int i=1; i< a.length; i++) {
			
			System.out.print("  "+a[i]);
		}
		return count;
	}

}
 

 

 

分享到:
评论

相关推荐

    贪心算法求解马踏棋盘

    利用贪心算法求解马踏棋盘,数据结构课程设计!

    计算机算法设计与分析学习心得.rar

    7. **贪心算法**:贪心策略是在每一步选择当前看起来最优的选择,不考虑未来的影响。贪心算法在解决某些问题上非常有效,如霍夫曼编码和Prim算法。 8. **回溯法与分支限界**:用于搜索所有可能解的算法,通常用于...

    leetcode初级算法.zip

    4. 贪心算法:每次做出局部最优选择,以期望得到全局最优解,如最小生成树、活动安排等。 5. 回溯法:用于解决组合优化问题,如八皇后问题、N皇后问题等。 三、LeetCode初级算法解题策略 1. 读题理解:理解题目...

    深入浅出算法竞赛.pptx

    在第三章中,作者详细介绍了算法竞赛中常用的算法,包括贪心算法、分治算法、动态规划、回溯算法等。作者通过具体实例来帮助读者深入理解这些算法的基本思想、实现方法和优化技巧,并帮助读者学会如何设计出高效的...

    数据结构基础与基础算法总结

    此外,还需了解贪心算法、动态规划和回溯等通用算法思想。贪心算法每次做出局部最优决策,但并不保证全局最优解;动态规划通过分解问题并存储子问题的解来避免重复计算;回溯法则在搜索解空间树时,通过撤销之前的...

    课程设计---克鲁斯卡尔算法求最小生成树.doc

    克鲁斯卡尔算法是一种基于贪心策略的算法,它逐步添加边,每次选择当前未添加到树中且不会形成环的边,直到连接所有顶点。 1. **需求分析** - **设计题目**:最小生成树 - **设计任务**:用户可以输入自定义的无...

    leetcode book pdf 中文

    本书涵盖了从基础到高级的各种算法题目,包括但不限于双指针、字符串处理、链表操作、数学问题、位操作、动态规划和贪心算法等。每道题后面标注的[E]、[M]、[H]分别代表题目难度,即轻松(Easy)、中等(Medium)和困难...

    PHPCHINA论坛志6月.pdf

    到了中级阶段,算法学习者需要学习更为复杂的算法概念和应用,包括图论的基本算法(如深度优先搜索、广度优先搜索)、动态规划的进阶应用、贪心算法等。这个阶段需要解决的问题通常更具有挑战性,并且需要更多的逻辑...

    暑假ACM训练解题报告(题解和分析)

    接着,报告可能会按照不同的算法类别,如排序、搜索、图论、动态规划、贪心、回溯、数学问题等,进行解题报告的组织。例如,作者可能详细描述了如何使用快速排序解决一个排序类问题,如何应用深度优先搜索或广度优先...

    leetcode题库-JavaStudy:学习Java的一些笔记,以及日常感受,欢迎Star

    3. **算法**:排序(快速排序、归并排序、堆排序等)、搜索(深度优先搜索、广度优先搜索)、动态规划、贪心算法、回溯法、分治策略等。LeetCode主要考察的就是这些问题解决策略,掌握这些算法对提升编程能力至关...

    2020年3月9日总结

    掌握排序、搜索、动态规划、贪心策略等基础算法是编写出高效代码的前提。这些算法不仅需要理解其原理,更需要通过大量的练习去熟悉它们的运用场景和技巧,以便在比赛中迅速准确地调用。然而,基础算法掌握的熟练程度...

    Leetcode-everyday

    在LeetCode上,Python被广泛用于解决各种算法题,包括但不限于搜索、排序、图论、动态规划、回溯、贪心策略等。通过每天练习,开发者可以逐步提高对Python语言的掌握程度,同时提升算法思维和问题解决能力。 在...

Global site tag (gtag.js) - Google Analytics