text: 贪心算法和动态规划的差异
  动态规划类似于穷举法，只是记录了之前的结果，不需要进行重复的计算，可以利用前边的结果（状态方程），一般复杂度比贪心高，但是可以得到全局最优解。
  贪心算法每次只考虑当前，不保证能得到全局最优，只保证当前最优，应用前一般需要证明，一般复杂度比较低。
  贪心：每一步的最优解一定包含上一步的最优解，上一步之前的最优解则不作保留；
  举例说明：也就是说，假如你要求第十步的最优解，那么第十步的最优解肯定与第九步的最优解有关，而第九步的最优解肯定与第八步的最优解有关。算法 动态规划和贪心算法都满足最优子结构性质。假设：原问题的最优解不包括子问题的最优解
  可知，原问题的解 w
  所以假设错误，原命题正确
  动态规划—重叠子问题
  贪心算法—贪心选择性质
  是一种局部最优解组合替代整体最优解的方案。
  但有些时候计算得到的最终解并非整体最优解。
  贪心算法采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择，就将所求问题简化为一个规模更小的子问题；
  通过每一步贪心选择，可得到问题的一个最优解，虽然每一步上都保证能获得局部最优解，但由此产生的全局解不一定是最优的；
  因此适合用贪心算法解决问题的前提是：局部最优策略能导致产生全局最优解 ；
  一般，对一个问题分析是否适用于贪心算法，可以先选择该问题下的几个实际数据进行分析，就可做出判断；
  2 动态规划 动态规划（Dynamic Programming，DP）是求解决策过程最优化的过程，能获得全局最优解；动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解；
  与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的，若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次（比如斐波拉契数列）；另外，分治自顶向下，动态规划自底向上；
  如果把所有的子问题看成一棵树的话，动态规划自底向上，从叶子向根；构造子问题的解，对每一个子树的根，求出下面每一个叶子的值，推得根的值，最后得到一棵完整的树，根的值即为最优值；
  需要在给定约束条件下优化某种指标时，动态规划很有用；
  每种动态规划解决方案都涉及网格，单元格中的值通常就是要优化的值；
  每个单元格都是一个子问题，因此需要考虑如何将问题分解为子问题；
  没有放之四海皆准的计算动态规划解决方案的公式；
  首先，它没有统一的处理方法，必须根据问题的各种性质并结合一定的技巧来处理；
  因而，受计算机的存贮量及计算速度的限制，当今的计算机仍不能用动态规划方法来解决较大规模的问题，这就是“维数障碍”；
  3 两者区别 1 贪心自顶向下求解，动态规划自底向上求解；贪心：如果把所有的子问题看成一棵树的话，贪心自顶向下，每次向下遍历最优子树即可（通常这个“最优”都是基于当前情况下显而易见的“最优”），这样的话，就不需要知道一个节点的所有子树情况，于是构不成一棵完整的树；
  动态规划：如果把所有的子问题看成一棵树的话，动态规划自底向上，从叶子向根；构造子问题的解，对每一个子树的根，求出下面每一个叶子的值，推得根的值，最后得到一棵完整的树，根的值即为最优值；
  2 贪心最优解一定包含上一步的最优解，动态规划最优解不一定包含上一步的最优解；
  贪心：每一步的最优解一定包含上一步的最优解，上一步之前的最优解不作保留；
  动态规划：全局最优解不一定包含上一步的最优解，因此需要记录上一步的所有解；
  3 贪心不能保证全局最优，动态规划（本质是穷举法）能保证全局最优；
  4 贪心复杂度较低，动态规划复杂度较高；
  利用 贪心算法 求解最优问题的步骤： （1）选定合适的贪心选择的标准； （2）证明在此标准下该
  第16章 贪心算法 第16章 贪心算法 理解 贪心算法的概念理解 贪心算法的概念掌握 贪心算法的基本要素理解 贪心算法 与 动态规划算法的差异 通过范例学习 贪心算法 设计策略算法导
  // 动态规划和贪心法求解tsp问题 #include<cstdlib>#include<iostream>#includ...数据结构分治法
  算法与程序设计：第4章贪心算法 .ppt
  尽管Prim 算法 每次做的算法 涉及的权重边不一定会涵盖连通图中的所有边，但是随着所使用的排序 算法的效率的提高，Kruskal 算法和 Prim 算法 之间的差异 将会清晰的显性出来。