算法知识点
贪心算法
一个贪心算法总是做出当前最好的选择，也就是说，它期望通过局部最优选择得到全局最优的解决方案。
对于贪心算法，需要注意以下几个问题：
- 一旦做出选择，就不可回溯
- 有可能得不到最优解
- 选择什么样的贪心策略直接决定算法的好坏
什么时候选择贪心算法：
满足贪心选择和最优子结构的问题
算法题目来源
《趣味算法第2版》
算法题目描述
海盗们截获一艘装满各种各样古董的货船,每一件古董都价值连城,但一旦打碎就会失去其原有的价值。海盗船虽然足够大,但载重量是有限的。海盗船的载重量为W WW,每件古董的重量为w i w_{i}w i
,如何才能把尽可能多的古董装上海盗船呢?
做题思路
问题邀请装载的古董尽可能的多，在载重量有限的情况下，优先把重量下的古董装进去，装的最多，可以采用重量最小者优先装的贪心策略，从局部最优达到全局最优，得到最优装载问题的最优解。
采用重量最小最先装，然后每次从余下的古董中选择一个重量最小的古董。
如果采用顺序查找，第1次选择，需要比较n nn次，第2次为n − 1 n-1n−1次，总共需要比较n ( n + 1 ) / 2 n(n+1)/2n(n+1)/2次, 时间复杂度为O ( n 2 ) O(n^{2})O(n 2 )
如果采用快速排序，再按顺序选择，则时间复杂度为O ( n log n ) O\left(n \log n\right)O(nlogn)。相比顺序查找更优。
因此如果序列不变的情况下，先排序再选取更好
最终方案
- 先排序
- 根据贪心策略选择装入的古董
模板代码
# 假设最大载重为 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排序可能会更好些
如果是背包问题，由于考虑最大价值，最小重量等多个问题，我们会提出对应的优化办法
