贪心算法 入门.

Slides:



Advertisements
Similar presentations
熱烈歡迎 各級長官 貴賓 全體會員 蒞臨會場.
Advertisements

项目四 网店推广与营销 4.1 店内推广与营销. 教学目的: 通过本节内容的学习,帮助学生了解消费者保障服务分类,理解店内活动是运 营店铺时不可缺少的一些营销活动。 知识要求: 1. 了解申请加入消费者保障服务项目的条件 2. 了解店内活动如满就送、限时打折、搭配套餐、优惠券的设置 技能目标: 1.
广西 2014 年 “ 区培计划 ” 学前教育远程培 训 总结简报 南宁马山县幼教 1 班 莫毅.
教育部 輔導教官:林家豪 年度育達商職紫錐花運動 強化反毒健康小學堂輔導課程 簡 報.
中职教师省级网络培训 使用说明 南京中华中等专业学校教研处 平台登陆 登录 (江苏教师教育) 在页面右侧找到登录框,填写用户名、密码进入系统.
“ 税融通 ” 业务简要介绍. + 一、什么是 “ 税融通 ” ? + “ 税融通 ” 是指银行金融机构根据中小微企业 纳税情况,向依法诚信的中小微企业提供 一定数额的信用贷款或担保贷款的金融产 品。
学年 江西省教师全员远程培训指南. 培训学习及考核时间安排 学习时间: 2013 年 10 月 年 1 月 15 日 考核时间: 2014 年 3 月 1 日 年 3 月 30 日.
-- 八 (19) 班第二学期期中家长会 、关于期中考试 2 、关于班级常规活动 3 、关于会考、体育 4 、关于自主招生 5 、给家长的一些建议.
《礼记 · 学记》学习心得报告 教育的本质与运用 主讲人:徐浩明. 一、认识什么是教育 二、明白教育的本质 三、如何落实德行教育.
山东理工大学成人高等教育 新生入学指南. 如何获悉学院的通知公告等? 1. 网站。所有的通知公告等都通过远程与继 续教育学院网站 发布, 同学们应每周登录 “ 学生工作室 ” 或 “ 函授教育 ” 关注是否有新的通知公告。
此时此刻,我还是爱你?还是不爱? 我想,我不爱你了! 因为我累了, 我爱得累了 …………. 你的好对于我来说 像是一种无形的压力 每次你对我好 我都觉得好难承受 你越是对我好 我就越怕你 总是想逃避。
财务处目前共有 50 人,其中事业编 32 人,非事业编 18 人。分为 6 个科室,分别是会计核算科、资金结算中心、综合管理科、预算管理科、 基建财务科和一卡通中心。 会计核算科主要业务为收入入账、费用报销审核等。 资金结算中心主要业务为资金收付、开具发票、学费管理。 综合管理科主要业务是工资及住房公积金管理、税务管理、收费项目.
心理咨询师的个人品牌建设 徐钧 南嘉心理咨询师部落(俱乐部) 申请 QQ 酒香还怕巷子深 你需要一个 “ 个人品牌 ” 以让别人知道你 你是谁? 你的目标是什么? 你要成为什么样的人? 你能做什么? 你会怎样做? 怎么与你有效沟通?
房地产法 主讲教师:龙慧峰 QQ: 电话: 法律实质上既是物质的又是意识形态的这一 事实是与以下事实相联系的:法律既是从 整个社会的结构和习惯自上而下发展而来, 又是从社会中的统治阶级们的政策和价值 中自上而下移动。 —— 【美】伯尔曼《法律与革命》
某中学一青少年因迷上网络游戏,视力由1. 2下降到0
加强工作室资源建设 提升网络辐射影响力 林月周工作室
和合共美,同修共进 ——工作室三年感言 何伟俊
发挥学科优势 打造“互联网+”党建工作模式
無性生殖是由親代直接產生新的個體,並不涉及配子的生成與結合。
生 命 教 育 「讓愛傳出去」 組別:第10組 組員:495i0004 陳靜宜 495i0009 郭品秀 495i0011 林千玉
坚持群众路线 做到“三严三实” 内蒙古直属机关工委党校 裴聚斌 电话:
新所得税申报表如何填写 注册税务师 注册会计师 高级会计师 注册资产评估师 注册土地估价师 注册房地产估价师 主讲人:林溪发
校园法治网 ◎传播校园法制文明 ◎营造校园法治环境
人类行为的起源 康复医学系 王海成 医学教授 精神科主任医师 QQ: 手机:
我的未来,我做主之 坚持不懈,直到成功。 电话: QQ: 时间:2013年5月27日 肖亚平.
自读高晓声的小说 《陈奂生上城》 写一篇800以上的感悟文章.
高考成功心理 平凉一中 刘雅娟.
2012江西(九江吉安)事业单位 公共基础知识 备考指导 主讲:罗红军 qq: 新浪微博:罗红军的微博
运筹帷幄 决胜高考 应怎样去做? 湖北黄冈中学 余利平 QQ:
幼儿园环境创设 成智客服QQ:
工作中的九型人格 主讲嘉宾:梁旭 ---九型人格应用系列课程 介绍自己 有多少听过九型 课程纪律 课程时间 工作中的九型人格
客 家 仙 草 台北縣中和市秀山國民小學 五 年 十 班 王 靖 婷.
兵 车 行 杜甫.
计算机基础知识 陈嘉明 玉溪农业职业技术学院.
藝術與人文---太鼓.
关于“人肉搜索”的滥用及其所引发的 “网络暴力”的道德与法律思考
手太阳小肠经.
自然的食物就是你最好的醫生 上課之前先聽一首歌~稻香 歌詞、音樂還不錯和大家分享一下
第2课 大一统与秦朝中央集权制度的确立 课标要求: 知道“始皇帝”的来历和郡县制建立的史实,了解中国古代中央集权制度的形成及其影响。
第十四篇 答李翊書 韓 愈.
责任 感恩 安全 开学第一课 广西柳州市柳东新区雒容镇盘古小学王秀娅 QQ:
校园信息管理系统 河北科技大学网络中心 2000/4/10.
怎樣吃才健康? 賴亭竹.
史記 貨 殖 列 傳                                                            商业篇.
胫腓骨骨折.
  中国技术交易信息服务平台 中国技术市场管理促进中心.
