贪心算法几个经典例子

⓵求解一道贪心算法

因为这个问题涉及到高维求解（大于3维），所以不推荐你用贪心算法或传算法之类的算法。
这里给出一种升级的蒙特卡罗算法——自适应序贯数论算法，这是一种以GLP***为基础的随机遍历算法，可以很轻易的解决一系列的高维求解问题，目前根据网上能找到的资料最多可以做到18维。
下面就根据你给出的例子讲解一下：
对于6000的料来说
1185最多做到5根（要求4根，所以一根木料对于1185的产品来说最多有0到45种可能）；1079最多做到5根；985最多做到6根；756最多做到7根。
所以第一次加工一码裂根木料最多有5*6*7*8=1680种加工可能（当然其中包括那些产品总度大迟卜闭于料的可能，但是我们可以通过罚函数来避免这些情况），那么利用GLP算法我们可以一次性产生这1680种可能，然后逐个比较那种可能最木料；
设第一加工出的产品量分别为1131
那么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"
#definejiedeweishu4
#defineglpgeshu10007
#defineglpgeshu15003//100063
#defineglpgeshu26007//33139//71053//172155//100063
#defineyuanmuchang6000
#defineqiegesushi5
#definechicun11185
#definechicun21079
#definechicun3985
#definechicun4756
#definechicun1shuliang4
#definechicun2shuliang6
#definechicun3shuliang10
#definechicun4shuliang8
floatxuqiuchicun[jiedeweishu]={chicun1,chicun2,chicun3,chicun4};
floatchicunxuqiuliang[jiedeweishu]={chicun1shuliang,chicun2shuliang,chicun3shuliang,chicun4shuliang};
floatzuobianjie0[jiedeweishu];//{-19,1,-11,1.5,0,200};//{0.39111,-18.5,1,-11,1,0,2};//左边界
floatyoubianjie0[jiedeweishu];//{-17,1.5,-7,2,0.05,900};//{0.393,-17,2,-9,2,0.1,6};//右边界
floatzuobianjie[jiedeweishu];
floatyoubianjie[jiedeweishu];
floatzuobianjie1[jiedeweishu];//过度用
floatyoubianjie1[jiedeweishu];
floatzuobianjie2[jiedeweishu];//部边界
floatyoubianjie2[jiedeweishu];
floatzuobianjie3[jiedeweishu];//大边界
floatyoubianjie3[jiedeweishu];
floatsheng_cheng_xiang_liang[jiedeweishu]={1,1206,3421,2842};//生成向量
floatsheng_cheng_xiang_liang1[jiedeweishu]={1,792,1889,191};//{1,39040,62047,89839,6347,30892,64404};//生成向量
floatsheng_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};
structchushi
{
floatgeti[jiedeweishu];
floatshiyingdu;
};
chushi*zuiyougeti;//精英保存策略
chushi*zuiyougetijicunqi;
intsishewuru(float);
floatchazhi;//左右边界的差
intbiaozhi;//判断寻优是否成功1表示成功0表示不成功
intmaxgen;//最大计算代数
intgen;//目前代数
voidinitialize;//算法初始化
voidjingyingbaoliu;//精英保存的实现
voidmubiaohanshu1(chushi&bianliang);//适应度的计算使用残差法
intcmpshiyingdujiang(constvoid*p1,constvoid*p2)
{
floati=((chushi*)p1)->shiyingdu;
floatj=((chushi*)p2)->shiyingdu;
returni<j?1:(i==j?0:-1);//现在是按降序牌排列，将1和-1互换后就是按升序排列
}
intcmp1(constvoid*p1,constvoid*p2)
{
floati=*(float*)p1;
floatj=*(float*)p2;
returni<j?1:(i==j?0:-1);//现在是按降序牌排列，将1和-1互换后就是按升序排列
}
voidmain
{
floatbianjiebianhuashuzu[jiedeweishu];
floatyiwanchengshuliang[jiedeweishu];
zuiyougeti=newchushi;//最优个体的生成
zuiyougetijicunqi=newchushi;
inti;
for(i=0;i<jiedeweishu;i++)
{
zuiyougeti->geti[i]=0;
yiwanchengshuliang[i]=0;
}
intmuliaoshuliang=0;
while(1)
{
if(yiwanchengshuliang[0]==chicun1shuliang&&yiwanchengshuliang[1]==chicun2shuliang&&yiwanchengshuliang[2]==chicun3shuliang&&yiwanchengshuliang[3]==chicun4shuliang)
break;//都加工完了就退出程序
biaozhi=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->shiyingdu=-3000;
//cout<<zuiyougeti->shiyingdu<<endl;
initialize;
//for(i=0;i<jiedeweishu;i++)///
//{//
//cout<<zuiyougeti->geti[i]<<",";//
//}///
//cout<<endl;///
//cout<<"初始最优解："<<""<<-zuiyougeti->shiyingdu<<endl;/////
for(gen=1;gen<maxgen;gen++)
{
jingyingbaoliu;
if(chazhi<1e-1)
break;
}
//cout<<"最终在收敛的范围内左右边界的最大差值:"<<chazhi<<endl;
//for(i=0;i<jiedeweishu;i++)
//{
//cout<<setiosflags(ios::fixed)<<setpre cision(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->shiyingdu)<<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");
}
voidinitialize
{
maxgen=20;//最大代数
gen=0;//起始代
chazhi=100;
chushi*chushizhongqunji;
chushizhongqunji=newchushi[glpgeshu];
inti,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]=newfloat[jiedeweishu];//生成的glp向量用glp_shu_zu储存
}
glpglp_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),&cmpshiyingdujiang);//根据适应度将初始种群集按降序进行排列
chushi*youxiugetiku;//建立一个储存优秀个体的库
youxiugetiku=newchushi[glpgeshu];//建立一个储存优秀个体的库
intjishuqi=0;
i=0;
while(chushizhongqunji[i].shiyingdu>zuiyougeti->shiyingdu)//凡是比上一代的最优个体还要好的个体都放入优秀个体库
{
for(intj=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=newfloat[jishuqi];
for(i=0;i<jiedeweishu;i++)
{
for(intj=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].shiyingdu>zuiyougeti->shiyingdu)//本代种群的最优个体比历史最有个个体好，则用本代的代替之，并将标志位赋值为1表示寻优成功
{
for(i=0;i<jiedeweishu;i++)
{
zuiyougeti->geti[i]=chushizhongqunji[0].geti[i];
}
zuiyougeti->shiyingdu=chushizhongqunji[0].shiyingdu;
biaozhi=1;
}
delete[]bianjiezancunqi;
delete[]youxiugetiku;
for(i=0;i<glpgeshu;i++)
{
delete[]glp_shu_zu[i];
}
delete[]glp_shu_zu;
delete[]chushizhongqunji;
}
voidjingyingbaoliu//精英保留的实现
{
floatglpshuliang,xiangliang[jiedeweishu];
if(biaozhi==1)//如果寻优成功则利用部搜索的数据
{
glpshuliang=glpgeshu1;
for(inti=0;i<jiedeweishu;i++)
{
xiangliang[i]=sheng_cheng_xiang_liang1[i];
}
}
else//否则利用全搜索的数据
{
glpshuliang=glpgeshu2;
for(inti=0;i<jiedeweishu;i++)
{
xiangliang[i]=sheng_cheng_xiang_liang2[i];
}
}
chushi*chushizhongqunji;//建立一个用来储存种群的容器
chushizhongqunji=newchushi[glpshuliang];
inti,j;
float**glp_shu_zu;//生成一个glp数组
glp_shu_zu=new(float*[glpshuliang]);
for(i=0;i<glpshuliang;i++)
{
glp_shu_zu[i]=newfloat[jiedeweishu];//生成的glp向量用glp_shu_zu储存
}
glpglp_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(biaozhi!=1)//如果寻优不成功则进入全搜索
{
//cout<<"380"<<endl;////
floatbianjiecha[jiedeweishu];
for(i=0;i<jiedeweishu;i++)
{
bianjiecha[i]=youbianjie3[i]-zuobianjie3[i];//计算上一代全每一维范围的宽度
}
staticfloatrou=0.9;//定义收缩比
//floatrou=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(chazhi==bianjiecha[0])//如果最大边界差不变的话就将收缩因子变小
{
rou=pow(rou,2);
}
chazhi=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),&cmpshiyingdujiang);
zuiyougetijicunqi->shiyingdu=zuiyougeti->shiyingdu;
if(chushizhongqunji[0].shiyingdu>zuiyougeti->shiyingdu)
{
for(i=0;i<jiedeweishu;i++)
{
zuiyougeti->geti[i]=chushizhongqunji[0].geti[i];
}
zuiyougeti->shiyingdu=chushizhongqunji[0].shiyingdu;
biaozhi=1;
}
else
{
//cout<<"446"<<endl;/////
biaozhi=0;
}
if(biaozhi==1)//如果寻优成功了就需要确立一个新的部最优解范围
{
chushi*youxiugetiku;
youxiugetiku=newchushi[glpshuliang];
intjishuqi=0;
i=0;
while(chushizhongqunji[i].shiyingdu>zuiyougetijicunqi->shiyingdu)
{
for(intj=0;j<jiedeweishu;j++)
{
youxiugetiku[i].geti[j]=chushizhongqunji[i].geti[j];
}
i++;
}
jishuqi=i;
float*bianjiezancunqi;
bianjiezancunqi=newfloat[jishuqi];
for(i=0;i<jiedeweishu;i++)
{
for(intj=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;
}
voidmubiaohanshu1(chushi&bianliang)//计算shiyingdu
{
inti=0;
intsunshi,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.shiyingdu=yuanmuchang-sunshi-chanpin;
if(bianliang.shiyingdu!=0)//如果不能正好将木料分成所需尺寸则要多切一刀
{
sunshi=qiegesushi*(bianliang.geti[0]+bianliang.geti[1]+bianliang.geti[2]+bianliang.geti[3]);
}
if(bianliang.shiyingdu<0)//罚函数
{
bianliang.shiyingdu=bianliang.shiyingdu+1e5;
}
bianliang.shiyingdu=-bianliang.shiyingdu;
}
intsishewuru(floatx)
{
floaty;
intz;
y=x-(int)x;
if(y<0.5)
{
z=(int)(x);
}
else
{
z=(int)x;
z=z+1;
}
returnz;
}
glp.h源文件贴不下了，把你邮箱给我我发给你
邮箱：hu_hu605@163

⓶哈夫曼编码（贪心算法）

参考：哈夫曼编码

哈夫曼编码是一种十分有效的编码方法，广泛应用于数据压缩中
通过采用不等的编码方式，根据字符频率的不同，选择不同度的编码，对频率越高的字符采用越短的编码实现数据的高度压缩。
这种对频率越高的字符采用越短的编码来编码的方式应用的就是贪心算法的思想。

下面看一个例子：
假如我们有一个包含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’’也应该符合条件，即贪婪算法，每次取最小的两个节点出来这种做法是正确的

⓷找零钱问题的贪心算法

问题描述：
当前有面值分别为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分。
具体实现
//找零钱算法
//Byfalcon
//输入：数组m，依次存放从大到小排列的面值数，n为需要找的钱数，单位全部为分
//输出：数组num，对照数组m中的面值存放不同面值的硬币的个数，即找钱方