ACM程序的计设基本之贪心法.ppt

贪心算法;贪心法的设计思想 ; 贪心法在解决问题的策略上目光短浅，只根据当前已有的信息就做出选择，而且一旦做出了选择，不管将来有什么结果，这个选择都不会改变。换言之，贪心法并不是从整体最优考虑，它所做出的选择只是在某种意义上的局部最优。 这种局部最优选择并不总能获得整体最优解（Optimal Solution），但通常能获得近似最优解（Near-Optimal Solution）。;引例 [找零钱];算法思想;贪心法求解的问题的特征： （1）最优子结构性质 当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质，也称此问题满足最优性原理。 （2）贪心选择性质 所谓贪心选择性质是指问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来得到。;2 贪心法的求解过程 ; （3）解决函数solution：检查解集合S是否构成问题的完整解。例如，在付款问题中，解决函数是已付出的货币金额恰好等于应付款。 （4）选择函数select：即贪心策略，这是贪心法的关键，它指出哪个候选对象最有希望构成问题的解，选择函数通常和目标函数有关。例如，在付款问题中，贪心策略就是在候选集合中选择面值最大的货币。 （5）可行函数feasible：检查解集合中加入一个候选对象是否可行，即解集合扩展后是否满足约束条件。例如，在付款问题中，可行函数是每一步选择的货币和已付出的货币相加不超过应付款。 ;贪心法的一般过程 Greedy(C) //C是问题的输入集合即候选集合 { S={ }; //初始解集合为空集 while (not solution(S)) //集合S没有构成问题的一个解 { x=select(C); //在候选集合C中做贪心选择 if feasible(S, x) //判断集合S中加入x后的解是否可行 S=S+{x}; C=C-{x}; } return S; };例1、 活动安排问题;例1、活动安排问题; a 和 b 事件的开始时刻小于结束时刻 Begin[a]End[a] Begin[b]End[b] b 事件的开始时刻大于等于 a 事件的结束时刻,即 Begin[b] = End[a] 记为 b a 这时 b 事件与 a 事件不重叠.;例1、活动安排问题; 找出 时间上不重叠的事件： 2#,9# 2#,8#,10# 2#,8#,11# 0#,3#,8#,10# 0#,3#,8#,11# 0#,1#,5#,8#,10# 0#,1#,5#,8#,11# 0#,1#,6#,10# 0#,1#,6#,11#; 每个都选择最早结束的序列---贪心策略 0#-1#-5#-8#-10# 这是最长序列 ; #includeiostream.h const int N=12; void OtputResult(int Select[N]); { cout“{ 0”; for( int i=1; iN; i++ ) if ( Select[ i ]=1) cout“,” i ; cout “ } “ endl; }; void main( ) { int Begin[N]={1,3,0,3,2,5,6,4,10,8,15,15}; int End[N]={3,4,7,8,9,10,12,14,15,18,19,20}; int Select[N]={0,0,0,0,0,0,0,0,0,0,0,0}; int i=0;//当前最早结束的事件 //当前可选事件的最早开始时间 int TimeStart=0;; while( i N ) { if ( Begin[ i ]=TimeStart ) { Select[ i ]=1; TimeStart=End[ i ]; } i ++; } OutputResult ( Select ) ; } ;3、贪心算法的基本要素;3 贪心算法的基本要素;3 贪心算法的基本要素;例2、 背包问题 ; 于是，背包问题归结为寻找一个满足约束条件式7.1，并使目标函数式7.2达到最大的解向量X=(x1, x2, …, xn)。