vlambda博客
学习文章列表

Part 1

纸币问题。比如，在2010年左右，你要买一台998元的手机，当柜台询问你是否有零钱，这时候问题就来了——应该用至少多少张的纸币才能刚好凑出998元？这是个非常经典的问题，那么贪心的策略又是什么呢？贪心策略，就是先使用最大面额的纸币去尽可能凑齐总金额，如果再多一张100元就超值了。那就用50元的，如果再多一张就超值，就用20元的，然后再用10元，以此类推，总要有一轮，刚好凑齐998元。以整体为目标，分解出多个逐步的最优部分，最终能得到问题整体的最优解。

Part 2

世界杯进入到了淘汰赛阶段。一个球队想要取得最好成绩，那么一定会采用这样的策略，就是努力打好当前的比赛，赢下对手，打赢了当前第一轮就相当于局部胜利，一直打赢到最后就是整体胜利，努力打好每场比赛的策略就是贪心策略。但这总是最优解吗？不。

Part 3

如果不是淘汰赛，而是小组赛。若球队在此之前已经踢了两场，并成功拿下胜利。那肯定可以出线了，最后一场如果再赢，就很有可能遇到上届冠军，如果打平或者打输了，球队就有可能避开上届的冠军，那么这个时候那个教练大概率情况下会选择把主力撤下来，然后让一个相对来说不是非常强的阵容上，让主力球员们得到充分休息，养精蓄锐，在下一场到了淘汰阶段时再来拼尽全力，这样的才算是最优解。既避开了难以攻破的球队，又保住了自家球队的出线机会。

SUMMARY

例题：如果有10个点，起点已经固定，

不断选出最近的目标点。以此类推

串起来所有的点（用数学软件MATLAB表示）

进行贪心策略所用的MATLAB代码