背包装豆子问题

  假设有一个可以容纳100Kg物品的背包,可以装各种物品,我们有以下五种豆子,每种豆子的总量和总价值都不同.为了让背包中装总价值最大的物品,我们需要如何选择放入背包中的豆子呢?每种豆子应该装多少？

  这个问题的思路是：算出每种豆子的单价，即单位重量的价值。将单价最大的先放入背包中，就好比放入同样重量时金子和铁块，当然选择金子了。可以算出来由单价从高到低放入的是：20Kg给都、30Kg绿豆、50Kg的红豆，这样就把100Kg的背包给装满了，并且实现了总价值最大化。

贪心算法解决问题步骤：
① 当我们看到如下问题时应当首先联想到贪心算法
针对一组数据，我们定义了限制值和期望值，限制值就比如说上边的100kg的背包容量，期望值是限制值内背包价值的最大值。
② 尝试看下此类问题是否可以使用贪心算法解决
是否可以将问题转化为：在对限制值同等贡献的情况下，对期望值贡献最大的数据的求解。

③ 举例印证贪心算法产生结果的最优解
严格证明贪心算法的正确性是非常复杂的，需要涉及比较多的数学推理。而且从实践角度来说，只要是能用贪心算法解决的问题，贪心算法的正确性显而易见，无需严格的数学推导。

分糖果问题

  我们有m个糖果和n个孩子，要把糖果分给这些孩子吃。但糖果少，孩子多，糖多大小还不一样，孩子们对糖果大小的需求也不一样。M个糖果的大小分别是s1、s2、s3、s4….sm.孩子们对糖果大小的需求是g1、g2、g3………gn。
问题：如果分这些糖果，能够尽可能满足数量最多的孩子？
  其实这些问题从另一个角度看就是：从n个孩子中，抽取一部分孩子分糖果，能够满足最大数量的孩子（期望值）。如何分这m（限制值）个糖果呢？
  思路就是：对一个孩子来说，小糖果能满足，就别用大糖果，这样大糖果就可以留给其他对糖果大小需求更大的孩子。对糖果需求小的孩子容易被满足，那就优先满足需求小的孩子，因为对我们期望值的贡献是一样的。

钱币找零问题

  假设有1元、2元、5元、10元、20元、50元、100元这些面额的纸币，张数分别为c1、c2、c5、c10、c20、c50、c100。我们现在要用这些钱来支付固定的K元，最少几张纸币可以满足？
  思路是：在日常生活中，先用大额纸币支付，比如一张100即可，省事。不够10元内就用1元补齐。

霍夫曼编码问题

  假设有1000个字符的文件，每个字符占用1byte，一个byte就是8bits，存储着1000个字符就需要8000个bit，那么是否有节省内存的存储方式？
  假设这1000个字符中只有6种字符，分别是a、b、c、d、e、f。而3个bit就可以表示8个不同字符，所以6个字符更不在话下，那么我们可以让3个bit来表示每一个字符，所以1000个字符的文件只需要3000个bit，比原来节省了很多空间，是否有更加节省内存的存储方式呢？
  这就是霍夫曼的编码方式，霍夫曼编码第一会找出字符的种类，第二会找出每种字符出现的频率。根据每个字符出现频率不同，选择的每个字符编码长度不同。根据贪心算法思想，霍夫曼编码把出现频率小的字符使用长一点的编码；把出现频率高的字符使用短一点的编码。这样(频率*编码长度)求和的期望值就是最小的，也就是占用的空间最少。
  思想是简单，实际操作中，一个1000个字符的文件去编码了，你怎么解码，也就是说你怎么区分长短不同的编码？你想想，如果一个文件只有一种长度的编码，那直接就根据长度解码就行了，但是现在长度有好几种，你每次是读取1位还是2位还是3位呢？为了解决这个加压缩过程中的歧义问题，霍夫曼编码陶秋各个字符的编码之间，不会出现某个编码是另一个编码前缀的情况。
  假设这6个字符出现频率是从高到低a、b、c、d、e、f。我们把它们编码成下图这样子，任何一个字符的编码都不是另一个编码的前缀，在解压缩的时候，我们每次读取尽可能长的二进制字符串，所以解压缩时候就不会出现歧义，经过这种编码压缩后，这1000个字符只需要2100bits就够了。

  有一个问题，比如出现频率为20的这个字符f，你怎么就知道编码是00000，而e频率30怎么就是00001呢？其实这里有一个技巧。
  把每个字符看做一个节点，并且附带把频率放入优先级队列中。我们从队列中取出频率最小的两个节点A、B，然后新建一个节点C，把频率设置为两个节点的频率之和，并且把这个新节点C作为节点A、B的父节点。最后把C节点放入到优先级队列中。重复此过程，直到队列中没有数据。

  接着，给每条边加上一个权值，指向左子节点的边为0，指向右自己诶单的边标记为1，那么从根节点到叶子节点的路径就是叶子节点对应的霍夫曼编码。

贪心小结

① 贪心算法的应用场景有限，主要更多是指导设计基础算法。
② 贪心算法原理不需要刻意深究，多练习才能体会到感觉。
③ 贪心算法的最优解证明并不容易，很多时候只需要举例子验证即可。