贪心算法实例

贪心算法实例贪心算法实例贪心算法一、贪心法的思想在实际问题中，经常会遇到求一个问题的最优解，这就是所谓的最优化问题。最优化问题往往包含一组限制条件和一个优化函数，符合条件的解决方案称为可行解，使优化函数取得最佳值的可行解称为最优解。贪心法是求解这类问题的一种常用算法，它的思想和做法是这样:从问题的某一个初始解出发，采用逐步构造(迄今为止)最优解的方法向给定的目标前进。在每个局部阶段，都做出一个看上去最优的决策 (即某种意义下的、或某个标准下的局部最优解)，并期望通过每次所做的局部最优选择，能够产生出一个全局...

贪心算法实例贪心算法一、贪心法的思想在实际问题中，经常会遇到求一个问题的最优解，这就是所谓的最优化问题。最优化问题往往包含一组限制条件和一个优化函数，符合条件的解决方案称为可行解，使优化函数取得最佳值的可行解称为最优解。贪心法是求解这类问题的一种常用算法，它的思想和做法是这样:从问题的某一个初始解出发，采用逐步构造(迄今为止)最优解的方法向给定的目标前进。在每个局部阶段，都做出一个看上去最优的决策 (即某种意义下的、或某个标准下的局部最优解)，并期望通过每次所做的局部最优选择，能够产生出一个全局最优解来。做出贪心决策的依据称为贪心准则(策略)。贪心与递推不同的是，推进的每一步不是依据某一固定的递推公式，而是做一个当时看似最佳的贪心选择，从而不断地将问题实例归纳为更小的相似子问题。在有些最优化问题中，采用贪心法求解不能保证一定得到最优解，这时可以采取一些变形的贪心法或其他解决最优化问题的方法(如动态规划方法)。下面我们通过几个应用实例来看看贪心法的应用。二、应用举例【例3】删数问题键盘输入一个高精度的正整数n(n的有效位数?240)，去掉其中任意s个数字后，剩下的数字按通过原左右次序将组成一个新的正整数。编程对给定的n 和s，寻找一种方案，使得剩下的数字组成的新数小。输入:n s 输出:最后剩下的最小数【样例输入】 178543 S=4 【样例输出】 13 【问题分析】由于正整数n的有效位数最大可达240位，所以可以采用字符串类型来存储n。那么，应如何来确定该删除哪s位呢,是不是只要删掉最大的s个数字就可以了呢,为了尽可能地逼近目标，我们选取的贪心策略为:每一步总是选择一个使剩下的数最小的数字删去，即按高位到低位的顺序搜索，若各位数字递增，则删除最后一个数字，否则删除第一个递减区间的首字符。然后回到串首，按上述规则再删除下一个数字。重复以上过程s次，剩下的数字串便是问题的解了。例如:对n=178543，s=4，删数的过程如下: n=178543 {删掉8} n=17543 {删掉7} n=1543 {删掉5} n=143 {删掉4} n=13 {解为13} 这样，删数问题就与如何寻找递减区间首字符这样一个简单的问题对应起来了。要注意一个细节问题: 可能会出现字符串首部有若干个0(甚至整个字符串都是0)的情况。按以上贪__心策略编制的程序框架如下: 输入s, n; while s > 0 do begin i:=1; {从串首开始找} while (i < length(n)) and (n[i]1) and (n[1]=‘0’) do delete(n,1,1); {删去串首可能产生的无用零}

                    本文档为【贪心算法实例】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

贪心算法实例

你可能还喜欢