贪心算法简单实践 -- 分糖果、钱币找零、最多区间覆盖、哈夫曼编解码

1. 贪心算法概览

贪心算法是一种算法思想。希望能够满足限制的情况下将期望值最大化。比如：Huffman编码，Dijkstra单源最短路径问题，Kruskal最小生成树 等问题都希望满足限制的情况下用最少的代价找到解决问题的办法。

这个办法就是贪心算法的思想。
实际用贪心算法解决问题可以有如下几步：

1. 当看到这类问题时 我们能够联想到贪心算法：针对一组数据，我们定义了期望值和限制值，希望在满足限制值的情况下期望值最大。
   比如最短路径中，限制值是每一次移动只能向下或向右，期望值是走到终点（某个顶点），期望用最少的步数走到目标顶点。
2. 尝试使用贪心算法来解决问题：每一次做出选择时在对限制值同等贡献量的情况下，选择对期望值贡献最大的数据。
3. 尝试在案例数据中举例，查看贪心方式的实验结果是否最优。

贪心算法适用的案例 是 每一次的选择都是独立事件，不会受到之前选择的影响。比如有权图中的最短路径的查找，当前的选择会对后续的选择造成影响，第一次选择最优的，后续可选的权值都是特别大的，则期望值并不是最优的。

可以看看如下几个简单实践。

2. 贪心算法实践

2.1 分糖果

我们有m个糖果和n个孩子。我们现在要把糖果分给这些孩子吃，但是糖果少，孩子多(m<n)，所以糖果只能分配给一部分孩子。

每个糖果的大小不等，这m个糖果的大小分别是s1，s2，s3，…，sm。除此之外，每个孩子对糖果大小的需求也是不一样的，只有糖果的大小大于等于孩子的对 糖果大小的需求的时候，孩子才得到满足。假设这n个孩子对糖果大小的需求分别是g1，g2，g3，…，gn。如何分配糖果，能尽可能满足最多数量的孩子?

期望值：最多满足孩子的个数
限制值：糖果大小s >= g ,才视为该糖果满足该孩子。
满足限制值的情况下，不论用小糖果还是大糖果满足孩子，对期望值的贡献都是一样的，满足的孩子个数++ 而已。

贪心算法：

• 对于一个孩子，用较小的糖果能够满足，则没有必要用更大的糖果；更大的糖果可以用来满足更多需求的孩子。
• 对于一个糖果，从较小需求的孩子开始，越容易满足。

代码如下：

// simple greedy algorithm: distribute candies
// six childs' request: 1 1 3 2 2 8
// five candies size:   4 2 5 7 9
//
// Greedy algorithm is suitable to solve the problem.
// We can let the smaller candy's size to satisfy the 
// smaller resquest of child.
int distributeCandy(vector<int> candies,
    vector<int> childs) {
  if(candies.size() == 0 || childs.size() == 0) {
    return 0;
  }

  // sort, we can compare from small to big request
  sort(candies.begin(), candies.end());
  sort(childs.begin(), childs.end());

  int res = 0;
  int i, j;
  
  for (i = 0, j = 0;i < childs.size() && 
      j < candies.size(); i++,j++) {
    if (childs[i] <= candies[j]) {
      res ++;
    }
  }

  return res;
}

完整测试代码:
​​​https://github.com/BaronStack/DATA_STRUCTURE/blob/master/greedy/distribute_candies.cc​​

2.2 钱币找零

这个问题在我们的日常生活中更加普遍。假设我们有1元、2元、5元、10元、20元、50元、100元这些面额的纸币，它们的张数分别是c1、c2、c5、c10、c20、c50、c100。我们现在要用这些钱来支付K元，最少要用多少张纸币呢?
在生活中，我们肯定是先用面值最大的来支付，如果不够，就继续用更小一点面值的，以此类推，最后剩下的用1元来补齐。

期望值：纸币数目最少
限制值：每种面额的张数

在满足限制值的情况下，希望用最少的纸币数目达成期望值。不论使用面额大的纸币还是面额小的纸币，期望值的纸币数目都会++，贡献一样。所以相同贡献值的情况下，使用更大面额的纸币更容易满足期望值。

代码如下：

int cmp(pair<int, int> a, pair<int, int> b) {
  return a.first > b.first;
}

// Get the total num of papers that satisfy the K
// param1: nums of every coin
// param2: target number
// param3: cost of every coin in coins
void getCoinNums(vector<pair<int,int>> coins,
                int K, vector<pair<int,int>> &result) {
  if (coins.size() == 0) {
    return;
  }

  int i, tmp;
  
  // sort from biger to smaller
  sort(coins.begin(), coins.end(), cmp);

  i = 0;
  tmp = 0;
  while(K && i < coins.size()) {
    tmp = K / coins[i].first;

    if (tmp != 0) {
      int real_nums;
      // defend the real coin nums overhead
      if (tmp <= coins[i].second) {
        real_nums = tmp;
      } else {
        real_nums = coins[i].second;
      }

      K -= real_nums * coins[i].first;

      result.push_back(make_pair(coins[i].first, real_nums));
    }
    i++;
  }
}

完整测试代码:
​​​https://github.com/BaronStack/DATA_STRUCTURE/blob/master/greedy/coins_charge.cc​​

2.3 最多覆盖区间

