贪心是人类自带的能力，贪心算法是在贪心决策上进行统筹规划的统称。
比如一道常见的算法笔试题---- 跳一跳 ：
我们自然而然能产生一种解法：尽可能的往右跳，看最后是否能到达。
本文即是对这种贪心决策的介绍。
狭义的贪心算法指的是解最优化问题的一种特殊方法，解决过程中总是做出当下最好的选择，因为具有最优子结构的特点，局部最优解可以得到全局最优解；这种贪心算法是动态规划的一种特例。 能用贪心解决的问题，也可以用动态规划解决。
而广义的贪心指的是一种通用的贪心策略，基于当前局面而进行贪心决策。以 跳一跳 的题目为例：
我们发现的题目的核心在于 向右能到达的最远距离 ，我们用maxRight来表示；
此时有一种贪心的策略：从第1个盒子开始向右遍历，对于每个经过的盒子，不断更新maxRight的值。
贪心的思考过程类似动态规划，依旧是两步： 大事化小 ， 小事化了 。
大事化小：
一个较大的问题，通过找到与子问题的重叠，把复杂的问题划分为多个小问题；
小事化了：
从小问题找到决策的核心，确定一种得到最优解的策略，比如跳一跳中的 向右能到达的最远距离 ；
在证明局部的最优解是否可以推出全局最优解的时候，常会用到数学的证明方式。
如果是动态规划：
要凑出m元，必须先凑出m-1、m-2、m-5、m-10元，我们用dp[i]表示凑出i元的最少纸币数；
有 dp[i]=min(dp[i-1], dp[i-2], dp[i-5], dp[i-10]) + 1
容易知道 dp[1]=dp[2]=dp[5]=dp[10]=1 ；
根据以上递推方程和初始化信息，可以容易推出dp[1~m]的所有值。
似乎有些不对？ 平时我们找零钱有这么复杂吗？
从贪心算法角度出发，当m>10且我们有10元纸币，我们优先使用10元纸币，然后再是5元、2元、1元纸币。
从日常生活的经验知道，这么做是正确的，但是为什么？
假如我们把题目变成这样，原来的策略还能生效吗？
接下来我们来分析这种策略：
已知对于m元纸币，1，2，5元纸币使用了a，b，c张，我们有a+2b+5c=m；
假设存在一种情况，1、2、5元纸币使用数是x，y，z张，使用了更少的5元纸币（z<c），且纸币张数更少（x+y+z<a+b+c），即是用更少5元纸币得到最优解。
我们令k=5*(c-z)，k元纸币需要floor(k/2)张2元纸币，k%2张1元纸币；（因为如果有2张1元纸币，可以使用1张2元纸币来替代，故而1元纸币只能是0张或者1张）
容易知道，减少(c-z)张5元纸币，需要增加floor(5*(c-z)/2)张2元纸币和(5*(c-z))%2张纸币，而这使得x+y+z必然大于a+b+c。
由此我们知道不可能存在使用更少5元纸币的更优解。
所以优先使用大额纸币是一种正确的贪心选择。
对于1、5、7元纸币，比如说要凑出10元，如果优先使用7元纸币，则张数是4；（1+1+1+7）
但如果只使用5元纸币，则张数是2；（5+5）
在这种情况下，优先使用大额纸币是不正确的贪心选择。（但用动态规划仍能得到最优解）
如果是动态规划：
前i秒的完成的任务数，可以由前面1~i-1秒的任务完成数推过来。
我们用 dp[i]表示前i秒能完成的任务数 ；
在计算前i秒能完成的任务数时，对于第j个任务，我们有两种决策：
1、不执行这个任务，那么dp[i]没有变化；
2、执行这个任务，那么必须腾出来(Sj, Tj)这段时间，那么 dp[i] = max(dp[i], dp[ S[j] ] ) + 1 ；
比如说对于任务j如果是第5秒开始第10秒结束，如果i>=10，那么有 dp[i]=max(dp[i], dp[5] + 1)； （相当于把第5秒到第i秒的时间分配给任务j）
再考虑贪心的策略，现实生活中人们是如何安排这种多任务的事情？我换一种描述方式：
我们自然而然会想到一个策略： 先把结束时间早的兼职给做了！
为什么？
因为先做完这个结束时间早的，能留出更多的时间做其他兼职。
我们天生具备了这种优化决策的能力。
这是一道 LeetCode题目 。
这个题目不能直接用动态规划去解，比如用dp[i]表示前i个人需要的最少糖果数。
因为（前i个人的最少糖果数）这种状态表示会收到第i+1个人的影响，如果a[i]>a[i+1]，那么第i个人应该比第i+1个人多。
即是 这种状态表示不具备无后效性。
如果是我们分配糖果，我们应该怎么分配？
答案是： 从分数最低的开始。
按照分数排序，从最低开始分，每次判断是否比左右的分数高。
假设每个人分c[i]个糖果，那么对于第i个人有 c[i]=max(c[i-1],c[c+1])+1 （c[i]默认为0，如果在计算i的时候,c[i-1]为0，表示i-1的分数比i高）
但是，这样解决的时间复杂度为 O(NLogN) ，主要瓶颈是在排序。
如果提交，会得到 Time Limit Exceeded 的提示。
我们需要对贪心的策略进行优化：
我们把左右两种情况分开看。
如果只考虑比左边的人分数高时，容易得到策略：
从左到右遍历，如果a[i]>a[i-1]，则有c[i]=c[i-1]+1；否则c[i]=1。
再考虑比右边的人分数高时，此时我们要从数组的最右边，向左开始遍历：
如果a[i]>a[i+1], 则有c[i]=c[i+1]+1；否则c[i]不变；
这样讲过两次遍历，我们可以得到一个分配方案，并且时间复杂度是 O(N) 。
题目给出关键信息：1、两个人过河，耗时为较长的时间；
还有隐藏的信息：2、两个人过河后，需要有一个人把船开回去；
要保证总时间尽可能小，这里有两个关键原则： 应该使得两个人时间差尽可能小（减少浪费），同时船回去的时间也尽可能小（减少等待）。
先不考虑空船回来的情况，如果有无限多的船，那么应该怎么分配？
答案： 每次从剩下的人选择耗时最长的人，再选择与他耗时最接近的人。
再考虑只有一条船的情况，假设有A/B/C三个人，并且耗时A<B<C。
那么最快的方案是：A+B去, A回；A+C去；总耗时是A+B+C。（因为A是最快的，让其他人来回时间只会更长， 减少等待的原则 ）
如果有A/B/C/D四个人，且耗时A<B<C<D，这时有两种方案：
1、最快的来回送人方式，A+B去；A回；A+C去，A回；A+D去； 总耗时是B+C+D+2A （减少等待原则）
2、最快和次快一起送人方式，A+B先去，A回；C+D去，B回；A+B去；总耗时是 3B+D+A （减少浪费原则）
对比方案1、2的选择，我们发现差别仅在A+C和2B；
为何方案1、2差别里没有D？
因为D最终一定要过河，且耗时一定为D。
如果有A/B/C/D/E 5个人，且耗时A<B<C<D<E，这时如何抉择？
仍是从最慢的E看。（参考我们无限多船的情况）
方案1，减少等待；先送E过去，然后接着考虑四个人的情况；
方案2，减少浪费；先送E/D过去，然后接着考虑A/B/C三个人的情况；（4人的时候的方案2）
到5个人的时候，我们已经明显发了一个特点：问题是重复，且可以由子问题去解决。
根据5个人的情况，我们可以推出状态转移方程 dp[i] = min(dp[i - 1] + a[i] + a[1], dp[i - 2] + a[2] + a[1] + a[i] + a[2])
再根据我们考虑的1、2、3、4个人的情况，我们分别可以算出dp[i]的初始化值：
dp[1] = a[1]
dp[2] = a[2]
dp[3] = a[2]+a[1]+a[3]
dp[4] = min(dp[3] + a[4] + a[1], dp[2]+a[2]+a[1]+a[4]+a[2])
由上述的状态转移方程和初始化值，我们可以推出dp[n]的值。
贪心的学习过程，就是对自己的思考进行优化。
是把握已有信息，进行最优化决策。
这里还有一些收集的 贪心练习题 ，可以实践练习。
这里 还有在线分享，欢迎报名。
因为这个问题涉及到高维求解（大于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=0i<jiedeweishui++)
{
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=0i<jiedeweishui++)
{
bianjiebianhuashuzu[i]=chicunxuqiuliang[i]-yiwanchengshuliang[i]
}
for(i=0i<jiedeweishui++)
{
zuobianjie0[i]=0
if(bianjiebianhuashuzu[i]>(int)(yuanmuchang/xuqiuchicun[i]))
{
youbianjie0[i]=(int)(yuanmuchang/xuqiuchicun[i])
}
else
{
youbianjie0[i]=bianjiebianhuashuzu[i]
}
}
for(i=0i<jiedeweishui++)
{
zuobianjie[i]=zuobianjie0[i]
youbianjie[i]=youbianjie0[i]
}
for(i=0i<jiedeweishui++)//在这套程序中边界分为两个部分,其中一组是根据最优解的收敛范围进行局部寻优,如果在局部找不到最优解则以现有最优解为中心进行全局搜索
{
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=0i<jiedeweishui++)/////
//{////
// cout<<zuiyougeti->geti[i]<<","////
//}/////////
//cout<<endl/////
// cout<<"初始最优解："<<" "<<-zuiyougeti->shiyingdu<<endl/////////////
for(gen=1gen<maxgengen++)
{
jingyingbaoliu()
if(chazhi<1e-1)
break
}
//cout<<"最终在收敛的范围内左右边界的最大差值: "<<chazhi<<endl
//for(i=0i<jiedeweishui++)
//{
// 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=0i<jiedeweishui++)
{
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=0i<jiedeweishui++)
{
zuobianjie1[i]=zuobianjie[i]
youbianjie1[i]=youbianjie[i]
}
float **glp_shu_zu//第一次求解，为了使解更精确这一次求解需要的点最多
glp_shu_zu=new (float *[glpgeshu])
for(i=0i<glpgeshui++)
{
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=0i<glpgeshui++)//产生初始种群
{
for(j=0j<jiedeweishuj++)
{
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=0i<glpgeshui++)//计算初始种群的适应度
{
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=0j<jiedeweishuj++)
{
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=0i<jiedeweishui++)
{
for(int j=0j<jishuqij++)
{
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=0i<jiedeweishui++)
{
zuiyougeti->geti[i]=chushizhongqunji[0].geti[i]
}
zuiyougeti->shiyingdu=chushizhongqunji[0].shiyingdu
biaozhi=1
}
delete [] bianjiezancunqi
delete [] youxiugetiku
for(i=0i<glpgeshui++)
{
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=0i<jiedeweishui++)
{
xiangliang[i]=sheng_cheng_xiang_liang1[i]
}
}
else//否则利用全局搜索的数据
{
glpshuliang=glpgeshu2
for(int i=0i<jiedeweishui++)
{
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=0i<glpshuliangi++)
{
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=0i<jiedeweishui++)
{
bianjiecha[i]=youbianjie3[i]-zuobianjie3[i]//计算上一代全局每一维范围的宽度
}
static float rou=0.9//定义收缩比
//float rou=pow(0.5,gen)
for(i=0i<jiedeweishui++)//确定新的范围
{
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=0i<glpshuliangi++)//根据新产生的最优个体确定glp群
{
for(j=0j<jiedeweishuj++)
{
chushizhongqunji[i].geti[j]=sishewuru((zuobianjie[j]+(youbianjie[j]-(zuobianjie[j]))*glp_shu_zu[i][j]))
}
}
for(i=0i<glpshuliangi++)
{
mubiaohanshu1(chushizhongqunji[i])
}
qsort(chushizhongqunji,glpshuliang,sizeof(chushi),&cmpshiyingdujiang)
zuiyougetijicunqi->shiyingdu=zuiyougeti->shiyingdu
if(chushizhongqunji[0].shiyingdu>zuiyougeti->shiyingdu)
{
for(i=0i<jiedeweishui++)
{
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=0j<jiedeweishuj++)
{
youxiugetiku[i].geti[j]=chushizhongqunji[i].geti[j]
}
i++
}
jishuqi=i
float *bianjiezancunqi
bianjiezancunqi=new float[jishuqi]
for(i=0i<jiedeweishui++)
{
for(int j=0j<jishuqij++)
{
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=0i<glpshuliangi++)
{
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源文件贴不下了，把你邮箱给我我发给你
思路：对于一个整数n，无论分成多少个数的和，都是这些数相同或相差最少的时候，它们的积才最大。如，对于数 4, 2 * 2最大；对于9，分成三个数3 * 3 * 3最大，分成两个数4 * 5最大。。。数学里可以证明。然后分治法就行了
1,2,3这三个数不可分，本身最大，遇到它们直接返回就行了，其它数分完递归调用。
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）