贪心算法证明框架
1、证明初始贪心选择不影响全局最优解，也就是要满足上凸
2、证明初始贪心后产生的子问题达到最优时，原问题也最优。

哈夫曼树（一种完全二叉树）：构造过程都可看成不断合并节点的过程

哈夫曼树的初始选择:
为了不失一般性，我们选择x1, x2两个互为兄弟结点的两点，并且位于最下层，将这两个点合并，假设存在最优方案在初始贪心选择X3、X4, 并且x1 + x2 <= x3 + x4,因为是对任意的完全二叉树，所以很难比较带权路径长度。因此我们认为
我们的贪心选择方案只是再第一步和假设的最优方案不同，即他选择x3 + x4,而我选择x1 + x2,剩余的操作我们都和
假设的最优方案一样。因此可以得到 WPL初始贪心选择-WPL理想 = （x1 + x2） - (x3 + x4) <= 0,因此可以看出我们
的初始贪心选择得到的二叉树是比假设的最优方案得到的权值总和还小。因此假设不成立。我们的初始贪心选择的第一步是
最优的选择。
接下来WPL原问题= WPL子问题 + x1 + x2,如果子问题最优，那么原问题就最优，即子问题是充分的条件。
通过递归的构造可以发现子问题也可以看作哈夫曼树，所以也可以用初始贪心选择。这样可以知道子问题是最优，
所以原问题最优。

贪心反例：01背包选择，如果我们一开始就选择价值最大的物品放入背包，那么最终结果肯定会被影响。因此不能够用
贪心来处理01背包