文章目錄

• • 1. 貪心算法
  • 2. 應(yīng)用
  • • 2.1 找零錢
    • 2.2 區(qū)間覆蓋
    • 2.3 霍夫曼編碼
    • • 霍夫曼編碼完整代碼

1. 貪心算法

• 我們希望在一定的限制條件下，獲得一個(gè)最優(yōu)解
• 每次都在當(dāng)前的標(biāo)準(zhǔn)下做出當(dāng)下最優(yōu)決策（整體不一定最優(yōu)），做出的決策不可以后悔，即不回溯，最終可以得到較為滿意的解
• 貪心算法不追求最優(yōu)解，節(jié)省時(shí)間，避免窮盡所有可能

2. 應(yīng)用

2.1 找零錢

給定金額的找零，用最少張（枚）錢給顧客。（總是優(yōu)先給大額的）

/*** @description: 貪心應(yīng)用--找零錢* @author: michael ming* @date: 2019/6/28 22:02* @modified by: */ #include <iostream> #include <memory.h> #include <math.h> #define N 10 using namespace std; void exchange(float money, float *rmb, int *amount) {if(money < 0.1)return;int i, k = 0;for(i = 0; i < N; ++i){money = round(money*10)/10.0;//四舍五入掉分k = money/rmb[i];amount[i] = k;money = money-k*rmb[i];} } int main() {float rmb[N] = {100, 50, 20, 10, 5, 2, 1, 0.5, 0.2, 0.1};int amount[N];while(1){memset(amount,0,N*sizeof(int));float money;cout << "請輸入要找的錢的金額：";cin >> money;money = round(money*10)/10.0;//四舍五入掉分cout << "找零結(jié)果如下(分位四舍五入)：" << endl;exchange(money,rmb,amount);int i = 0;while(i < N){if(amount[i] != 0)cout << amount[i] << "個(gè)" << rmb[i] << " ";i++;}cout << endl;cout << "----------------------" << endl;} }

2.2 區(qū)間覆蓋

運(yùn)用場景：任務(wù)調(diào)度，教師排課，學(xué)生活動(dòng)室安排等

在上面圖中再加入些區(qū)間數(shù)據(jù)[2,3];[-1,4],[5,12];[4,5]，代碼實(shí)現(xiàn)如下：

/*** @description: 貪心算法--區(qū)間覆蓋應(yīng)用* (給定每個(gè)人可以在一個(gè)房間內(nèi)活動(dòng)的時(shí)間，要求讓最多的人在這個(gè)房間活動(dòng)，打印出這些人)* @author: michael ming* @date: 2019/6/29 23:34* @modified by: */ #include <iostream> #include <algorithm> using namespace std; struct Interval {int left, right;bool operator<(const Interval &sel_idx) const{if(left == sel_idx.left)return right < sel_idx.right;//左端點(diǎn)相等，取右端小的elsereturn left < sel_idx.left;//左端不等，取左端小的}bool belongto(int l, int r)//區(qū)間屬于[l,r]的子集{return left >= l && right <= r;}bool absnotbelong(int l, int r)//兩個(gè)區(qū)間完全無重疊{return left >= r || right <= l;} }; int main() {const int N = 10;//區(qū)間數(shù)量int left = 1, right = 10;//大區(qū)間左右端點(diǎn)（房間開放時(shí)間）int select[N];//存儲(chǔ)選出來的區(qū)間（人）idint i, j, k, sel_idx = 0;for(i = 0; i < N; ++i){select[i] = -1;}Interval qujian[N] = {{1,5},{2,4},{3,5},{5,9},{6,8},{8,10},{2,3},{-1,4},{5,12},{4,5}};//所有人的占用時(shí)間段sort(qujian,qujian+N);//對區(qū)間進(jìn)行排序（先按開始時(shí)間早排序，一樣早，按占用時(shí)間少排前面）for(i = 0; i < N; ++i){if(qujian[i].left >= left && qujian[i].right <= right)//占用時(shí)間在開放時(shí)間內(nèi){while(sel_idx != 0 && !qujian[i].absnotbelong(qujian[select[sel_idx-1]].left,qujian[select[sel_idx-1]].right)){//如果有人占用了房間，一直找到第一個(gè)跟他時(shí)間不沖突的人++i;}for(k = i, j = k+1; j < N; ++j){//找到時(shí)間是不沖突那個(gè)人的最小子集的人if(qujian[j].belongto(qujian[k].left,qujian[k].right)){k = j;}}select[sel_idx++] = k;//占用最短的那個(gè)人選出來i = k;//從這個(gè)人開始再往后找}}cout << "total selected " << sel_idx << " people, their time as following:" << endl;for(i = 0; i < N && select[i] != -1; ++i){//打印被選出來的人的時(shí)間信息cout << i << ": [" << qujian[select[i]].left << ","<< qujian[select[i]].right << "]" << endl;}return 0; }

2.3 霍夫曼編碼

