贪心算法.ppt

第六章贪心算法一、基本概念所谓贪心算法是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优解。贪心算法没有固定的算法框架,算法设计的关键是贪心策略的选择。必须注意的是,贪心算法不是对所有问题都能得到整体最优解,选择的贪心策略必须具备无后效性,即某个状态以后的过程不会影响以前的状态,只与当前状态有关。所以对所采用的贪心策略一定要仔细分析其是否满足无后效性。二、。。,得到子问题的局部最优解。。三、适用问题贪心策略适用的前提是:局部最优策略能导致产生全局最优解。四、实现框架从问题的某一初始解出发;while(能朝给定总目标前进一步){利用可行的决策,求出可行解的一个解元素;}由所有解元素组合成问题的一个可行解;五、贪心策略的选择因为用贪心算法只能通过解局部最优解的策略来达到全局最优解,因此,一定要注意判断问题是否适合采用贪心算法策略,找到的解是否一定是问题的最优解。【例1】排队打水问题有N个人排队到R个水龙头去打水,他们装满水桶的时间为T1,T2,…,Tn为整数且各不相等,应如何安排他们的打水顺序才能使他们花费的时间最少?【算法分析】由于排队时,越靠前面的计算的次数越多,显然越小的排在越前面得出的结果越小(可以用数学方法简单证明,这里就不再赘述),所以这道题可以用贪心法解答,基本步骤:(1)将输入的时间按从小到大排序;(2)将排序后的时间按顺序依次放入每个水龙头的队列中;(3)统计,输出答案。【样例输入】42//4人打水,2个水龙头2645//每个打水时间参考程序主要框架如下:cin>>n>>r;memset(s,0,sizeof(s));//初始化j=0;minx=0;for(i=1;i<=n;++i)//用贪心法求解{j++;if(j==r+1)j=1;//前r个人为一组,第r+1个人回到第一个水龙s[j]+=a[i];//加上等待时间minx+=s[j];}cout<<minx;//输出解答【样例输出】23//总共花费时间【例2】均分纸牌(NOIP2002)有N堆纸牌,编号分别为1,2,…,N。每堆上有若干张,但纸牌总数必为N的倍数。可以在任一堆上取若干张纸牌,然后移动。移牌规则为:在编号为1堆上取的纸牌,只能移到编号为2的堆上;在编号为N的堆上取的纸牌,只能移到编号为N-1的堆上;其他堆上取的纸牌,可以移到相邻左边或右边的堆上。现在要求找出一种移动方法,用最少的移动次数使每堆上纸牌数都一样多。例如N=4,4堆纸牌数分别为:① 9 ② 8 ③ 17 ④ 6移动3次可达到目的:从③取4张牌放到④(981310)->从③取3张牌放到②(9111010)->从②取1张牌放到①(10101010)。【输入格式】N(N堆纸牌,1<=N<=100)A1A2…An(N堆纸牌,每堆纸牌初始数,l<=Ai<=10000)【输出格式】所有堆均达到相等时的最少移动次数。【样例输入】 4 98176【样例输出】 3【算法分析】如果你想到把每堆牌的张数减去平均张数,题目就变成移动正数,加到负数中,使大家都变成0,那就意味着成功了一半!拿例题来说,平均张数为10,原张数9,8,17,6,变为-1,-2,7,-4,其中没有为0的数,我们从左边出发:要使第1堆的牌数-1变为0,只须将-1张牌移到它的右边(第2堆)-2中;结果是-1变为0,-2变为-3,各堆牌张数变为0,-3,7,-4;同理:要使第2堆变为0,只需将-3移到它的右边(第3堆)中去,各堆牌张数变为0,0,4,-4;要使第3堆变为0,只需将第3堆中的4移到它的右边(第4堆)中去,结果为0,0,0,0,完成任务。每移动1次牌,步数加1。也许你要问,负数张牌怎么移,不违反题意吗?其实从第i堆移动-m张牌到第i+1堆,等价于从第i+1堆移动m张牌到第i堆,步数是一样的。如果张数中本来就有为0的,怎么办呢?如0,-1,-5,6,还是从左算起(从右算起也完全一样),第1堆是0,无需移牌,余下与上相同;再比如-1,-2,3,10,-4,-6,从左算起,第1次移动的结果为0,-3,3,10,-4,-6;第2次移动的结果为0,0,0,10,-4,-6,现在第3堆已经变为0了,可节省1步,余下继续。参考程序主要框架如下:cin>>n; ave=0;step=0; for(i=1;i<=n;++i) { cin>>a[i];ave+=a[i];//读入各堆牌张数,求总张数ave } ave/=n;//求牌的平均张数ave for(i=1;i<=n;++i)a[i]-=a