假设我们有n个区间，区间的起始端点和结束端点分别是[l1, r1]，[l2, r2]，[l3, r3]，…，[ln, rn]。我们从这n个区间中选出一部分区间，这部分区间满足两两不相 交(端点相交的情况不算相交)，最多能选出多少个区间呢?

比如区间： [6,8], [2,4], [3,5], [1,5], [5,9], [8,10]， 则最多不相交区间为 ： [2,4], [6,8], [8,10]

我们将各个区间的右端点从小到大排序，每次选择区间时只需要确认当前区间的左端点比上一个区间的右端点大就可以了。之所以选择对右端点进行从小到大的排序，因为右端点决定的是一个区间的下界，我们每次选择尽可能选择下界小且和之前的区间没有相交的区间，则才能够得到最多的不相交区间。

实现代码如下：

int cmp(pair<int, int> a, pair<int, int> b) {
  if (a.second < b.second) {
    return 1;
  } else if (a.second == b.second &&
             a.first < b.first) {
    return 1;
  } else {
    return 0;
  }
}

// algorithm:
// 1. Sort the array with right node increase
// 2. Maintain a num e, if rest of the interval's left node
// bigger than e, then the interval will be choosen
//
// example:
// Befor sort: [6,8], [2,4], [3,5], [1,5], [5,9], [8,10]
// After sort: [2,4], [1,5], [3,5], [6,8], [5,9], [8,10]
//
// result : [2,4], [6,8], [8,10]
void intervalCoverage(vector<pair<int,int>> intervals,
                      vector<pair<int,int>> &result) {
  if (intervals.size() == 0) {
    return;
  }

  int i, e, count;

  sort(intervals.begin(), intervals.end(), cmp);

  e = -1;
  count = 0;
  for (i = 0;i < intervals.size(); i++) {
    if(intervals[i].first >= e) {
      count ++;
      e = intervals[i].second;
      result.push_back(make_pair(intervals[i].first,
                                intervals[i].second));
    }
  }
}

完整测试代码：
​​​https://github.com/BaronStack/DATA_STRUCTURE/blob/master/greedy/interval_coverage.cc​​

2.4 哈夫曼编解码

哈夫曼编码是一种针对数据高效压缩的编码方式，能够达到20%-90%的压缩比。
比如：

• 1000长度的字符串 需要1000bytes = 8000 bit的存储空间。
• 优化：如果1000长度的字符串中总共有8个不同的字符，则这八个字符可以用三个bit位就能表示（000-111），1000长度的字符串只需要3000 bit的存储空间
• 进一步优化：haffman编码，每个字符的bit位表示可以不定长（解码会复杂一些），总长度不会超过3位（1000字符不会超过3000bit的存储空间）。haffman编码为了满足不定长的要求，不会出现针对某一个字符的编码是另一个字符编码前缀的情况。

比如如下字符表，huffman编码 以及 其对应的总二进制位数 ，最后1000字符总共也只有2100的bit存储空间。

所以这里根据频率构建huffman 编码的过程就用到了贪心的思想。

构建huffman树的过程 选择两个小频率的字符开始构建的父节点作为一个新节点，再选择一个次小的与该新节点一起构建一个新的父节点，依次由下向上构建。最终出现频率越高的字符串越靠近根节点。

构建过程如下：

void huffmanTree(priority_queue<Node> &q) {
  // root node is store in proiority_queue
  // when the q size is 1
  while (q.size() != 1) {
    Node *left = new Node(q.top()); 
    q.pop();
    Node *right = new Node(q.top()); 
    q.pop();
 
  // father's node and it's left and right child
    Node node('R', left->frequency + 
                    right->frequency, left, right);
    q.push(node);
  }
}

构建完huffman树之后，进行各个字符的编码，这里仅仅将所有的左子树权值设置为0，又子树权值设置为1就可以了

huffman编码过程如下：

// Huffman encode function
// param1: Root is the huffman tree's root node
// param2: prefix is the encode result per char
// param3: a map with 'char' and it's huffman's encode
void huffmanEncode(Node *root, string &prefix,
                 map<char, string> &result) {
  string m_prefix = prefix;
 
  if (root->left == nullptr)
    return;
 
  // set the left weight recursion
  prefix += "0";
  if (root->left->left == nullptr) {
    // find the char's result in the leaf node
    result[root->left->c] = prefix;
  } else {
    huffmanEncode(root->left, prefix, result);
  }
 
  // back to the begin node to set the right weight
  prefix = m_prefix;
 
  prefix += "1";
  if (root->right->right == nullptr) {
    result[root->right->c] = prefix;
  } else {
    huffmanEncode(root->right, prefix, result);
  }
}

huffman解码如下：

// Huffman decode function
// param1: des is the input string to be decode
// param2: res is the map between char and huffman's
// encode string
// param3: decode string
bool huffmanDecode(string des, map <char, string> res,
                   string &result) {
  if (des == "") {
    return false;
  }

  int i;
  map<char,string>::const_iterator it;
  string buf_str = "";

  for (i = 0; i < des.size(); i ++) {
    buf_str += des[i];
    for (it = res.begin() ; it != res.end(); it++ ) {
      if (it->second == buf_str) {
        result += it->first; 
        buf_str = "";
        break;
      }
    }

    if(i == des.size() - 1 && it == res.end()) {
      return false;
    }
  }
  
  return true;
}

完整测试代码:
​​​https://github.com/BaronStack/DATA_STRUCTURE/blob/master/greedy/haffman.cc​​