游泳四式技術分析暨初級教法.
第二单元(6-9课) 近代化的探索.
用“自言自语法”提高学生 英语口头表达能力 李奉栖.
高考复习专题 文言文翻译
新帝國主義開港 (一)臺灣成為侵略者目標 1.背景: A.買賣利豐=鴉片進口+米、糖、樟腦、煤炭出口 B.地理位置優越=航行安全+商貿中心 2.新帝國主義: A.19C中:英、法、美、日為主 B.臺被迫開港通商,割地賠款,簽訂不平等條約.
徵收苗栗市福全段147、1588及文心段10、11地號等4筆土地之
佳力科技 防爆叉车的应用、发展 浙江佳力科技股份有限公司.
吳 慎 宜 文化大學勞動暨人力資源系講師 FM91.3 台北勞工教育電台台長
讲 义 大家好!根据局领导的指示,在局会计科和各业务科室的安排下,我给各位简要介绍支付中心的工作职能和集中支付的业务流程。这样使我们之间沟通更融洽,便于我们为预算单位提供更优质的服务。 下面我主要从三方面介绍集中支付业务,一是网上支付系统,二是集中支付业务流程及规定等,
中国人民公安大学经费管理办法(试行) 第一章总则 第四条:“一支笔” “一支笔”--仅指单位主要负责人。负责对本 单位的经费进行审核审批。
烟花爆竹企业开复工 安 全 培 训参考课件 浏 阳 市 安 监 局.
常规免疫接种率 监测 免疫规划科 章梦然.
入托、入学儿童预防接种证查验 武平县疾病预防控制中心 林传贵
食物在口腔里的变化.
酒 中国是一个 文化历史悠久的国家.
理解常见文言实词在文中的含义.
词类活用.
杨玉环(公元719-756年) 杨玉环,名玉环,字太真,唐玄宗李隆基的宠妃,原名杨芙蓉(故有芙蓉出水),出生地为四川成都,祖籍山西永济。杨贵妃自小习音律,善歌舞,姿色超群。曾祖父杨汪是隋朝的上柱国、吏部尚书,唐初被李世民所杀,父杨玄琰(yǎn),是蜀州(四川崇州)司户,其叔父杨玄璬(jiǎo)曾任河南府士曹,杨玉环的童年是在四川度过的,10岁左右,父亲去世,她寄养在洛阳的三叔杨玄璬家。后来又迁往山西永乐(山西永济)。 
左迁至蓝关示侄孙湘 韩愈.
科普说明文 生物入侵者 高天群.
文化底蕴与作文 第一节:底蕴成句 【温馨点拨】:底蕴成句是把含有文化底蕴的内容表达成句。底蕴成句有三种情况:
微信商城系统操作说明 色卡会智能门店.
資管人的規劃 -學校生活資源 1 1.
大綱 一.受試者之禮券/禮品所得稅規範 二.範例介紹 三.自主管理 四.財務室提醒.
Presentation transcript:

