(三) 贪心算法
2024-05-04 06:52
1. (三) 贪心算法
贪心算法的思想非常简单且算法效率很高，在一些问题的解决上有着明显的优势。
假设有3种硬币，面值分别为1元、5角、1角。这3种硬币各自的数量不限，现在要找给顾客3元6角钱，请问怎样找才能使得找给顾客的硬币数量最少呢？
你也许会不假思索的说出答案：找给顾客3枚1元硬币，1枚5角硬币，1枚1角硬币。其实也可以找给顾客7枚5角硬币，1枚1角硬币。可是在这里不符合题意。在这里，我们下意识地应用了所谓贪心算法解决这个问题。
所谓贪心算法，就是 总是做出在当前看来是最好的选择(未从整体考虑) 的一种方法。以上述的题目为例，为了找给顾客的硬币数量最少，在选择硬币的面值时，当然是尽可能地选择面值大的硬币。因此，下意识地遵循了以下方案： （1）首先找出一个面值不超过3元6角的最大硬币，即1元硬币。 （2）然后从3元6角中减去1元，得到2元6角，再找出一个面值不超过2元6角的最大硬币，即1元硬币。 （3）然后从2元6角中减去1元，得到1元6角，再找出一个面值不超过1元6角的最大硬币，即1元硬币。 （4）然后从1元6角中减去1元，得到6角，再找出一个面值不超过6角的最大硬币，即5角硬币。 （5）然后从6角中减去5角，得到1角，再找出一个面值不超过1角的最大硬币，即1角硬币。 （6）找零钱的过程结束。 这个过程就是一个典型的贪心算法思想。
贪心策略总是做出在当前看来是最优的选择，也就是说贪心策略并不是从整体上加以考虑，它所做出的选择只是在某种意义上的 局部最优解 ，而许多问题自身的特性决定了该问题运用贪心策略可以得到最优解或较优解。(注：贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题它能产生整体最优解。但其解必然是最优解的很好近似解。）
贪心算法没有固定的算法框架，算法设计的关键是 贪心策略的选择 。选择的贪心策略必须具备无后效性。
贪心策略 适用的前提 是：
严格意义上讲，要使用贪心算法求解问题，该问题应当具备以下性质：
注意 ：对于一个给定的问题，往往可能有好几种量度标准。初看起来，这些量度标准似乎都是可取的，但实际上，用其中的大多数量度标准作贪婪处理所得到该量度意义下的最优解并不是问题的最优解，而是次优解。
因此， 选择能产生问题最优解的最优量度标准是使用贪婪算法的核心 。
实际上，贪心算法 适用的情况很少 。一般，对一个问题分析是否适用于贪心算法，可以先选择该问题下的几个实际数据进行分析，就可做出判断。
最优解问题大部分都可以拆分成一个个的子问题(多阶段决策问题)，把解空间的遍历视作对子问题树的遍历，则以某种形式对树整个的遍历一遍就可以求出最优解，大部分情况下这是不可行的。
贪心算法和动态规划本质上是对子问题树的一种修剪，两种算法要求问题都具有的一个性质就是子问题最优性(组成最优解的每一个子问题的解，对于这个子问题本身肯定也是最优的)。
动态规划方法代表了这一类问题的一般解法， 自底向上 构造子问题的解，对每一个子树的根，求出下面每一个叶子的值，并且以其中的最优值作为自身的值，其它的值舍弃。
而贪心算法是动态规划方法的一个特例，可以证明每一个子树的根的值不取决于下面叶子的值，而只取决于当前问题的状况。换句话说，不需要知道一个节点所有子树的情况，就可以求出这个节点的值。由于贪心算法的这个特性，它对解空间树的遍历不需要自底向上，而只需要自根开始( 自顶向下 )，选择最优的路，一直走到底就可以了。
一个问题分为多个阶段，每个阶段可以有n种决策，各个阶段的决策构成一个决策序列，称为一个策略。 这两种算法都是选择性算法，在进行决策的选择时：
前提是这个问题得具有贪心选择性质，需要证明(数学归纳法(第一、第二))，如果不满足那就只能使用动态规划解决。(一旦证明贪心选择性质，用贪心算法解决问题比动态规划具有更低的时间复杂度和空间复杂度。)
从范畴上来看： Greedy ⊂ DP ⊂ Searching （贪心是动规的特例） 即所有的贪心算法问题都能用DP求解，更可以归结为一个搜索问题，反之不成立。
贪心算法所作的选择可以依赖于以往所作过的选择，但决不依赖于将来的选择，也不依赖于子问题的解，这使得算法在编码和执行的过程中都有着一定的速度优势。如果一个问题可以同时用几种方法解决，贪心算法应该是最好的选择之一。但是贪心算法并不是对所有的问题都能得到整体最优解或最理想的近似解，与回溯法等比较，它的适用区域相对狭窄许多，因此正确地判断它的应用时机十分重要。
一步一步地进行，常 以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况 ，它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。
它采用 自顶向下 ，以 迭代 的方法做出相继的贪心选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问题，通过每一步贪心选择，可得到问题的一个最优解，虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以 贪心法不需要回溯 。
【问题描述】 马的遍历问题。在8×8方格的棋盘上，从任意指定方格出发，为马寻找一条走遍棋盘每一格并且只经过一次的一条最短路径。
【贪心算法】 其实马踏棋盘的问题很早就有人提出，且早在1823年，J.C.Warnsdorff就提出了一个有名的算法。在每个结点对其子结点进行选取时，优先选择‘出口’最小的进行搜索，‘出口’的意思是在这些子结点中它们的可行子结点的个数，也就是‘孙子’结点越少的越优先跳，为什么要这样选取，这是一种局部调整最优的做法，如果优先选择出口多的子结点，那出口少的子结点就会越来越多，很可能出现‘死’结点（顾名思义就是没有出口又没有跳过的结点），这样对下面的搜索纯粹是徒劳，这样会浪费很多无用的时间，反过来如果每次都优先选择出口少的结点跳，那出口少的结点就会越来越少，这样跳成功的机会就更大一些。
2. 贪心算法
平面点集三角剖分的贪心算法要求三角剖分后边的总长度尽可能小。算法的基本思想是将所有的两点间距离从小到大排序，依次序每次取一条三角剖分的边，直至达到要求的边数。以下是两种贪心算法的主要步骤。
3.2.2.1 贪心算法1
第一步:设置一个记录三角剖分中边的数组T。
第二步:计算点集S中所有点对之间的距离d(pi，pj)，1≤i，j≤n，i≠j，并且对距离从小到大进行排序，设为d1，d2，…，dn(n-1)/2，相应的线段记为e1，e2，…，en(n-1)/2，将这些线段存储在数组E中。
第三步:从线段集E中取出长度最短的边e1存到T中作为三角剖分的第一条边，此时k=1。
第四步:依次从E中取出长度最短的边ek，与T中已有的边进行求交运算，如果不相交则存到T中，并从E中删除ek。这一步运行到S中没有边为止，即至k=n(n-1)/2。
第五步:输出T。
该算法中，第二步需要计算n(n-1)/2次距离，另外距离排序需要O(n2lgn)次比较。T中元素随第四步循环次数的增加而增加，因此向T中加入一条新边所需要的判定两条线段是否相交的次数也随之增加。如果第四步的前3n-6次循环后已经构成点集的三角剖分，那么第四步循环所需要的判定两条线段是否相交的次数为
1+2+…+3n-7+(3n-6)×(n(n-1)/2-(3n-6))=O(n3)
在常数时间内可以判定两条线段是否相交，因此该算法的时间复杂性为O(n3)。
3.2.2.2 贪心算法2
第一步:求点集的凸壳，设凸壳顶点为p1，p2，…，pm，凸壳的边为e1，e2，…，em。并将凸壳顶点按顺序连接成边的ei加入T(三角剖分的边集合)，并且ei的权值被赋为1。凸壳内点的集合为S1={pm+1，pm+2，…，pn}。
第二步:从内部点S1中任取一点pi，求与pi距离最近的点pj，将线段 存入T。
第三步:求与pj距离最近的点(除点pi外)，设为pk，并将线段 存入T，pipjpk构成一个三角形，并将三条边wij、wjk和wki的权值设为1。
第四步:分别求与pi、pj和pk距离最近的点(除点pi、pj和pk本身外)，设为p'i，p'j，p'k，将 加入T，并将这些边的权值设为1，而wij、wjk和wki的值加1，即为2。边的权值为2则表示该边为两个三角形共有。
第五步:对权值为1的边(除e1，e2，…，em外)的两个端点分别求与其距离最近的点，并将其连线(得到新的三角形)加入T，新三角形边的权值加1。
第六步:对权值为1的边重复上一步，当一条边被使用一次其权值增加1，直到所有边的权值均为2为止(除e1，e2，…，em外)。
贪心算法2中，第一步耗费O(nlgn);第二步需要计算n-1次距离与n-2次比较;第三步求pk要计算n-2次的距离与n-3次比较;第四步要进行(n-3)×3次的距离计算及(n-4)×3次比较;第五步至多进行n-6次的距离计算与n-7次比较;第六步到第五步的循环次数不超过3n-9;因此整个贪心算法2的时间复杂性为
O(nlgn)+O(n)+O(n)+O(n)+(n-6)×(3n-9)=O(n2)
3. 求解一道贪心算法
因为这个问题涉及到高维求解（大于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
#include
#include
#include
#include
#include
#include
#include
#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 shiyingdu;
};
chushi *zuiyougeti;//精英保存策略
chushi *zuiyougetijicunqi;
int sishewuru(float);
float chazhi;//左右边界的差
int biaozhi;//判断寻优是否成功1表示成功0表示不成功
int maxgen;//最大计算代数
int gen;//目前代数
void initialize;//算法初始化
void jingyingbaoliu;//精英保存的实现
void mubiaohanshu1(chushi &bianliang);//适应度的计算使用残差法
int cmpshiyingdujiang(const void *p1,const void *p2)
{
float i=((chushi *)p1)->shiyingdu;
float j=((chushi *)p2)->shiyingdu;
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;//都加工完了就退出程序
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;
//coutshiyingdu<<endl;
initialize;
//for(i=0;i<jiedeweishu;i++)/////
//{////
// coutgeti[i]<<",";////
//}/////////
//cout<<endl;/////
// coutshiyingdu<<endl;/////////////
for(gen=1;gen<maxgen;gen++)
{
jingyingbaoliu;
if(chazhi<1e-1)
break;
}
//cout<<"最终在收敛的范围内左右边界的最大差值: "<<chazhi<<endl;
//for(i=0;i<jiedeweishu;i++)
//{
// coutgeti[i]<<",";
// }
//cout<<endl;
//cout<<"共用代数"<<gen<<endl;
coutgeti[0]<<"根"<<endl;
coutgeti[1]<<"根"<<endl;
coutgeti[2]<<"根"<<endl;
coutgeti[3]<<"根"<<endl;
coutshiyingdu)<<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;//起始代
chazhi=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),&cmpshiyingdujiang);//根据适应度将初始种群集按降序进行排列
chushi *youxiugetiku;//建立一个储存优秀个体的库
youxiugetiku=new chushi[glpgeshu];//建立一个储存优秀个体的库
int jishuqi=0;
i=0;
while(chushizhongqunji[i].shiyingdu>zuiyougeti->shiyingdu)//凡是比上一代的最优个体还要好的个体都放入优秀个体库
{
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].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;
}
void jingyingbaoliu //精英保留的实现
{
float glpshuliang,xiangliang[jiedeweishu];
if(biaozhi==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(biaozhi!=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(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=new chushi[glpshuliang];
int jishuqi=0;
i=0;
while(chushizhongqunji[i].shiyingdu>zuiyougetijicunqi->shiyingdu)
{
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)//计算shiyingdu
{
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.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;
}
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源文件贴不下了，把你邮箱给我我发给你
邮箱：hu_hu605@163
4. 贪心算法
在某一个标准下，优先考虑做满足标准的样本，最后考虑最不满足标准的样本，最终得到一个答案的算法，叫做贪心算法。
即，不从整体最优上加以考虑，所做出的是在某种意义上的局部最优解。
局部最优 -?-> 整体最优
一些项目要占用一个会议室宣讲，会议室不能同时容纳两个项目的宣讲。 给你每一个项目开始的时间和结束的时间(给你一个数 组，里面是一个个具体 的项目)，你来安排宣讲的日程，要求会议室进行的宣讲的场次最多。 返回这个最多的宣讲场次。
一块金条切成两半，是需要花费和长度数值一样的铜板的。比如长度为20的金 条，不管切成长度多大的两半，都要花费20个铜板。
一群人想整分整块金条，怎么分最省铜板? 例如,给定数组{10,20,30}，代表一共三个人，整块金条长度为10+20+30=60。 金条要分成10,20,30三个部分。 如果先把长度60的金条分成10和50，花费60； 再把长度50的金条分成20和30，花费50；一共花费110铜板。 但是如果先把长度60的金条分成30和30，花费60；再把长度30金条分成10和20， 花费30；一共花费90铜板。
输入一个数组，返回分割的最小代价。
输入：
正数数组costs
正数数组profits
正数k
正数m
含义： costs[i]表示i号项目的花费
profits[i]表示i号项目在扣除花费之后还能挣到的钱(利润)
k表示你只能串行的最多做k个项目
m表示你初始的资金
说明：
你每做完一个项目，马上获得的收益，可以支持你去做下一个项目。
输出： 你最后获得的最大钱数。
5. 贪心算法及其应用
求解一个问题时有多个步骤，每个步骤都选择当下最优的那个解，而不用考虑整体的最优解。通常，当我们面对的问题拥有以下特点的时候，就可以考虑使用贪心算法。
比如，我们举个例子，仓库里面总共有五种豆子，其对应的重量和总价值如下，现在我们有一个可以装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]，期望值就是尽可能多的区间。
我们的解决办法就是每次从区间中选择那种左端点>=已经覆盖区间右边端点的，且该区间右端点尽可能高小的。如此，我们可以让未覆盖区间尽可能地大，才能保证可以塞进去尽可能多的区间。
贪心算法最重要的就是学会如何将要解决的问题抽象成适合贪心算法特点的模型，找到限制条件和期望值，只要做好这一步，接下来的就比较简单了。在平时我们不用刻意去记，多多练习类似的问题才是最有效的学习方法。
6. 贪心算法的介绍
贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。
7. 贪心算法的特性
8. 贪心算法是什么
贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。 比如最小生成树Kruskal算法，每次在不构成环的前提下，总是选择权最小的边。
最新文章
热门文章
推荐阅读