第4章 贪心算法1学习要点理解贪心算法的概念。掌握贪心算法的基本要素（1）最优子结构性质（2）贪心选择性质理解贪心算法与动态规划算法的差异理解贪心算法的一般理论通过应用范例学习贪心设计策略。（1）活动安排问题；（2）最优装载问题；（3）哈夫曼编码；（4）单源最短路径；（5）最小生成树；（6）多机调度问题。23一、贪心算法定义 指的是从对问题的某一初始解出发,一步一步的攀登给定的目标,尽可能快地去逼近更好的解。当达到某一步,不能再攀登时,算法便终止。二、贪心算法特点 贪心算法总是做出在当前看来是最好的选择,它并不是从总体最优上加以考虑,他所作出的选择只是在某种意义上的局部最优选择。能够得到的解不一定是最优解。概述举例：假设有四种硬币25分、10分、5分、1分若干个。要凑够63分，应该怎样取硬币使得硬币个数最少？描述问题：数组a4存放所取四种硬币 的个数,w4存放四种硬币币值约束条件可行解目标函数4如果把硬币换为：一分、五分、一角一分，而找给顾客如果把硬币换为：一分、五分、一角一分，而找给顾客的是一角五分的是一角五分5背包问题背包问题:共有共有n种物品要装入一个背包中，背包种物品要装入一个