• 假設(shè)有一個(gè)包含1000個(gè)字符的文件，每個(gè)字符占1個(gè)byte（1byte=8bits），存儲(chǔ)這1000個(gè)字符一共需要8000bits，有沒有更加節(jié)省空間的存儲(chǔ)方式呢？
• 假設(shè)通過統(tǒng)計(jì)發(fā)現(xiàn)，這1000個(gè)字符中只包含6種不同字符，假設(shè)它們分別是a、b、c、d、e、f。而3個(gè)二進(jìn)制位（bit）就可以表示8個(gè)不同的字符，a(000)、b(001)、c(010)、d(011)、e(100)、f(101)，所以，為了盡量減少存儲(chǔ)空間，每個(gè)字符我們用3個(gè)二進(jìn)制位來表示。那存儲(chǔ)這1000個(gè)字符只需要3000bits就可以了，比原來的存儲(chǔ)方式節(jié)省了很多空間。
• 還有沒有更加節(jié)省空間的存儲(chǔ)方式呢？
• 霍夫曼編碼，考慮字符的出現(xiàn)頻率，頻率小的，用長編碼，大的，用短編碼，使得總體編碼長度變短（且由于其編碼方式，沒有一個(gè)字符的編碼是另一個(gè)的編碼的前綴，避免了解碼過程中的歧義）
  
  
  

霍夫曼編碼完整代碼

/*** @description: 貪心應(yīng)用--霍夫曼編碼* @author: michael ming* @date: 2019/6/30 23:53* @modified by: */ #include <string> #include <vector> #include <queue> #include <iostream> #include <algorithm> #include <memory.h>#define N 6 //字符集字符種數(shù) using namespace std; struct htNode//霍夫曼樹節(jié)點(diǎn) {char data;//數(shù)據(jù)類型char code;//數(shù)據(jù)存放的節(jié)點(diǎn)編碼unsigned int weight;//數(shù)據(jù)權(quán)值htNode *parent, *lchild, *rchild;//連接節(jié)點(diǎn)指針htNode():data('/'),code('\0'),weight(0){parent = lchild = rchild = NULL;} }; class comp//優(yōu)先隊(duì)列比較函數(shù) { public:bool operator()(htNode* &a, htNode* &b)const{if(a->weight == b->weight)return a->data > b->data;return a->weight > b->weight;} };class HuffmanTree { public:htNode *root;//根節(jié)點(diǎn)指針htNode* node[2*N-1];//N個(gè)字符，霍夫曼樹節(jié)點(diǎn)個(gè)數(shù)2*N-1priority_queue<htNode*,vector<htNode*>,comp> pri_queue;//優(yōu)先隊(duì)列中存放類指針時(shí)，第三個(gè)參數(shù)應(yīng)該另寫一個(gè)comp類，類內(nèi)寫operator()void creatTree_outputCode(int *w){char ch = 'a';htNode *left, *right;for(int i = 0; i < N; ++i,++ch){//生成前N個(gè)字符節(jié)點(diǎn)，輸入權(quán)重，和字符信息//并放入優(yōu)先隊(duì)列（權(quán)值小的優(yōu)先）node[i] = new htNode();node[i]->weight = w[i];node[i]->data = ch;pri_queue.push(node[i]);}for(int i = N; i < 2*N-1; ++i){//后面新生成的N-1個(gè)節(jié)點(diǎn)node[i] = new htNode();if(pri_queue.top()->data != '/'){//隊(duì)首的節(jié)點(diǎn)不是新生成的，隊(duì)首放右邊right = pri_queue.top();right->code = '1';//右邊節(jié)點(diǎn)編碼1pri_queue.pop();left = pri_queue.top();left->code = '0';//左邊節(jié)點(diǎn)編碼0pri_queue.pop();//左右節(jié)點(diǎn)出隊(duì)}else{//隊(duì)首是新生成的節(jié)點(diǎn)，放左邊//（以上if-else保證新生成的節(jié)點(diǎn)總在左邊）left = pri_queue.top();left->code = '0';pri_queue.pop();right = pri_queue.top();right->code = '1';pri_queue.pop();//左右節(jié)點(diǎn)出隊(duì)}//新節(jié)點(diǎn)權(quán)值、上下連接指針對接node[i]->weight = left->weight+right->weight;node[i]->lchild = left;node[i]->rchild = right;left->parent = node[i];right->parent = node[i];pri_queue.push(node[i]);//新生成的節(jié)點(diǎn)入隊(duì)}root = pri_queue.top();//最后還剩一個(gè)節(jié)點(diǎn)，是根節(jié)點(diǎn)creatHuffCode();for(int i = 0; i < 2*N-1; ++i)//釋放資源{delete node[i];}}void creatHuffCode(){htNode *parent;string huffcode;//霍夫曼編碼int codelen = 0;//輸入的字符串編碼后的總長度bitsfor(int i = 0; i < N; ++i)//遍歷前N個(gè)字符節(jié)點(diǎn)，求其編碼{huffcode = "";parent = node[i];//從自己（葉子節(jié)點(diǎn)）開始向上找父節(jié)點(diǎn)，直到rootcout << i+1 << " " << node[i]->data << " 的霍夫曼編碼是: ";while(parent != root)//{huffcode.push_back(parent->code);//將路徑中的編碼匯成字符串parent = parent->parent;}reverse(huffcode.begin(),huffcode.end());//將最終的編碼反轉(zhuǎn)一下cout << huffcode << endl;codelen += huffcode.size()*node[i]->weight;//單字符code長*出現(xiàn)次數(shù)}cout << "該字符串的huffman編碼長度為: " << codelen << " bits.";} };int main() {HuffmanTree huff;cout << "請輸入某字符串中" << N << "個(gè)字母abc...的權(quán)值（頻率）：" << endl;int w[N];//權(quán)重for(int i = 0; i < N; ++i){cout << i+1 << " ";cin >> w[i];//輸入權(quán)值}huff.creatTree_outputCode(w);//將權(quán)值傳入并生成Huffman樹;生成霍夫曼編碼，打印出來return 0; }

總結(jié)

以上是生活随笔為你收集整理的贪心算法（Greedy Algorithm）之霍夫曼编码的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。