贪心算法经典例题

文章描述:-2022年2月18日发(作者:万根云主机)-- 贪心算法经典例题 所谓贪心算法指的是为了解决在不回溯的前提之下,出整体最优或者接近最优解的这样一种类型的问题而设计出来的算法。贪心算法的基本思想是出整体当中每个小的局部的最优解,并且将所有的这些局部最优解合起来形成整体上的一个最优解。因此能够使用贪心算法的问题必须满足下面的两个性质:1.整体的最优解可以通过局部的最优解来求出;2.一个整体能

-

贪心算法经典例题 2022年2月18日发(作者:万根云主机)


--
贪心算法经典例题

所谓贪心算法指的是为了解决在不回溯的前提之下,出整体最
优或者接近最优解的这样一种类型的问题而设计出来的算法。贪心算
法的基本思想是出整体当中每个小的局部的最优解,并且将所有的
这些局部最优解合起来形成整体上的一个最优解。因此能够使用贪心
算法的问题必须满足下面的两个性质:1.整体的最优解可以通过局部
的最优解来求出;2.一个整体能够被分为多个局部,并且这些局部都
能够求出最优解。使用贪心算法当中的两个典型问题是活动安排问题
和背包问题。

利用贪心算法解题,需要解决两个问题:
一是问题是否适合用贪心法求解。我们看一个币的例子,如果一
个货币系统有3种币值,面值分别为一角、五分和一分,求最小币
数时,可以用贪心法求解;如果将这三种币值改为一角一分、五分和
一分,就不能使用贪心法求解。用贪心法解题很方便,但它的适用范
围很小,判断一个问题是否适合用贪心法求解,目前还没有一个通用的
方法,在信息学竞赛中,需要凭个人的经验来判断何时该使用贪心算
法。
二是确定了可以用贪心算法之后,如何选择一个贪心标准,才能保
证得到问题的最优解。在选择贪心标准时,我们要对所选的贪心标准
进行验证才能使用,不要被表面上看似正确的贪心标准所迷惑,如下
面的例子。

--


--

例2 (NOIP1998tg)设有n个正整数,将他们连接成一排,组成
一个最大的多位整数。例如:n=3时,3个整数13,312,343,连成的
最大整数为:34331213
又如:n=4时,4个整数7,13,4,246连接成的最大整数为7424
613
输入:N
N个数
输出:连接成的多位数

算法分析:此题很容易想到使用贪心法,在考试时有很多同学把整
数按从大到小的顺序连接起来,测试题目的例子也都符合,但最后测
试的结果却不全对。按这种贪心标准,我们很容易到反例:12,1
21 应该组成12121而非12112,那么是不是相互包含的时候就从
小到大呢?也不一定,如:12,123 就是12312而非12112,
这样情况就有很多种了。是不是此题不能用贪心法呢?
其实此题是可以用贪心法来求解,只是刚才的贪心标准不对,正
确的贪心标准是:先把整数化成字符串,然后再比较a+b和b+a,
如果a+b>b+a,就把a排在b的前面,反之则把a排在b的后面。
源程序:
var
s:array[1..20] of string;
t:string;i,j,k,n:longint;
--


--
begin
readln(n);
for i:=1 to n do begin
read(k);
str(k,s[i]);
end;
for i:=1 to n-1 do
for j:=i+1 to n do
if s[i]+s[j] begin{交换}
t:=s[i];
s[i]:=s[j];
s[j]:=t;
end;
for i:=1 to n do write(s[i]);
end.

贪心算法所作的选择可以依赖于以往所作过的选择,但决不依赖
于将来的选择,也不依赖于子问题的解,因此贪心算法与其它算法相
比具有一定的速度优势。如果一个问题可以同时用几种方法解决,贪
心算法应该是最好的选择之一。


--

-

贪心算法经典例题

发布时间:2022-02-18 23:17:42
文章版权声明:除非注明,否则均为IT技术网-学习WEB前端开发等IT技术的网络平台原创文章,转载或复制请以超链接形式并注明出处。

发表评论

评论列表 (有 11 条评论,43人围观)

最近发表

随便看看

热门文章

标签列表