贪心算法 入门

本节将介绍以下内容: 贪心算法的基本思想 贪心算法的基本思路 贪心算法的进行过程 基本题型与例题解析

贪心算法的基本思想 在不可预见后面会发生什么的情况下,我们都会选择在当前情况 下看起来是最好的选择。这就是贪心算法的基本思想。 那么贪心算法对于整体来说,不一定作出了最好的决策,只是在 一定意义上是局部最优解。不过对许多问题,它作出的局部最优 解的组合就是整体最优解。最小生成树的Prim算法和Kruskal算 法就是贪心算法的经典应用。 在某些情况下,我们并不需要最优解,只是需要一个较优解,那 么贪心算法执行简单,是很好的选择,在现实中应用广泛。

贪心算法的基本要素 一个问题可以贪心,需要有以下两个性质: 贪心选择性:这个问题的整体最优解可以通过一系列局部最优的 选择来达到。在后面有动态规划的内容,贪心与动态规划都是寻 找最优解的手段,但是动态规划是从后往前寻找答案,而贪心是 从前往后寻找答案,所以贪心相比动态规划有一定的局限性,但 由于构造简单,仍是一个重要的算法。 最优子结构性质:这个问题的最优解包含其子问题的最优解时, 这个问题就有最优子结构性质。如果一个问题不拥有最优子结构 性质,就不能用贪心与动态规划解决。

贪心算法的基本思路 从问题的初始状态开始,往最终状态前进,每次都选择当前最好 的选择。当到达最终状态时停止;如果不能再作出选择,又未到 达最终状态,那么这个问题不能或利用贪心思想不能到达最终状 态,停止。 存在的问题: 1.不能保证最后的解是最优解。 2.不能用来求最大或最小解问题。 3.只能求满足某些约束条件的可行解范围。

贪心算法的执行过程 有一个背包,其容量M一定。物品有若干个,要求尽可能让装入 背包中的物品的总价值最大,但是不能超过总容量。 思路1:每次挑选价值最大的物品,直到无法选择物品。 思路2:每次挑选重量最小的物品,直到无法选择物品。 思路3:每次选择单位重量价值最大的物品,直到无法选择物品。 无法选择物品两种情况。

思路1:选取价值最大 M=30 选择结果为A。 但是,更优的结果是选择B和C。说明思路1是不可行的。 物品ID A B C 物品重量 28 12 物品价值 30 20

思路2:选取重量最小 M=30 选择的结果为A和C。 但是,最优的结果是选择B,说明思路2也是不可行的。 物品ID A B C 物品重量 10 30 12 物品价值 15

思路3:选取单位重量价值最大 W=30 不加优化的情况下,选择是A。 但是,最优的选择是B和C。说明思路3也是不可行的。 物品ID A B 物品重量 28 20 10 物品价值

思路3:选择单位重量价值最大 加上一点优化,当单位重量价值相同的时候,先选择重量最小的。 这样对于上一组数据的选择是B和C,正确。 W=30 选择为B和C,但显然选择A更优,说明优化后的思路3还是错误的。 物品ID A B C 物品重量 30 15 10 物品价值

背包问题的解决 从上面的三种思路来看,该背包问题并不能用贪心解决。 一般来说,背包问题用贪心解决不能保证得到的是整体最优解, 所以背包问题需要用动态规划来解决。 但是经过这样三种思路的分析,应该对贪心的步骤有了一定的理 解。下面来解决一下贪心能够解决的问题。 是不是很失望?哈哈哈哈哈

种类一:一般贪心(交换)问题 HDU 1009 Fat Mouse’ Trade Fat Mouse 准备了M磅猫粮,准备和看守存放了他最喜欢的食物 -咖啡豆的房间的猫进行交易。猫看守着N间房间,第i间房间存放 了J[i]磅咖啡豆,交换所有咖啡豆需要F[i]磅的猫粮,FM不必交换 整个房间的咖啡豆,也就是说,他可以用(F[i]*a)%磅的猫粮交换 得到(J[i]*a)%磅咖啡豆。现在他请你帮忙,帮他交换到最多数量 的咖啡豆。

HDU 1009 Fat Mouse’ Trade Input: Output: 5 3 7 2 4 3 5 2 20 3 25 18 24 15 15 10 -1 -1 Output: 13.333 31.500 猫粮数 房间数 第一组数据,保留3位小数 咖啡豆数 猫粮数 猫粮数 房间数 第二组数据,保留3位小数 咖啡豆数 猫粮数 -1 -1 结束 结束,不进行处理

