趣味算法-04-跟着作者读《趣味算法（第2版）》-贪心算法
趣味算法-04-跟着作者读《趣味算法（第2版）》-贪心算法
用户2225445
发布于 2022-11-12 17:13:44
发布于 2022-11-12 17:13:44
努力是为了不平庸算法学习有些时候是枯燥的，这一次，让我们先人一步，趣学算法！
趣味算法-04-跟着作者读《趣味算法（第2版）》-贪心算法
- [系列博客：](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
做题过程中遇到的bug及解决方案
这个办法是最优的吗？其实对于本题是最优的，因为要求是获得最多的古董，那么一定是从小到大的古董最多，本体剩余9的载重量没有填满，也无法再填充更大的古董了。
有没有优化空间呢
针对这道题来说，排序部分可以优化下，采用Timsort排序可能会更好些 如果是背包问题，由于考虑最大价值，最小重量等多个问题，我们会提出对应的优化办法
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2022-10-24，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录