努力是为了不平庸算法学习有些时候是枯燥的,这一次,让我们先人一步,趣学算法!
- [系列博客:](https://cloud.tencent.com/developer)
- [算法知识点](https://cloud.tencent.com/developer)
- [算法题目来源](https://cloud.tencent.com/developer)
- [算法题目描述](https://cloud.tencent.com/developer)
- [做题思路](https://cloud.tencent.com/developer)
- [模板代码](https://cloud.tencent.com/developer)
- [做题过程中遇到的bug及解决方案](https://cloud.tencent.com/developer)
- [有没有优化空间呢](https://cloud.tencent.com/developer)
本文是系列博客的第4篇,是听了陈老师的报告后的记录,主要包括如何学习算法。
贪心算法 一个贪心算法总是做出当前最好的选择,也就是说,它期望通过局部最优选择得到全局最优的解决方案。 对于贪心算法,需要注意以下几个问题:
什么时候选择贪心算法: 满足贪心选择和最优子结构的问题
《趣味算法第2版》
海盗们截获一艘装满各种各样古董的货船,每一件古董都价值连城,但一旦打碎就会失去其原有的价值。海盗船虽然足够大,但载重量是有限的。海盗船的载重量为W ,每件古董的重量为w_{i} ,如何才能把尽可能多的古董装上海盗船呢?
问题邀请装载的古董尽可能的多,在载重量有限的情况下,优先把重量下的古董装进去,装的最多,可以采用重量最小者优先装的贪心策略,从局部最优达到全局最优,得到最优装载问题的最优解。 采用重量最小最先装,然后每次从余下的古董中选择一个重量最小的古董。
因此如果序列不变的情况下,先排序再选取更好
最终方案
# 假设最大载重为 30
W = 30
# 重量分布为
w = [4,10,7,11,3,5,14,2]
# 排序
w_new = sorted(w)
print(w_new)
print("*"*10)
w_tmp = 0
w_in = []
for i in w_new:
if (w_tmp < 30) and (w_tmp + i <30) :
w_tmp = w_tmp + i
w_in.append(i)
else:
w_tmp = w_tmp
print(w_in)
print("*"*10)
print(w_tmp)
输出为:
D:\ProgramData\Anaconda3\envs\py10\python.exe D:/pythonproject/chapter11/csdn博客/chapter02贪心算法.py
[2, 3, 4, 5, 7, 10, 11, 14]
**********
[2, 3, 4, 5, 7]
**********
21
这个办法是最优的吗?其实对于本题是最优的,因为要求是获得最多的古董,那么一定是从小到大的古董最多,本体剩余9的载重量没有填满,也无法再填充更大的古董了。
针对这道题来说,排序部分可以优化下,采用Timsort排序可能会更好些 如果是背包问题,由于考虑最大价值,最小重量等多个问题,我们会提出对应的优化办法