贪心算法简介

目录

一、什么是谈心算法

二、例题

 证明找零问题：

三、贪心算法的特点

一、什么是谈心算法

         其实是贪心策略，是解决问题的策略，局部最优->全局最优
 解释：
 1、将解决问题的过程分为若干步
 2、解决每一步的时候，都选择当前看起来最优的解法
 3、希望得到全局最优解

二、例题

 
 例一：找零问题
        用了50块钱买了4块钱的东西，只有20、10、5、1的面额的纸币，要求找的张数最少
 这里第一个考虑20块钱，当前最优情况是两张20，还剩6块；再考虑5块钱，当前最优解是一张；
 最后是一块钱，当前最优解是一张一块的，完成
 
 例二：最小路径和
        九宫格，从左上格子走到右下格子，只能向下或者向右走，每个格子路程为格子里的数
 往下走到底，然后只能往右走到头

 
 例三：背包问题
        体积为V，W代表价值，最大容量固定，每个物品有无限多个，怎样装价值背包最大
 （体积小的，价值也低

 只考虑体积的话，会只装体积小的物品，一直装到不能装；或者考虑价格，先装最贵的，
 再装其他装的下的且价值最高的；或者两者以及考虑，用价值/体积作为判断标准（单位体积）
 
 但实际以上找的方法除了例一都是错的
 核心就是贪，而且鼠目寸光，只希望当前拥有最优解

 证明找零问题：

 先证明一个性质——
 10元的分为三种情况大于2、等于2、小于2
 一定是小于2，因为其他的都可以用数量更少的20代替
 因此B <= 1
 同理可证的C <= 1，D <= 4
 
 贪心解法：【a, b, c, d】
 最优解法：【A, B, C, D】
 
 因为是贪心解法，所以a >= A，但又因为一旦A < a，那么这二十块钱就要有后面更小的面额去补
 不复合最优解，因此A = a；
 同理可证B = b，C = c
 自然而然，d = D
 证毕。

三、贪心算法的特点

 1、贪心策略的提出
        （1）贪心策略的提出是没有标准以及模版的（检验、要求、瞎蒙）
        （2）可能每一道题的策略都是不同的
 2、贪心策略的正确性
        因为有可能贪心策略是一个错误的方法
        正确的谈心策略是需要证明的，而证伪只要举反例就可以
        常用的证明方法：数学中见过的所有的证明方法
 3、学习方向
        （1）心理上：遇到不会的贪心题很正常，把心态放平
        （2）前期学习的时候，重点放在贪心的策略上，把这个策略当成经验吸收
        （3）如何去证明——题目解析、算法原理、写代码