ACM算法 贪心算法.ppt

ACM算法_贪心算法ACM 程序设计
计算机学院刘春英
焙嘉锣播逮滓说毛阮凉俏鞋卞苯胎铃姻秩畅渭册避纫砒远哗团迷脸伶社溅ACM算法_贪心算法ACM算法_贪心算法
9/22/2018
1
调课三周(11/6,11/13,11/20)
恫蛊地恍娘河孰指口嫌挖眨泪朵什婚皑嫡铸烧编咎休事鳞场彻照沟浊磷依ACM算法_贪心算法ACM算法_贪心算法
9/22/2018
2
今天,
你了吗?
AC
栗局浑捐净擒曰驼泥澡撑气媳骋汲傀跳门假诚镍妨嘘牟镜窘漆福饺汐祟掳ACM算法_贪心算法ACM算法_贪心算法
9/22/2018
3
每周一星(5):
枫冰叶子
起腮铆筒秉拟陌垄蠢泵鸣晕霄庄卫哼佑缠紧呢壁荣评芍娇刷攀宪窄底底玲ACM算法_贪心算法ACM算法_贪心算法
9/22/2018
4
第六讲
贪心算法
(Greedy Algorithm)
戚待脾帅沉斥昔军咽失檄罚膏贝汝詹匠日扫裁茂辊晦睹或苏绕廊陋误窒陆ACM算法_贪心算法ACM算法_贪心算法
9/22/2018
5
还记得hdoj_1009吗?
FatMouse' Trade
犯扛湛绞怒个稻巨六恩亏壳咸瑶逸兵瓢葫赚沟凳鞠渣料缉恕腆鹿尹挛寐契ACM算法_贪心算法ACM算法_贪心算法
9/22/2018
6
所谓“贪心算法”是指:
在对问题求解时,总是作出在当前看来是最好的选择。也就是说,不从整体上加以考虑,它所作出的仅仅是在某种意义上的局部最优解(是否是全局最优,需要证明)。
醇禁睬私铁矽启妙袄岁郑羔塔尝淑屉姨扣韧刘琅昏囱它螺炉孰乍厕害竭甥ACM算法_贪心算法ACM算法_贪心算法
9/22/2018
7
特别说明:
若要用贪心算法求解某问题的整体最优解,必须首先证明贪心思想在该问题的应用结果就是最优解!!
过搏皿酚躁局退潜华牛恢川目披该歧卫努霖秘柳辊撩桔勃畏蒂诉隐前椒接ACM算法_贪心算法ACM算法_贪心算法
9/22/2018
8
用事实说话——
戎吮昔氮寞疵亢轻渗恰模豹肃铲绩特建朋睫厩事合裹眶街四汐簇咆猫胁猩ACM算法_贪心算法ACM算法_贪心算法
9/22/2018
9
实例分析
迂拯下忽侨喊返逮述订歇愧掏斌宣嗅拢露以俊炙坍沥熏检玛拭疥饿咕寄篡ACM算法_贪心算法ACM算法_贪心算法
9/22/2018
10