贪心.ppt

贪心算法
所谓贪心算法是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优解。
贪心算法不是对所有问题都能得到整体最优解,但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。
贪心算法的基本思路如下:
。
。
,得到子问题的局部最优解。
。
实现该算法的过程:
从问题的某一初始解出发;
while 能朝给定总目标前进一步 do
求出可行解的一个解元素;
由所有解元素组合成问题的一个可行解;
问题1、最大子段和(SEQ)
【问题描述】
老师给笑笑布置了一份的作业,笑笑不知如何解决,找你帮忙解决。
老师给了一串很长的数列,要求从中找出连续的一段来使得总和最大。
【输入文件】
文件名:
文件中第一行包括一个整数N,表示数列长度为N(N <= 100000)。
第二行包括N个整数来描述这个数列,每个整数的绝对值不超过1000。
【输出文件】
文件名:
文件中只有一个整数,为最大的连续段总和。
【样例输入】
5
1 -2 3 1 -4
【样例输出】
4
问题分析:
求“最大连续段和”是一个比较基础的问题,可以用多种方法解决,下面讨论三种算法,请大家通过具体的数据测试实现三种算法的程序效率,学习逐步求精的算法分析方法。
算法1:
枚举:用三重循环枚举子段起点位置、终点位置、求子段和,比较子段和求最大值。算法时间效率O(n3)。
算法2:
算法1中,在求子段和过程中有许多重复的操作,如:求第3个数到第5个数的和包含在求第2个数到第5个数和之中,显然,重复进行了求和操作。如何解决呢?
解决方法是通过预处理,求出从第1位置到每个位置的和b[i],而b[i]值等于b[i-1]值加当前位置值,减少了重复求和运算,对于子段[I,j]的子段和S,则有s=b[j]-b[i]。
这样,用两重循环枚举子段起点位置i与终点位置j,求得所有子段和,比较子段和求最大值。算法时间效率O(n2)。
算法3:
设B[j]为以第j个位置为结尾的最大子段和,若B[j-1]大于0,显然,B[j]=B[J-1]+当前数,因为,与和大于0连续序列构成的序列和一定比本身数构成的序列和大,如果B[j-1]小于0,则B[j]=当前数,因为,当前数大于当前数加上一个负数。
这里应用了一个贪心思想,当前数+正数>当前数,当前数+负数<当前数。通过求从第1个到第n个数以本身数为结尾的最大子段和,即枚举了所有数最大子段和。
由于问题只求最大子段和,在求解过程能够求得以当前数为结尾的最大子段和,然后比较记下其中的最大值即可。
设连续子段和为t,则:
t+a[i] t>=0
t=
a[i] t<0
算法描述:
读入序列中的n个数存放在a数组中;
初值设置,第1个数的子段和t=a[1],最大子段和ans=a[1];
一重循环枚举第2个数到第n个数,执行下列操作:
求以当前数为结尾的最大子段和t;
如果t>ans,刷新ans值;
输出ans值。
算法时间效率为O(n) 。
readln(n);
for i:=1 to n do
read(a[i]);
t:=a[1]; ans:=a[1]; //t当前数结尾的最大子段和,ans 最大子段和
for i:=2 to n do
begin
if t<0 then t:=a[i] //求当前数结尾的最大子段和
else t:=t+a[i];
if t>ans then ans:=t; //求最大子段和
end;
问题2、集合删数
问题描述:
一个集合有如下元素:1是集合元素;若P是集合的元素,则2 * P +1,4*P+5也是集合的元素,取出此集合中最小的K个元素,按从小到大的顺序组合成一个多位数,现要求从中删除M个数位上的数字,使得剩下的数字最大,编程输出删除前和删除后的多位数字。
注:不存在所有数被删除的情况`
输入格式:
输入的仅一行,K,M的值,K,M均小于等于30000。
输出格式:
输出为两行,第一行为删除前的数字,第二行为删除后的数字。
样例输入:
5 4
样例输出:
137915
95
问题简述
问题由两个子问题组成:
1、构造一个多位数:1是集合元素;若P是集合的元素,则2 * P +1,4*P+5也是集合的元素,取出此集合中最小的K个元素,按从小到大的顺序组合成一个多位数
2、从多位数中删除M个数位上的数字,使得剩下的数字最大
1、分析集合元素特点:
若P是集合的元素,则2 * P +1,4