算法设计与分析(二)之动态规划
贪心算法的特点
设计要素：
贪心法适用于组合优化问题。
求解过程是多不判断过程，最终的判断序列对应于问题的最优解。
依据某种“短视的”贪心选择性质判断，性质好坏决定算法的成败。
贪心法必须进行正确性证明。
证明贪心法不正确的技巧：举反例。
贪心法的优势
：算法简单，时间和空间复杂性低
最优装载问题
问题：
n个集装箱1,2,3,…..,n装上轮船，集装箱i的重量wi，轮船装载重量限制为C，无体积限制。问如何装是的上船的集装箱最多？不妨设每个箱子的重量Wi =C.
该问题是0-1背包问题的子问题，集装箱相当于物品，物品重量是Wi，价值Vi都等于1，轮船载重限制C相当于背包重量限制b。
建模：
设 x1,x2,x3,x4….,xn 表示解向量，Xi=0,1，Xi=0当且仅当第i个集装箱装上船
算法设计
贪心策略：轻者优先
算法设计：
将集装箱排序，使得
W1 =W2 =… =Wn
按照标号从小到大装箱，直到装入下一个箱子将使得集装箱 总重超过轮船装载重量限制，则停止。
正确性证明思路
命题：对装载问题任何规模为n的输入实例，算法得到最优解。
设集装箱从轻到中记为1,2,3…,n
归纳基础：证明对任何只含1个箱子的输入实例，贪心法得到最优解。显然正确
归纳步骤： 证明：假设对于任何n个箱子的输入实例贪心法都能得到最优解，那么对任何n+1个箱子的输入实例贪心法也得到最优解。
小结
装载问题是0-1背包问题的子问题（每件物品重量为1），NP难的问题存在多项式时间可解的子问题
得不到最优解的问题的处理方法
找零钱问题
最小生成树
Prim算法
Kruskal算法
单源最短路径问题及算法
Dijkstra算法
贪心法小结
贪心法适用于组合优化问题
求解过程是多步判断过程，最终的判断序列对应于问题的最优解
判断依据某种“短视的”贪心选择性质，性质的好坏决定了算法的正确性。贪心性质的选择往往依赖于直觉或经验。
贪心法正确性证明方法：
1).直接结算优化函数，贪心法的解恰好取得最优值
2).数学归纳法（对算法步数或者问题规模归纳）
3). 交换论证
证明贪心策略不对：举反例
对于某些不能保证对所有的实例都得到最优解的贪心算法（近似算法），可做参数化分析或者误差分析
贪心法的优势：算法简单，时间和空间复杂性低
几个著名的贪心算法
最小生成树的Prim算法
最小生成树的Kruskal算法
单源最短路的Dijkstra算法
大数据学习交流QQ群：374038693
更多关于hadoop，spark和机器学习，数据结构与算法文章请关注本文：
