贪心策略.ppt

贪心法
它是求解优化问题的一种常用算法,也最接近人们日常思维的一种算法。在现实生活中,我们经常下意识的做贪心选择。例如,在商场购物时,总是选购物美价廉的物品。质量相同的情况下,首选价位低的物品。
什么是贪心法
贪心法:是从问题的某一初始状态出发,通过逐步构造最优解的方法向给定的目标前进,并期望通过这种方法产生最优解,它是一种解题策略,也是一种解题思想。
做出贪心决策的依据称为贪心准则。贪心准则(策略)
贪心方法
贪心与递推不同:贪心推进的每一步不是依据某一固定的递推式,而是做当时看似最佳的贪心选择,不断地将原问题归纳为更小的相似问题。更小的相似子问题(与子母树”。还有,
在有些最优化问题中,采用贪心法不能保证一定得到最优解,归纳分析选择贪心准则是正确解决贪心问题的关键。能否一开始就考虑采用动态规划方法,而不采用贪心法?
引例
给定N行M列的正整数矩阵,要求从每行中选出1个数,使得选出的N个数的和最大。

分析:要使总和最大,则每个数要尽可能大,自然应该选每行中最大的那个数。因此,我们设计出如下算法:
读入N, M,矩阵数据;
Total := 0;
for I := 1 to N do begin {对N行进行选择}
选择第I行最大的数,记为K;
Total := Total + K;
end;
输出最大总和Total;
贪心法的优缺点:
解题的步骤:

,根据局部最优策略,向目标前进 (或较优)解
优点:思维复杂度低,运行效率高,计算量小等,是数学竞赛中的有力武器。
缺点:通常很难找到一种简单可行并保障正确的贪心思路。
问题:
什么样的问题适合于用贪心法来解决?
用贪心法解题时,如何判断能否保证得到最优解?若不能得到最优解,该如何处理?
典型例题
【例1】删数问题
通过键盘输入一个高精度的正整数n(n≤240位),去掉其中任意s个数字后,剩下的数字按原左右次序将组成一个新的正整数。编程对给定的n和s,寻找一种方案,使得剩下的数字组成的新数最小。
输入:n
s
输出:最后剩下的最小数
问题分析
由于正整数n的有效位数最大可达240位,所以可采用字符串类型来存储n
应如何来确定该删除哪s位呢?是不是只要删掉最大的s个数字就可以了?
否,例:735814,删除最大的4,得31>14
问题分析
例如: n=735814
s=4
删数的过程如下:
n=735814 {删掉8}
n=73514 {删掉7}
n=3514 {删掉5}
n=314 {删掉4} {删掉3}
n=31 n=14
问题分析
例如:n=178543
s=4
删数的过程如下:
n=178543 {删掉8}
n=17543 {删掉7}
n=1543 {删掉5}
n=143 {删掉4}
n=13 {解为13}