学习前福利-猪头肉我给交了

文集列表：
自我修养--瞎写的故事
python--入门到放弃
杂七杂八--啥都有
操作系统--不要低估一颗底层的心
机器学习--入门槛超高
算法--笑而不语

---

正文

大部分算法基于以下四种思想：
1.动态规划
2.分而治之（递归思想）
3.贪心算法
4.暴力穷举

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。假设一个问题比较复杂，暂时找不到全局最优解，那么我们可以考虑把原问题拆成几个小问题（分而治之思想），分别求每个小问题的最优解，再把这些“局部最优解”叠起来，就“当作”整个问题的最优解了。
贪心选择是采用从顶向下、以迭代的方法做出相继选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问题。求最小生成树和Prim算法和Kruskal算法都是漂亮的贪心算法。

#实例1 找零钱问题：
#要求找零张数最少，输入价格，输出面额。
class Solution:
    def zhaoling(self, nums):
        money = [50, 20, 10, 5, 1]
        result = 100 - nums
        for i in money:
            if result >= i:
                count = result // i
                result = result - count * i
                print("{}元的{}张".format(i,count))
        else:
            print("找零完毕")
s = Solution()
print(s.zhaoling(52))

#实例2 分糖果问题：
#要求每人至少一个，评分比相邻高的糖果要多，
#输入评分列表，输出至少需要的糖果数
class Solution:
    def fentang(self, grade):
        result = [1]
        for index in range(1, len(grade)):
            if grade[index] > grade[index - 1]:
                result.append(result[index - 1] + 1)
            elif grade[index] < grade[index - 1]:
                result.append(result[index - 1] - 1)
            else:
                result.append(result[index - 1])
        judge = min(result)
        if judge <= 0:
            for index in range(0, len(result)):
                result[index] = result[index] + 1 - judge
        return result

s = Solution()
print(s.fentang([1, 2, 1]))
print(s.fentang([2, 1, 2]))
print(s.fentang([6,8,10,4,4,3,2,1]))