今日复习内容:重新学习一下贪心算法
今天做题的时候,想了半天贪心算法,结果没全想出来,所以菜就多练,重新学一下呗。
贪心算法是一种常见的算法范式,通常用于求解最优化过程。在每一步的选择中,贪心算法总是做出当前看起来最优的选择,而不考虑当前选择之后的结果。贪心算法的核心思想是通过局部最优解来寻求全局最优解。
贪心算法具有以下特点:
(1)局部最优性:每一步选择都是局部最优的,即当前情况下的最优选择。
(2)不可回退行:一旦做出了选择,就不会再改变,这意味着贪心算法做出的选择是永久性的,不会考虑后续的情况。
(3)简单高效:贪心算法通常实现简单,执行效率高,适用于解决某些特定类型的问题。
贪心算法通常适用于满足以下条件的问题:
(1)问题可以通过局部最优解达到全局最优解;
(2)问题的求解过程可以划分为一系列步骤,每一步选择都是局部最优的,且当前选择不影响后续步骤的选择;
(3)问题的求解过程不需要回退或者回溯,即一旦做出选择就无需再修改。
实例:
(1)找零问题:给定一定面额的货币,如何用最少的数量的货币来完成找零?贪心算法可以从面额最大的货币开始,逐步选取,直到找零完成。
(2)背包问题:给定一个背包和一组物品,每个物品有自己的价值和重量,如何在背包容量限制下装入尽可能多的价值?如果物品可以分割,可以使用贪心算法按照单位重量的价值从大到小选择物品装入背包。
(3)活动选择问题:给定一系列活动,每个活动都有开始时间和结束时间,同时只能进行一个活动,如何安排活动使得参加的活动数量最多?贪心算法可以按照结束时间从早到晚排序,然后依次选择结束时间最早且与之前活动不冲突的活动。
值得注意的是,贪心算法虽然较简单,但并不是所有问题都适合用贪心算法求解。在某些情况下,贪心算法可能无法得到最优解,或者需要证明才能确保其正确性。因此,在应用贪心算法时,需要谨慎选择问题和验证算法的有效性。
我找了好多题,我觉得多做几个题,应该就OK了。
例题1:答疑
有n位同学同时找老师答疑。每位同学都预先估计了自己答疑的时间。
老师可以安排答疑的顺序,同学们要依次进入老师办公室答疑,一位同学答疑的过程如下:
1.首先进入办公室,编号位i的同学需要si毫秒的时间。
2.然后同学问问题老师解答,编号位i的同学有ai毫秒的时间。
3.答疑完成后,同学很高兴,会在课程群里面发一条消息,需要的时间可以忽略。
4.最后同学收拾东西离开办公室,需要ei毫秒的时间,一般需要10秒,20秒或30秒,即ei取值为10000,20000或30000。
一位同学离开办公室后,紧接着下一位同学就可以进办公室了。
答疑从0时刻开始,老师想合理的安排答疑的顺序,使得同学们在课程群里面发消息的时刻之和最小。
输入描述:
输入第一行包含一个整数n,表示同学的数量;
接下来n行,描述每位同学的时间,其中第i行包含三个整数si,ai,ei,意义如上所述。
其中,1 <= n <= 1000,1 <= si <= 60000,1 <= ai <= 10^6,ei 一定为10000,20000,30000之一。
输出描述:
输出一个整数,表示同学们在课程群里面发消息的时刻之和最小是多少?
分析:我写出前三个同学的情况
第一个同学:sum1(time) = s1 + a1 + e1
第二个同学:sum2(time) = s2 + a2 + s1 + a1 + e1
第三个同学:sum3(time) = s3 + a3 + s2 + a2 + e2 + s1 + a1 + e1
我们要求的是s1 + a1 + e1 ,s2 + a2 + e2,s3 + a3 + e3谁最小
参考答案:
n = int(input())
ls = []
for i in range(n):ls.append(list(map(int, input().split())))
count = 0
t = 0
ls.sort(key=lambda x: sum(x))for i in range(n):t += sum(ls[i])count += t - ls[i][-1]print(count)
运行结果:
例题2:重复字符串
题目描述:
如果一个字符串s恰好可以由某个字符串重复k次得到,我们就称s是k次重复字符串。例如abcabcabc可以看作abc重复3次得到,所以abcabcabc是3次重复字符串。
同理,aaaaaa既是2次重复字符串,又是3次重复字符串和6次重复字符串。
现在给定一个字符串s,请你判断至少要修改其中几个字符串,可以使s变成一个k次字符串?
输入描述:
输入第一行包含一个整数k;
第二行包含一个只含小写字母的字符串s。
其中,1 <= k <= 10^5,1<= |s| <= 10^5,其中|s|表示s的长度。
输出描述:
输出一个整数代表答案,如果s无法修改成k次字符串,就输出-1。
参考答案:
k = int(input())
s = input()
l = len(s) // k
num = 0
for i in range(l):ls = s[i:len(s):l]lis = {}for i in ls:lis[i] = lis.get(i,0) + 1lis = sorted(lis.items(),key = lambda x:x[1])for i,j in lis[:-1]:num += j
print(num)
OK,我做不下去了,这篇就这样吧,下一篇继续!