- 浏览: 3507500 次
- 性别:
- 来自: 杭州
文章分类
- 全部博客 (1491)
- Hibernate (28)
- spring (37)
- struts2 (19)
- jsp (12)
- servlet (2)
- mysql (24)
- tomcat (3)
- weblogic (1)
- ajax (36)
- jquery (47)
- html (43)
- JS (32)
- ibatis (0)
- DWR (3)
- EXTJS (43)
- Linux (15)
- Maven (3)
- python (8)
- 其他 (8)
- JAVASE (6)
- java javase string (0)
- JAVA 语法 (3)
- juddiv3 (15)
- Mule (1)
- jquery easyui (2)
- mule esb (1)
- java (644)
- log4j (4)
- weka (12)
- android (257)
- web services (4)
- PHP (1)
- 算法 (18)
- 数据结构 算法 (7)
- 数据挖掘 (4)
- 期刊 (6)
- 面试 (5)
- C++ (1)
- 论文 (10)
- 工作 (1)
- 数据结构 (6)
- JAVA配置 (1)
- JAVA垃圾回收 (2)
- SVM (13)
- web st (1)
- jvm (7)
- weka libsvm (1)
- weka屈伟 (1)
- job (2)
- 排序 算法 面试 (3)
- spss (2)
- 搜索引擎 (6)
- java 爬虫 (6)
- 分布式 (1)
- data ming (1)
- eclipse (6)
- 正则表达式 (1)
- 分词器 (2)
- 张孝祥 (1)
- solr (3)
- nutch (1)
- 爬虫 (4)
- lucene (3)
- 狗日的腾讯 (1)
- 我的收藏网址 (13)
- 网络 (1)
- java 数据结构 (22)
- ACM (7)
- jboss (0)
- 大纸 (10)
- maven2 (0)
- elipse (0)
- SVN使用 (2)
- office (1)
- .net (14)
- extjs4 (2)
- zhaopin (0)
- C (2)
- spring mvc (5)
- JPA (9)
- iphone (3)
- css (3)
- 前端框架 (2)
- jui (1)
- dwz (1)
- joomla (1)
- im (1)
- web (2)
- 1 (0)
- 移动UI (1)
- java (1)
- jsoup (1)
- 管理模板 (2)
- javajava (1)
- kali (7)
- 单片机 (1)
- 嵌入式 (1)
- mybatis (2)
- layui (7)
- asp (12)
- asp.net (1)
- sql (1)
- c# (4)
- andorid (1)
- 地价 (1)
- yihuo (1)
- oracle (1)
最新评论
-
endual:
https://blog.csdn.net/chenxbxh2 ...
IE6 bug -
ice86rain:
你好,ES跑起来了吗?我的在tomcat启动时卡在这里Hibe ...
ES架构技术介绍 -
TopLongMan:
...
java public ,protect,friendly,private的方法权限(转) -
贝塔ZQ:
java实现操作word中的表格内容,用插件实现的话,可以试试 ...
java 读取 doc poi读取word中的表格(转) -
ysj570440569:
Maven多模块spring + springMVC + JP ...
Spring+SpringMVC+JPA
每一个贪心算法的背后,总有一个动态规划在默默的陪着。
----------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; } }
发表评论
-
snmp
2020-04-13 11:07 395https://www.iteye.com/blog/zhan ... -
snmp
2020-04-10 21:33 525https://blog.csdn.net/qq_333141 ... -
服务器监控软件
2019-12-31 11:07 470[ERROR] org.hyperic.sigar.Sigar ... -
多数据源
2019-12-23 22:09 415https://gitee.com/baomidou/dyna ... -
mybatis多数据源
2019-12-23 18:09 410https://blog.csdn.net/qq_288042 ... -
springboot ueditor
2019-12-17 18:26 348https://blog.csdn.net/u01216982 ... -
java支持多数据源
2019-12-13 15:59 415spxcms是否支持多数据源 ... -
java日志
2019-12-10 12:01 259https://blog.csdn.net/peng_wei_ ... -
spring 多数据源
2019-12-06 09:55 391https://www.jb51.net/article/10 ... -
idea
2019-12-04 17:13 363https://blog.csdn.net/dengachao ... -
手机大屏
2019-11-30 16:02 304http://demo.demohuo.top/modals/ ... -
quarz配置
2019-11-08 11:48 421https://blog.csdn.net/BryantLmm ... -
mysql同步
2019-11-06 12:20 313https://blog.csdn.net/baidu_418 ... -
nginx配置多个服务
2019-11-04 20:35 712https://blog.csdn.net/everljs/a ... -
h5 加壳
2019-11-04 16:05 582https://jingyan.baidu.com/artic ... -
jeui 前端框架
2019-10-22 14:30 1122http://www.jemui.com/demo/ http ... -
jeui 维护
2019-10-22 14:29 2http://www.jemui.com/demo/ htt ... -
jeui 维护
2019-10-22 14:29 2http://www.jemui.com/demo/ -
jeui 维护
2019-10-22 14:29 2http://www.jemui.com/demo/ -
jeui 维护
2019-10-22 14:29 2http://www.jemui.com/demo/
相关推荐
贪心算法 贪心算法 贪心算法 贪心算法 贪心算法 贪心算法
贪心算法贪心算法贪心算法贪心算法贪心算法贪心算法贪心算法贪心算法贪心算法贪心算法贪心算法
贪心算法 贪心算法的理解 贪心算法的算法 贪心算法的讲解
贪心算法、分治算法和动态规划的区别 贪心算法和动态规划.pdf
贪心算法 找零钱 c语言 简洁 绝对无误
贪心算法是一种对某些求最优解问题的更简单、更迅速的设计技术。贪心算法的特点是一步一步地进行,常以当前情况为基础根据某个优化测度作最优选择,而不考虑各种可能的整体情况,省去了为找最优解要穷尽所有可能而...
算法作业-贪心算法论文含实例,可以借鉴其中的算法原理。加深自己的理解
TSP贪心算法C++ TSP贪心算法C++
算法这么课程的结课论文,以最短路径算法为例描述贪心算法
贪心算法贪心算法贪心算法贪心算 背包问题背包问题背包问题
贪心算法 背包问题 c语言 绝对无误 运行成功
贪心算法和动态规划以及分治法的区别? (1) 贪心算法和动态规划.pdf
用贪心算法解单源最短路径问题 明确单源最短路径问题的概念;利用贪心算法解决单源最短路径问题;并通过本例熟悉贪心算法在程序设计中的应用方法。
实验2装箱问题-贪心算法
贪心算法之最优合并问题
贪心算法是一个比较常用的算法…… 所谓贪心算法是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优解。 贪心算法不是对所有问题都...
使用贪心算法求解tsp问题,使用vc实现,资源中包含有程序的文档,包含tsp问题说明、贪心算法分析和程序源码。
贪心算法背包问题c语言实现贪心算法背包问题c语言实现贪心算法背包问题c语言实现贪心算法背包问题c语言实现贪心算法背包问题c语言实现贪心算法背包问题c语言实现贪心算法背包问题c语言实现贪心算法背包问题c语言实现...
贪心算法 贪心算法贪心算法 贪心算法 贪心算法JAVA语言