Question

求解一道贪心算法

Answer 1

因为这个问题涉及到高维求解（大于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 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;

//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)<<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->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");

}

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