貪心算法簡單實踐 -- 分糖果、錢币找零、最多區間覆寫、哈夫曼編解碼

1. 貪心算法概覽

貪心算法是一種算法思想。希望能夠滿足限制的情況下将期望值最大化。比如：Huffman編碼，Dijkstra單源最短路徑問題，Kruskal最小生成樹等問題都希望滿足限制的情況下用最少的代價找到解決問題的辦法。

這個辦法就是貪心算法的思想。

實際用貪心算法解決問題可以有如下幾步：

當看到這類問題時我們能夠聯想到貪心算法：針對一組資料，我們定義了期望值和限制值，希望在滿足限制值的情況下期望值最大。

比如最短路徑中，限制值是每一次移動隻能向下或向右，期望值是走到終點（某個頂點），期望用最少的步數走到目标頂點。
嘗試使用貪心算法來解決問題：每一次做出選擇時在對限制值同等貢獻量的情況下，選擇對期望值貢獻最大的資料。
嘗試在案例資料中舉例，檢視貪心方式的實驗結果是否最優。

貪心算法适用的案例是每一次的選擇都是獨立事件，不會受到之前選擇的影響。比如有權圖中的最短路徑的查找，目前的選擇會對後續的選擇造成影響，第一次選擇最優的，後續可選的權值都是特别大的，則期望值并不是最優的。

可以看看如下幾個簡單實踐。

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 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;
}

貪心算法簡單實踐 -- 分糖果、錢币找零、最多區間覆寫、哈夫曼編解碼

1. 貪心算法概覽

2. 貪心算法實踐

2.1 分糖果

2.2 錢币找零

2.3 最多覆寫區間

2.4 哈夫曼編解碼

繼續閱讀

淺談MFC CSting類拼接效率

微信小程式前端解密擷取使用者資訊

C和java中關于字元串與字元數組的定義和轉化

Java：String類字元串與數組之間的轉換

Java中 byte[] 數組與 String 字元串的轉化

Spring MVC 自學雜記（五） -- SpringMVC與前台的json資料互動

《MySQL技術内幕：InnoDB存儲引擎》筆記

擴容TIKV節點遇到的坑

PHP輔導代做程式設計：CS353 Database System

自學Zabbix3.10.2-事件通知Notifications upon events-Actions報警配置點選傳回：自學zabbix集錦

HDU 5678 ztr loves trees

拓端tecdat|R語言彈性網絡Elastic Net正則化懲罰回歸模型交叉驗證可視化

二叉樹及其應用--二叉樹建立

回文樹學習小結

查找檔案中的字元串

詳解STM32單片機的堆棧