- 1、本文档共31页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
ACM程序的计设基本之贪心法
贪心算法;贪心法的设计思想 ; 贪心法在解决问题的策略上目光短浅,只根据当前已有的信息就做出选择,而且一旦做出了选择,不管将来有什么结果,这个选择都不会改变。换言之,贪心法并不是从整体最优考虑,它所做出的选择只是在某种意义上的局部最优。
这种局部最优选择并不总能获得整体最优解(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)。
文档评论(0)