HDU 1009 Fat Mouse’ Trade 分析: 题目描述和之前的背包问题很像,但是题目多了一个可以用一部 分猫粮换取一部分咖啡豆的条件。如果那个背包问题也加入这样 的条件,那就可以保证背包能够装满,这样就可以用贪心去解决。 那么这个问题,可以选择之前的思路三,选择每单位猫粮换取的 咖啡豆最多的房间进行交易,直到猫粮用完。 得出解决方案后,先验证一下第一组数据,三个房间分别是 3.5;1.333;2.5,先换房间1和3的,都可以全部换到。剩下房间 2不能换到所有的咖啡豆,因为猫粮剩余1,只能换到1/3,那么 结果就是7+5+4*(1/3)=13.333,答案正确。 5 3 7 2 4 3 5 2 题解

类型二:时间安排问题(区间覆盖) HDU 2037 今年暑假不AC

HDU 2037 今年暑假不AC Output: 5 能完整地看5个节目 Input: 12 电视节目数量 1 3 某个节目开始时间和结束时间 3 4 0 7 3 8 15 19 15 20 10 15 8 18 6 12 5 10 4 14 2 9 0 输入0结束 Output: 5 能完整地看5个节目

HDU 2037 今年暑假不AC 分析: 时间安排问题,用贪心总能得到整体最优解,用数学归纳法可以 证明,可以自己尝试证明,从略。 可以先对所有的节目以结束时间从早到晚进行排序,结束时间相 同的时候,按照开始时间从早到晚排序。 然后看第一个节目,它的开始时间最早,结束时间最早,那么这 个节目是一定要看的。然后后面的节目都对比前一个看的节目的 结束时间,如果此时还在看上一个节目,那么继续看前一个节目, 放弃这一个节目。直到分析完所有节目。 题解

类型二:时间安排问题(区间覆盖) 这种题目还有一种变形,都是区间覆盖问题。 在一维空间,有一些线段,这些线段有可能会有重叠,要求去掉 其中一些线段,使得线段不重叠而且覆盖长度最长。 这个问题其实就是时间安排问题,但是如果没有遇见过,基本不 会想到用贪心可以解决。 如果这个问题不要求去掉线段,而是直接求总覆盖长度,就变成 了类型三:线段覆盖问题,实质上仍是区间覆盖问题。

类型三:线段覆盖问题(区间覆盖) I 1 2 3 4 5 6 7 8 9 10 s[i] 11 f[i] 12 13 15 这种类型和类型二非常类似,只需要稍加修改,排序的时候先按 照开始时间排序,再按结束时间排序。总长先记为线段1的全长, 然后线段2和线段1比较,如果线段2不与线段1重复,总长就加上 线段2的全长;如果线段2结束点在线段1结束点前,那么线段2长 度不计;如果线段2与1重复且结束点不在线段1内部,则总长加 上线段1结束点到线段2结束点的长度。 10 2 3 3 5 4 7 5 6 6 9 7 8 8 12 9 10 10 13 11 15 题解

类型四:数字组合问题 这种类型可以归类到类型一中,不过类型一说是交易类型,所以 这种就单独成一类好了。 这种题目可以简单,也可以难,难题一般是思路不好想。 例1:给出一些整数,要求对这些数字的各数位重新排序并组合, 使组成的数字最大。 解:题目说的是对数字的数位排序,那么肯定是把0-9所有数字个 数统计一下,按照9 8 7…0的顺序输出即可。

类型四:数字组合问题 Input: 5 5438 4452 21 402 248 0 Output: 8855444443222210 5 5438 4452 21 402 248 0 Output: 8855444443222210 数字个数 结束

类型四:数字组合问题 例2:HDU 5718 Oracle 题目给出一个不含前导零的正整数,要求将这个整数拆分成两个 不含前导零的正整数,使这两个数的和最大。如果不存在这样的 方案,输出Uncertain。 Input: 3 112 233 1 Output: 22 35 Uncertain Hint: 第一组拆分成21和1 第二组拆分成33和2 第三组无法拆分 数据组数

HDU 5718 Oracle 分析: 不能拆分的情况,有两种,1是只有一位,2是去掉0后只有一位, 在判断的时候这两种可以归为一种。例:1和10000。 能拆分的情况,一定是拆分成n-1位和1位的两个数,这个1位的 数,一定取除了0以外的最小的数。n-1位的数就像例1一样,从 大到小排好。题目要求输出和,进行一下大数加法就可以了。 题解

return 0; 如对知识点有问题可以联系: QQ:597916197 Mail:ocrosoft@ocrosoft.com 如对题目或题解有问题除了上面的联系方式, 也可以在题解页面评论进行评论。 15软件工程 李天阳