转载 C语言贪心算法 c语言贪心算法

贪心算法

开放分类：算法、信息学

贪心算法

例题：畜棚修理（1999年USACO春季公开赛试题）

有一长列畜棚，其中一些被木板覆着。你可以使用总共N个木板，这些木板可以覆盖任意连续的畜棚。覆盖所有必要的畜棚，使得所用的木板尽可能的少。

贪心算法很快，一般的为O(n)到O(n^2)而且需要很少的额外空间。不幸地是，它一般是不正确的。但是，当它正确，它就会远快于其它算法。

算法

在贪心算法背后所隐含的基本算法，是从小规模问题中生成大规模问题。这不像其他算法，在贪心算法的进行过程中，它只关心它发现的最好的策略。因此，对于例题，为了生成N=5时的策略，它先寻找N=4时的最优策略，然后以此生成。此时，对于其它N=4时的策略，不予考虑。

问题
贪心时，有两个基础的问题需要考虑。

怎么生成？

怎样从小规模策略中生成大规模策略？一般地，有这样一个运作过程。对于例题，由四块木板生成五块木板的最显然的方法，就是将其中一块木板中的一部分拿掉，这样一块木板变成了两块。而你要做的，是在那些不需要被木板覆盖的畜棚区域中，选出最长的片段（这样，就使得所用的木板最少了）。

拿掉被覆盖畜棚的木板中的一个片段，使得它变成两段。一段在该片段之前，一段在该片段之后。

它有效吗？

对于程序员，真正的挑战是谈心算法不总有效。即便它可能对于一些简单的数据、随意的数据，以及所有你能考虑到的情况有效，但只要有一种情况不奏效，至少一个（假设没有更多），评测系统就会由此停下。

对于例题，看看上述的谈心算法的工作工程，要考虑如下几点：

假设，答案中不包括贪心算法所拿掉的较大缺口，而是较小的。那么通过结合较小缺口，使其与两边的木板相连。答案是通过用一定量的木板覆盖尽量少的畜棚。新的答案更好些，所以假设是错误的，我们总是去掉最大缺口是正确的。

如果答案不包含特殊的缺口，但是包含一个与之同样大的缺口，做相同的转换，发现所需的木板量并没有变化，这个新的答案与原来的答案是一样的。我们可以选取任意一个。

因此，所产生的结果是最优的，它包含的是最大的切除片段。每一步都是这样，最终也一定是这样。

结论

如果一个贪心算法存在，那就用它。它们的编写、编译、运行都很快，唯一令人遗憾地，它地正确性。如果贪心算法可以得到正确的答案，那就努力地寻找这个算法。但是，不要指望贪心算法能解决所有问题

贪心算法的3个相当经典的程序

1.线段覆盖（linescover）

题目大意：在一维空间中告诉你N条线段的起始坐标与终止坐标，要求求出这些线段一共占了多大的长度。

解题思路：将线段按其实坐标进行排序,使之依次递增。然后定义一个变量last记录考虑到当前线段之时被线段覆盖的最大的坐标值。因为已经排过序所以当前线段的效应长度为(x为起始坐标，y为终止坐标)：

length:=0(y<=last)

y-last(x<=last &y>last)

y-x(x>last &y>last)

并且注意同时更新last的值。最后统计每条线段的效应长度就为我们所需要的答案。

2.最优数对（bestpair）

题目大意：按递增的顺序告诉你N个正整数和一个实数P，要求求出求出该数列中的比例最接近P的两个数（保证绝对没有两个数使得其比值为P）。

解题思路：定义两个指针i和j，然后进行如下操作：当code[j]/code[i]>p时inc（j），当code[j]/code[i]<p时inc（i），然后记录其中产生的最优值即可。

3.连续数之和最大值（maxsum）

题目大意：给你N个数，要求求出其中的连续数之和的最大值。（也可以加入a和b来限制连续数的长度不小于a且不大于b）。

解题思路：定义一个统计变量tot，然后用循环进行如下操作：inc（tot，item）其中如果出现tot<0的情况，则将tot赋值为0。在循环过程之中tot出现的最大值即为答案。如果加入了限制条件的话，问题就变得难一些了（这句真的不是废话）。为此我们需要定义：数组sum[i]来表示code[1]到code[i]之和（这样的话code[a]~code[b]的和我们就可以用sum[b]-sum[a-1]来表示了。），数组hash[i]来表示满足条件的sum[a-1]所对应的下标（并使之按sum[i]的递增顺序排列，一定要处理好sum[i]进出hash的过程）。这样的话对于终止坐标为i的连续数列其最大和必定为sum[i]-sum[hash[1]],求出其最大值即可。

爱华网本文地址 » http://www.413yy.cn/a/25101010/35182.html