算法201104-贪心1.ppt

第四章贪心算法
贪心算法的基本思想
背包问题的贪心求解
最小生成树
最短路径
最优归并模式
哈夫曼编码
GREEDY
贪心算法的基本思想
背包问题的贪心求解
贪心算法
求解问题的类型-解与解向量
现实中有这样的问题:
有n个输入和一组约束条件。
解的结构对应为一个n维向量(x1,x2,,xn),其中xi(i=1,2,,n) 对应为输入元素的相应取值(具体根据实际问题不同取值方法不同)。
(x1,x2,,xn)需满足相应约束条件
满足约束条件的任意一组输入称为问题的一组可行解;使目标函数达到最大或最小(根据实际问题的要求)的可行解称为最优解。贪心法用于求解的问题,其目标往往是求最优解。
例子-1
1 找零钱问题:以人民币1元,2元,5元,10元,20元,50元,以99元为例,要求所找的张数最少?
99=50+20*2+5+2*2
2 古代有一位医师到某个到处都是草药的山洞里采药,山洞里有一些不同的草药,同时每种草药只有一株,采每一株都需要一些时间,每一株都有它自身的价值。只能在一段时间内采药,在这段时间里,医师可以采到一些草药,医师了解每种草药需要的时间及其价值。如果是你,你应该如何采药才可以让采到的草药的总价值最大。
例子-2
3 [ 渴婴问题] 有一个非常渴的、聪明的小婴儿,她可能得到的东西包括一杯水、一桶牛奶、多罐不同种类的果汁、许多不同的装在瓶子或罐子中的苏打水,即婴儿可得到n 种不同的饮料。根据以前关于这n 种饮料的不同体验,此婴儿知道这其中某些饮料更合自己的胃口,因此,婴儿采取如下方法为每一种饮料赋予一个满意度值:饮用1盎司第i 种饮料,对它作出相对评价,将一个数值si 作为满意度赋予第i 种饮料。
但当前情况是:具有最大满意度值的饮料有时并没有足够的量来满足此婴儿解渴的需要。设ai是第i 种饮料的总量(以盎司为单位),而此婴儿需要t盎司的饮料来解渴,那么,需要饮用n种不同的饮料各多少量才能满足婴儿解渴的需求呢(最大满意度)?
例子-3
4 [最小代价通讯网络] 城市及城市之间所有可能的通信连接可被视作一个无向图,图的每条边都被赋予一个权值,权值表示建成由这条边所表示的通信连接所要付出的代价。包含图中所有顶点(城市)的连通子图都是一个可行解。设所有的权值都非负,则所有可能的可行解都可表示成无向图的一组生成树,而最优解是其中具有最小代价的生成树。
例子-4
城市高速路问题
其他问题
Go Home
Travel
Investment
Budget
贪心法
向着某一目标(最大、最小、最优化、最短、其他?),考虑问题的求解方法,每一步尽量与目标要求一致,逐步求解,步步为“赢”
活动安排问题
设有n个活动的集合E = {1, 2, …, n},其中每个活动都要求使用同一资源,且在同一时间里只能有一个活动可以使用该资源。现要求给出一个活动安排,使得利用该资源活动为最多。
每个活动i都有使用该资源的一个启始时间si和一个结束时间fi,si<fi,其占用资源的时间为半开区间[si , fi)。若区间[si , fi)与区间[sj , fj)不相交,则称活动i与活动j是相容的。
活动安排问题就是求E的最大相容活动子集。
会场或教室