貪心演算法例子
㈠ 貪心演算法及其應用
求解一個問題時有多個步驟，每個步驟都選擇當下最優的那個解，而不用考慮整體的最優解。通常，當我們面對的問題擁有以下特點的時候，就可以考慮使用貪心演算法。
比如，我們舉個例子，倉庫裡面總共有五種豆子，其對應的重量和總價值如下，現在我們有一個可以裝100KG重量的袋子，怎麼裝才能使得袋子中的豆子價值最大？
我們首先看看這個問題是否符合貪心演算法的使用場景？限制值是袋子100KG，期望值是袋子裡面的價值最高。所以是符合的。那麼我們嘗試著應用下貪心演算法的方法，每一個步驟都尋找當下的最優解，怎麼做呢？
把倉庫裡面的每種豆子價值除以重量，得出每種豆子的單價，那麼當下的最優解，肯定是盡可能最多地裝單價最貴的，也就是先把20KG的黃豆都裝上，然後再把30KG的綠豆都裝上，再裝50KG的紅豆，那麼此時正好裝滿袋子，總價值將是270元，這就是通過貪心演算法求解的答案。
貪心演算法的應用在這個問題上的求解是否是最優解需要一個很復雜的數學論證，我們不用那樣，只要心裡舉幾個例子，驗證下是否比它更好即可，如果舉不出例子，那麼就可以認為這就是最優解了。
雖然貪心演算法雖然在大部分實踐場景中都能得到最優解，但是並不能保證一定是最優解。比如在如下的有向帶權圖中尋找從S到T的最短路徑，那麼答案肯定就是S->A->E->T，總代價為1+4+4=9；
然而，實際上的最短路徑是S->B->D->T，總代價為6。
所以，不能所有這類問題都迷信貪心演算法的求解，但其作為一種演算法指導思想，還是很值得學習的。
除了以上袋子裝豆子的問題之外，還有很多應用場景。這種問題能否使用貪心演算法來解決的關鍵是你能否將問題轉換為貪心演算法適用的問題，即找到問題的限制值和期望值。
我們有m個糖果要分給n個孩子，n大於m，註定有的孩子不能分到糖果。其中，每個糖果的大小都不同，分別為S1,S2,S3...,Sm，每個孩子對糖果的需求也是不同的，為N1,N2,N3...,Nn，那麼我們如何分糖果，才能盡可能滿足最多數量孩子的需求？
這個問題中，限制值是糖果的數量m，期望值滿足最多的孩子需求。對於每個孩子，能用小的糖果滿足其需求，就不要用大的，避免浪費。所以我們可以給所有孩子的需求排個序，從需求最小的孩子開始，用剛好能滿足他的糖果來分給他，以此來分完所有的糖果。
我們有1元、5元、10元、20元、50元、100元紙幣各C1、C5、C10、C20、C50、C100張，現在要購買一個價值K元的東西，請問怎麼才能適用最少的紙幣？
這個問題應該不難，限制值是各個紙幣的張數，期望值是適用最少的紙幣。那麼我們就先用面值最大的100元去付錢，當再加一張100元就超過K時，就更換小面額的，直至正好為K元。
對於n個區間[L1,R1],[L2,R2]...[Ln,Rn]，我們怎麼從中選出盡可能多的區間，使它們不相交？
我們需要把這個問題轉換為符合貪心演算法特點的問題，假設這么多區間的最左端點是Lmin，最右端點是Rmax，那麼問題就是在[Lmin,Rmax]中，選擇盡可能多的區間往裡面塞，並且保證它們不相交。這里，限制值就是區間[Lmin,Rmax]，期望值就是盡可能多的區間。
我們的解決辦法就是每次從區間中選擇那種左端點>=已經覆蓋區間右邊端點的，且該區間右端點盡可能高小的。如此，我們可以讓未覆蓋區間盡可能地大，才能保證可以塞進去盡可能多的區間。
貪心演算法最重要的就是學會如何將要解決的問題抽象成適合貪心演算法特點的模型，找到限制條件和期望值，只要做好這一步，接下來的就比較簡單了。在平時我們不用刻意去記，多多練習類似的問題才是最有效的學習方法。
㈡ 求解一道貪心演算法
因為這個問題涉及到高維求解（大於3維），所以不推薦你用貪心演算法或遺傳演算法之類的演算法。這里給出一種升級的蒙特卡羅演算法——自適應序貫數論演算法，這是一種以GLP集合為基礎的隨機遍歷演算法，可以很輕易的解決一系列的高維求解問題，目前根據網上能找到的資料最多可以做到18維。
下面就根據你給出的例子講解一下：
對於6000的料來說
1185最多做到5根（要求4根，所以一根木料對於1185的產品來說最多有0到45種可能）；1079最多做到5根；985最多做到6根；756最多做到7根。
所以第一次加工一根木料最多有5*6*7*8=1680種加工可能（當然其中包括那些產品總長度大於料長的可能，但是我們可以通過罰函數來避免這些情況），那麼利用GLP演算法我們可以一次性產生這1680種可能，然後逐個比較那種可能最省木料；
設第一加工出的產品量分別為1 1 3 1
那麼1185加工量剩3，1079剩5，985剩7，756剩7，所以第二次加工的可能性有（3+1）*（5+1）*（6+1）*（7+1）=1120種
關於自適應序貫數論演算法，根據這道題你可以這樣理解，4種尺寸構成了一個4維的空間，四種尺寸的每一種組合相當於空間中的一個點（1185的1根，1079的1根，985的3根，756的1根，這就組成了這個4維空間中的(1,1,3,1)點) ，自適應序貫數論演算法就是先根據GLP演算法在這個4維空間中隨機的，均勻的分布一定的點（也就是尺寸的組合），然後根據目標函數確定其中哪一個點是最優點，我們認為最優點的附近出現最優解的可能性最大，那麼我們就以最優點為中心，以一定的尺度為半徑將原空間縮小，然後我們在心空間中再一次利用GLP演算法均勻，隨機的充滿這個空間，然後重復以上過程，直到這個空間小到我們事先規定的大小，這樣我們就找到了最優解。
也許你會擔心演算法一上來就收斂到了局部最優解，然後一直在這里打轉，不用擔心，GLP最大的優點就是均勻的充斥整個空間，盡量將每一種可能都遍歷到。
這種演算法的缺點在於充斥空間用的點需要生成向量來生成，每一種充斥方式都需要不同的向量，你可以在《數論方法在統計中的應用》這本書中查到已有的每種充斥方式對應的那些生成向量。
下面是我跟據對你給出的例子的理解算出的結果。
1185:1根
1079:1根
985:3根
756:1根
剩餘木料0
1185:1根
1079:1根
985:3根
756:1根
剩餘木料0
1185:1根
1079:1根
985:3根
756:1根
剩餘木料0
1185:1根
1079:0根
985:1根
756:5根
剩餘木料15
1185:0根
1079:3根
985:0根
756:0根
剩餘木料2748
用去木料：5根
請按任意鍵繼續. . .
程序代碼如下：（變數都是用漢語拼音標的）
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <iostream.h>
#include <iomanip.h>
#include <time.h>
#include <fstream.h>
#include <windows.h>
#include "glp.h"
#define jiedeweishu 4
#define glpgeshu 10007
#define glpgeshu1 5003//100063
#define glpgeshu2 6007//33139//71053//172155//100063
#define yuanmuchang 6000
#define qiegesushi 5
#define chicun1 1185
#define chicun2 1079
#define chicun3 985
#define chicun4 756
#define chicun1shuliang 4
#define chicun2shuliang 6
#define chicun3shuliang 10
#define chicun4shuliang 8
float xuqiuchicun[jiedeweishu]={chicun1,chicun2,chicun3,chicun4};
float chicunxuqiuliang[jiedeweishu]={chicun1shuliang,chicun2shuliang,chicun3shuliang,chicun4shuliang};
float zuobianjie0[jiedeweishu];//{-19,1,-11,1.5,0,200};//{0.39111,-18.5,1,-11,1,0,2};//左邊界
float youbianjie0[jiedeweishu];//{-17,1.5,-7,2,0.05,900};//{0.393,-17,2,-9,2,0.1,6};//右邊界
float zuobianjie[jiedeweishu];
float youbianjie[jiedeweishu];
float zuobianjie1[jiedeweishu];//過度用
float youbianjie1[jiedeweishu];
float zuobianjie2[jiedeweishu];//局部邊界
float youbianjie2[jiedeweishu];
float zuobianjie3[jiedeweishu];//大邊界
float youbianjie3[jiedeweishu];
float sheng_cheng_xiang_liang[jiedeweishu]={1,1206,3421,2842};//生成向量
float sheng_cheng_xiang_liang1[jiedeweishu]={1,792,1889,191};//{1,39040,62047,89839,6347,30892,64404};//生成向量
float sheng_cheng_xiang_liang2[jiedeweishu]={1,1351,5080,3086};//{1,18236,1831,19143,5522,22910};//{1,18010,3155,50203,6065,13328};//{1,167459,153499,130657,99554,61040,18165};
struct chushi
{
float geti[jiedeweishu];
float shiying;
};
chushi *zuiyougeti;//精英保存策略
chushi *zuiyougetijicunqi;
int sishewuru(float);
float cha;//左右邊界的差
int biao;//判斷尋優是否成功1表示成功0表示不成功
int maxgen;//最大計算代數
int gen;//目前代數
void initialize();//演算法初始化
void jingyingbaoliu();//精英保存的實現
void mubiaohanshu1(chushi &bianliang);//適應度的計算使用殘差法
int cmpshiyingjiang(const void *p1,const void *p2)
{
float i=((chushi *)p1)->shiying;
float j=((chushi *)p2)->shiying;
return i<j ? 1:(i==j ? 0:-1);//現在是按降序牌排列，將1和-1互換後就是按升序排列
}
int cmp1(const void *p1,const void *p2)
{
float i= *(float*)p1;
float j= *(float*)p2;
return i<j ? 1:(i==j ? 0:-1);//現在是按降序牌排列，將1和-1互換後就是按升序排列
}
void main()
{
float bianjiebianhuashuzu[jiedeweishu];
float yiwanchengshuliang[jiedeweishu];
zuiyougeti=new chushi;//最優個體的生成
zuiyougetijicunqi=new chushi;
int i;
for(i=0;i<jiedeweishu;i++)
{
zuiyougeti->geti[i]=0;
yiwanchengshuliang[i]=0;
}
int muliaoshuliang=0;
while(1)
{
if(yiwanchengshuliang[0]==chicun1shuliang&&yiwanchengshuliang[1]==chicun2shuliang&&yiwanchengshuliang[2]==chicun3shuliang&&yiwanchengshuliang[3]==chicun4shuliang)
break;//都加工完了就退出程序
biao=1;
for(i=0;i<jiedeweishu;i++)
{
bianjiebianhuashuzu[i]=chicunxuqiuliang[i]-yiwanchengshuliang[i];
}
for(i=0;i<jiedeweishu;i++)
{
zuobianjie0[i]=0;
if(bianjiebianhuashuzu[i]>(int)(yuanmuchang/xuqiuchicun[i]))
{
youbianjie0[i]=(int)(yuanmuchang/xuqiuchicun[i]);
}
else
{
youbianjie0[i]=bianjiebianhuashuzu[i];
}
}
for(i=0;i<jiedeweishu;i++)
{
zuobianjie[i]=zuobianjie0[i];
youbianjie[i]=youbianjie0[i];
}
for(i=0;i<jiedeweishu;i++)//在這套程序中邊界分為兩個部分,其中一組是根據最優解的收斂范圍進行局部尋優,如果在局部找不到最優解則以現有最優解為中心進行全局搜索
{
zuobianjie2[i]=zuobianjie[i];
youbianjie2[i]=youbianjie[i];
zuobianjie3[i]=zuobianjie[i];
youbianjie3[i]=youbianjie[i];
}
zuiyougeti->shiying=-3000;
//cout<< zuiyougeti->shiying<<endl;
initialize();
//for(i=0;i<jiedeweishu;i++)/////
//{////
// cout<<zuiyougeti->geti[i]<<",";////
//}/////////
//cout<<endl;/////
// cout<<"初始最優解："<<" "<<-zuiyougeti->shiying<<endl;/////////////
for(gen=1;gen<maxgen;gen++)
{
jingyingbaoliu();
if(cha<1e-1)
break;
}
//cout<<"最終在收斂的范圍內左右邊界的最大差值: "<<cha<<endl;
//for(i=0;i<jiedeweishu;i++)
//{
// cout<<setiosflags(ios::fixed)<<setprecision(6)<<zuiyougeti->geti[i]<<",";
// }
//cout<<endl;
//cout<<"共用代數"<<gen<<endl;
cout<<"1185:"<<zuiyougeti->geti[0]<<"根"<<endl;
cout<<"1079:"<<zuiyougeti->geti[1]<<"根"<<endl;
cout<<"985:"<<zuiyougeti->geti[2]<<"根"<<endl;
cout<<"756:"<<zuiyougeti->geti[3]<<"根"<<endl;
cout<<"剩餘木料"<<(-zuiyougeti->shiying)<<endl;////////////////
cout<<endl;
for(i=0;i<jiedeweishu;i++)
{
yiwanchengshuliang[i]=yiwanchengshuliang[i]+zuiyougeti->geti[i];
}
muliaoshuliang++;
}
cout<<"用去木料："<<muliaoshuliang<<"根"<<endl;
delete [] zuiyougetijicunqi;
delete [] zuiyougeti;
system("pause");
}
void initialize()
{
maxgen=20;//最大代數
gen=0;//起始代
cha=100;
chushi *chushizhongqunji;
chushizhongqunji=new chushi[glpgeshu];
int i,j;
for(i=0;i<jiedeweishu;i++)
{
zuobianjie1[i]=zuobianjie[i];
youbianjie1[i]=youbianjie[i];
}
float **glp_shu_zu;//第一次求解，為了使解更精確這一次求解需要的點最多
glp_shu_zu=new (float *[glpgeshu]);
for(i=0;i<glpgeshu;i++)
{
glp_shu_zu[i]=new float[jiedeweishu];//生成的glp向量用glp_shu_zu儲存
}
glp glp_qiu_jie_first(glpgeshu,jiedeweishu);//定義生成多少組glp向量和向量的維數
glp_qiu_jie_first.glp_qiu_jie(glp_shu_zu,sheng_cheng_xiang_liang);//將生成的glp向量用glp_shu_zu儲存，同時將生成向量帶入glp類
for(i=0;i<glpgeshu;i++)//產生初始種群
{
for(j=0;j<jiedeweishu;j++)
{
chushizhongqunji[i].geti[j]=sishewuru((zuobianjie[j]+(youbianjie[j]-(zuobianjie[j]))*glp_shu_zu[i][j]));
if(j==3&&glp_shu_zu[i][j]<0)
{
cout<<"274"<<endl;/////////////
cout<<zuobianjie[j]<<" "<<glp_shu_zu[i][j]<<" "<<youbianjie[j]<<endl;////////////////////
system("pause");///////////////////
}
}
}
for(i=0;i<glpgeshu;i++)//計算初始種群的適應度
{
mubiaohanshu1(chushizhongqunji[i]);
}
qsort(chushizhongqunji,glpgeshu,sizeof(chushi),&cmpshiyingjiang);//根據適應度將初始種群集按降序進行排列
chushi *youxiugetiku;//建立一個儲存優秀個體的庫
youxiugetiku=new chushi[glpgeshu];//建立一個儲存優秀個體的庫
int jishuqi=0;
i=0;
while(chushizhongqunji[i].shiying>zuiyougeti->shiying)//凡是比上一代的最優個體還要好的個體都放入優秀個體庫
{
for(int j=0;j<jiedeweishu;j++)
{
youxiugetiku[i].geti[j]=chushizhongqunji[i].geti[j];
//cout<<youxiugetiku[i].geti[j]<<endl;
}
//system("pause");
i++;
}
// cout<<i<<endl;//////////////
//system("pause");//////////////////////////////////////
jishuqi=i;//將得到的優秀個體的數量放入jishuqi保存
float *bianjiezancunqi;//下面就要以優秀個體庫中個體的范圍在成立一個局部搜索區域，所以先建立一個邊界暫存器
bianjiezancunqi=new float[jishuqi];
for(i=0;i<jiedeweishu;i++)
{
for(int j=0;j<jishuqi;j++)
{
bianjiezancunqi[j]=youxiugetiku[j].geti[i];//將優秀個體庫每一維的數據都放入bianjiezancunqi
}
qsort(bianjiezancunqi,jishuqi,sizeof(float),&cmp1);//對這些數據按降序排列，取兩個邊界又得到一個局部范圍
//將得到的范圍進行保存
zuobianjie[i]=bianjiezancunqi[jishuqi-1];
youbianjie[i]=bianjiezancunqi[0];
//cout<<zuobianjie[i]<<endl;//////////////////////////
// cout<<youbianjie[i]<<endl;///////////////////////////
//cout<<endl;///////////////////
//
if(zuobianjie[i]<zuobianjie2[i])//如果新得到的局部左邊界在上一代局部左邊界左邊，則左邊界取上一代的
{
zuobianjie[i]=zuobianjie2[i];
}
if(youbianjie[i]>youbianjie2[i])//如果新得到的局部右邊界在上一代局部右邊界右邊，則右邊界取上一代的
{
youbianjie[i]=youbianjie2[i];
}
}
if(chushizhongqunji[0].shiying>zuiyougeti->shiying)//本代種群的最優個體比歷史最有個個體好，則用本代的代替之，並將標志位賦值為1表示尋優成功
{
for(i=0;i<jiedeweishu;i++)
{
zuiyougeti->geti[i]=chushizhongqunji[0].geti[i];
}
zuiyougeti->shiying=chushizhongqunji[0].shiying;
biao=1;
}
delete [] bianjiezancunqi;
delete [] youxiugetiku;
for(i=0;i<glpgeshu;i++)
{
delete [] glp_shu_zu[i];
}
delete [] glp_shu_zu;
delete [] chushizhongqunji;
}
void jingyingbaoliu() //精英保留的實現
{
float glpshuliang,xiangliang[jiedeweishu];
if(biao==1)//如果尋優成功則利用局部搜索的數據
{
glpshuliang=glpgeshu1;
for(int i=0;i<jiedeweishu;i++)
{
xiangliang[i]=sheng_cheng_xiang_liang1[i];
}
}
else//否則利用全局搜索的數據
{
glpshuliang=glpgeshu2;
for(int i=0;i<jiedeweishu;i++)
{
xiangliang[i]=sheng_cheng_xiang_liang2[i];
}
}
chushi *chushizhongqunji;//建立一個用來儲存種群的容器
chushizhongqunji=new chushi[glpshuliang];
int i,j;
float **glp_shu_zu;//生成一個glp數組
glp_shu_zu=new (float *[glpshuliang]);
for(i=0;i<glpshuliang;i++)
{
glp_shu_zu[i]=new float[jiedeweishu];//生成的glp向量用glp_shu_zu儲存
}
glp glp_qiu_jie_first(glpshuliang,jiedeweishu);//定義生成多少組glp向量和向量的維數
glp_qiu_jie_first.glp_qiu_jie(glp_shu_zu,xiangliang);//將生成的glp向量用glp_shu_zu儲存，同時將生成向量帶入glp類
//cout<<"377"<<endl;
if(biao!=1)//如果尋優不成功則進入全局搜索
{
//cout<<"380"<<endl;////////////
float bianjiecha[jiedeweishu];
for(i=0;i<jiedeweishu;i++)
{
bianjiecha[i]=youbianjie3[i]-zuobianjie3[i];//計算上一代全局每一維范圍的寬度
}
static float rou=0.9;//定義收縮比
//float rou=pow(0.5,gen);
for(i=0;i<jiedeweishu;i++)//確定新的范圍
{
zuobianjie1[i]=zuiyougeti->geti[i]-rou*bianjiecha[i];//左邊界為以最優個體為中心-范圍寬度乘以收縮比
if(zuobianjie1[i]>zuobianjie2[i])//如果新的左邊界比目前局部左邊界大，那麼以目前的為全局尋優的左邊界
{
zuobianjie[i]=zuobianjie1[i];
zuobianjie3[i]=zuobianjie1[i];
}
else//否則以局部左邊界為全局左邊界
{
zuobianjie[i]=zuobianjie2[i];
zuobianjie3[i]=zuobianjie2[i];
}
youbianjie1[i]=zuiyougeti->geti[i]+rou*bianjiecha[i];//右邊界為以最優個體為中心+范圍寬度乘以收縮比
if(youbianjie1[i]<youbianjie2[i])
{
youbianjie[i]=youbianjie1[i];
youbianjie3[i]=youbianjie1[i];
}
else
{
youbianjie[i]=youbianjie2[i];
youbianjie3[i]=youbianjie2[i];
}
}
qsort(bianjiecha,jiedeweishu,sizeof(float),&cmp1);
if(cha==bianjiecha[0])//如果最大邊界差不變的話就將收縮因子變小
{
rou=pow(rou,2);
}
cha=bianjiecha[0];
}
//cout<<"421"<<endl;/////////////////////
for(i=0;i<glpshuliang;i++)//根據新產生的最優個體確定glp群
{
for(j=0;j<jiedeweishu;j++)
{
chushizhongqunji[i].geti[j]=sishewuru((zuobianjie[j]+(youbianjie[j]-(zuobianjie[j]))*glp_shu_zu[i][j]));
}
}
for(i=0;i<glpshuliang;i++)
{
mubiaohanshu1(chushizhongqunji[i]);
}
qsort(chushizhongqunji,glpshuliang,sizeof(chushi),&cmpshiyingjiang);
zuiyougetijicunqi->shiying=zuiyougeti->shiying;
if(chushizhongqunji[0].shiying>zuiyougeti->shiying)
{
for(i=0;i<jiedeweishu;i++)
{
zuiyougeti->geti[i]=chushizhongqunji[0].geti[i];
}
zuiyougeti->shiying=chushizhongqunji[0].shiying;
biao=1;
}
else
{
// cout<<"446"<<endl;/////////////
biao=0;
}
if(biao==1)//如果尋優成功了就需要確立一個新的局部最優解范圍
{
chushi *youxiugetiku;
youxiugetiku=new chushi[glpshuliang];
int jishuqi=0;
i=0;
while(chushizhongqunji[i].shiying>zuiyougetijicunqi->shiying)
{
for(int j=0;j<jiedeweishu;j++)
{
youxiugetiku[i].geti[j]=chushizhongqunji[i].geti[j];
}
i++;
}
jishuqi=i;
float *bianjiezancunqi;
bianjiezancunqi=new float[jishuqi];
for(i=0;i<jiedeweishu;i++)
{
for(int j=0;j<jishuqi;j++)
{
bianjiezancunqi[j]=youxiugetiku[j].geti[i];
}
qsort(bianjiezancunqi,jishuqi,sizeof(float),&cmp1);
zuobianjie[i]=bianjiezancunqi[jishuqi-1];
youbianjie[i]=bianjiezancunqi[0];
// cout<<zuobianjie[i]<<endl;//////////////
// cout<<youbianjie[i]<<endl;/////////////
// cout<<endl;///////////////
if(zuobianjie[i]<zuobianjie2[i])
{
zuobianjie[i]=zuobianjie2[i];
}
if(youbianjie[i]>youbianjie2[i])
{
youbianjie[i]=youbianjie2[i];
}
}
delete [] bianjiezancunqi;
delete [] youxiugetiku;
}
for(i=0;i<glpshuliang;i++)
{
delete [] glp_shu_zu[i];
}
delete [] glp_shu_zu;
delete [] chushizhongqunji;
}
void mubiaohanshu1(chushi &bianliang)//計算shiying
{
int i=0;
int sunshi,chanpin;
sunshi=qiegesushi*(bianliang.geti[0]+bianliang.geti[1]+bianliang.geti[2]+bianliang.geti[3]-1);
chanpin=chicun1*bianliang.geti[0]+chicun2*bianliang.geti[1]+chicun3*bianliang.geti[2]+chicun4*bianliang.geti[3];
bianliang.shiying=yuanmuchang-sunshi-chanpin;
if(bianliang.shiying!=0)//如果不能正好將木料分成所需尺寸則要多切一刀
{
sunshi=qiegesushi*(bianliang.geti[0]+bianliang.geti[1]+bianliang.geti[2]+bianliang.geti[3]);
}
if(bianliang.shiying<0)//罰函數
{
bianliang.shiying=bianliang.shiying+1e5;
}
bianliang.shiying=-bianliang.shiying;
}
int sishewuru(float x)
{
float y;
int z;
y=x-(int)x;
if(y<0.5)
{
z=(int)(x);
}
else
{
z=(int)x;
z=z+1;
}
return z;
}
glp.h源文件貼不下了，把你郵箱給我我發給你
郵箱：[email protected]
㈢ 哈夫曼編碼（貪心演算法）
參考： 哈夫曼編碼
哈夫曼編碼是一種十分有效的編碼方法，廣泛應用於 數據壓縮 中
通過採用 不等長 的編碼方式，根據 字元頻率的不同 ，選擇 不差派拿同長度的編碼 ，對頻率 越高 的字元採用 越短 的編碼實現數據的高度壓縮。
這種對頻率越高的字元採用越短的編碼來編碼的方式應用的就是貪心演算法的思想。
下面看一個例子：
假如我們有虛搭一個包含1000個字元的文件，每個字元佔1個byte(1byte=8bits)，則存儲這100個字元一共需要8000bits。這還是有一些大的
那我們統計一下這1000個字元中總共有多少種字元，原來需要8bit來表示一個字元，如果使用更少的位數來表示這些字元，則可以減少存儲空間。
假設這1000個字元中總共有a、b、c、d、e、f共6種字元，使用使用3個二進制位來表示的話，存儲這1000個字元就只需要3000bits，比原來更節省存儲空間。
或許還可以再壓縮一下：
根據字元出現的 頻率 給與字元 不等長 的編碼，頻率越高的字元編碼越短，頻率越低的字元編碼越長。
它不能像等長編碼一樣直接按固定長度去讀取二進制位，翻譯成字元，為了能夠准確讀取翻譯字元，它要求一個字元的編碼不能是另外一個字元的前綴。
假設a、b、c、d、e、f這6個字元出現的頻率依次降低，則我們可以給與他們這樣的編碼
假如字元的出現頻率如圖所示，按照這樣的編碼表示的話，總位數如圖，一共2100bits，更加節省空間了
貪心策略：頻率小的字元，優先入隊。
步驟：
1.將每一個字元作為節點，以出現頻率大小作為權重，將其都放入 優先隊列 中（一個最小堆）；
2.每次出隊兩個節點並創建一個父節點，使其權值為剛剛出隊的節點的權值和，並且為兩個節點的父節點（合並）。然後將這個樹入隊。
3.重復操作2，直到隊列中只有一個元素（此時這個元素表示形式應該為一個樹）時，完成創建。
創建好了樹，該怎麼編碼呢？
我們對一個哈夫曼樹，從父節點開始的所有節點，往左邊標0，右邊標1。那麼到達葉子節點的順次編碼就可以找到了。
C：字元集合
Q：優先隊列
EXTRACT-MIN：傳入一羨山個隊列，出隊最小的元素
INSERT：將z插入到Q中
當for循環結束之後，此時隊列中只有一個元素，就是我們需要的哈夫曼樹，最後返回此樹即可。
假設T樹已經是一個最優的樹，假設x、y的頻率小於等於最低處的a、b，然後交換x、a，y、b。
計算代價是否發生變化。
比如這里比較 T 變成 T 』 後代價是否變化，發現代價變小或不變。
同理T』到T』』，又因為T本來假設就是最優的，所以只能相等
所以T』』也應該符合條件，即貪婪演算法，每次取最小的兩個節點出來這種做法是正確的
㈣ 貪心演算法幾個經典例子
貪心演算法經典例子如下：
活動安排問題是可以用貪心演算法有效求解的一個很好的例子，該問題要求高效地安排一系列爭用某一公共資源的活動。貪心演算法提供了一個簡單、漂亮的方法使得盡可能多的活動能兼容地使用公共資源。
設有n個活動的集合e=（1，2，…，n），其中每個活動都要求使用同一資源，如演講會場等，而在同一時間內只有一個活動能使用這一資源。每個活動i都有一個要求使用該資源的起始時間si和一個結束時間fi，且si<fi。如果選擇了活動i，則它在半開時間區間（si，fi）內佔用資源。
活動安排問題
若區間（si，fi）與區間（sj，fj）不相交，則稱活動i與活動j是相容的。也就是說，當si≥fi或sj≥fj時，活動i與活動j相容。活動安排問題就是要在所給的活動集合中選出最大的相容活動子集合。
在下面所給出的解活動安排問題的貪心演算法gpeedyselector中，各活動的起始時間和結束時間存儲於數組s和f中且按結束時間的非減序：f1≤f2≤…≤fn排列。如果所給出的活動未按此序排列，我們可以用o（nlogn）的時間將它重排。
㈤ 分析用動態規劃和貪心演算法求解背包問題的差異
動態規劃本質是以空間換時間，算出了所有可行解的值域。
而貪心演算法，每次選則最優的，而結果未必最優。
舉個簡單例子。
背包能裝8kg,有3個物品，分別為3kg,4kg,5kg
動態規劃，是計算，3+4， 3+5，得出解，最大的是3+5=8kg
貪心演算法，是選擇，第一次選最大的：5kg<8kg，第二次選則剩下的最大的4kg，4+5>8,故而解為5kg。
㈥ 0/1背包問題能不能使用貪心法解決
貪心演算法解決背包問題有幾種策略：
(i)一種貪婪准則為：從剩餘的物品中，選出可以裝入背包的價值最大的物品，利用這種規則，價值最大的物品首先被裝入（假設有足夠容量），然後是下一個價值最大的物品，如此繼續下去。這種策略不能保證得到最優解。例如，考慮n=2, w=[100,10,10], p =[20,15,15], c = 105。當利用價值貪婪准則時，獲得的解為x= [ 1 , 0 , 0 ]，這種方案的總價值為2 0。而最優解為[ 0 , 1 , 1 ]，其總價值為3 0。
(ii)另一種方案是重量貪婪准則是：從剩下的物品中選擇可裝入背包的重量最小的物品。雖然這種規則對於前面的例子能產生最優解，但在一般情況下則不一定能得到最優解。考慮n= 2 ,w=[10,20], p=[5,100], c= 2 5。當利用重量貪婪策略時，獲得的解為x =[1,0], 比最優解[ 0 , 1 ]要差。
(iii)還有一種貪婪准則，就是我們教材上提到的，認為，每一項計算yi=vi/si,即該項值和大小的比，再按比值的降序來排序，從第一項開始裝背包，然後是第二項，依次類推，盡可能的多放，直到裝滿背包。
有的參考資料也稱為價值密度pi/wi貪婪演算法。這種策略也不能保證得到最優解。利用此策略試解n= 3 ,w=[20,15,15], p=[40,25,25], c=30 時的最優解。雖然按pi /wi 非遞（增）減的次序裝入物品不能保證得到最優解，但它是一個直覺上近似的解。
而且這是解決普通背包問題的最優解，因為在選擇物品i裝入背包時，可以選擇物品i的一部分，而不一定要全部裝入背包，1≤i≤n。
㈦ 找零錢問題的貪心演算法
問題描述：
當前有面值分別為2角5分，1角，5分，1分的硬幣，請給出找n分錢的最佳方案（要求找出的硬幣數目最少）
問題分析：
根據常識，我們到店裡買東西找錢時，老闆總是先給我們最大面值的，要是不夠再找面值小一點的，直到找滿為止。如果老闆都給你找分數的或者幾角的，那你肯定不幹，另外，他也可能沒有那麼多零碎的錢給你找。其實這就是一個典型的貪心選擇問題。
問題的演算法設計與實現：
先舉個例子，假如老闆要找給我99分錢，他有上面的面值分別為25，10，5，1的硬幣數，為了找給我最少的硬幣數，那麼他是不是該這樣找呢，先看看該找多少個25分的， 99／25＝3，好像是3個，要是4個的話，我們還得再給老闆一個1分的，我不幹，那麼老闆只能給我3個25分，由於還少給我24，所以還得給我2個10分的和4個1分。
具體實現
//找零錢演算法
//By falcon
//輸入：數組m，依次存放從大到小排列的面值數，n為需要找的錢數，單位全部為分
//輸出：數組num，對照數組m中的面值存放不同面值的硬幣的個數，即找錢方案