贪心算法实例
A. 贪心算法中，通常会让证明贪心选择性，请问，证明贪心选择性的实质是什么怎样说明一个问题具有贪心选择呢
一般都是要最省事的比如
设有n中不同面值的硬币，个硬币的面值春雨数组T[1：n]中，现在要用这些面值的硬币来找钱。可以使用的各种面值的硬币个数存于数组Coins[1:n]中。
对任意签署0<=m<=20001，设计一个用最少硬币找钱m的方法。
用贪心算法，先用最大面值的，直到超出之前再改用更小面值的，超出之前再用更更小面值的。。直到正好。这样最少
程序实例
#include<stdio.h>
void main()
{
int m;
int i;
printf("please input m:");
scanf("%d",&m);
int T[6] ={100,50,20,10,5,1};
int coins[6] = {0};
for(i = 0; i < 6; )
{
if(m < T[i])
{
i++;
continue;
}
while(m >= T[i])
{
m -= T[i];
coins[i]++;
}
i++;
}
for(i = 0; i < 6; i++)
if(coins==0)
printf("%-4d有 %-2d张\n",T[i],coins[i]);
printf("\n");
}
B. 贪婪算法几个经典例子
问题一：贪心算法的例题分析 例题1、[0-1背包问题]有一个背包，背包容量是M=150。有7个物品，物品不可以分割成任意大小。要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。物品 A B C D E F G重量 35kg 30kg 6kg 50kg 40kg 10kg 25kg价值 10$ 40$ 30$ 50$ 35$ 40$ 30$分析：目标函数：∑pi最大约束条件是装入的物品总重量不超过背包容量：∑wi 64输出一个解，返回上一步骤c--（x,y) ← c计算(x,y）的八个方位的子结点，选出那些可行的子结点循环遍历所有可行子结点，步骤c++重复2显然⑵是一个递归调用的过程，大致如下：C++程序： #define N 8void dfs(int x,int y,int count){ int i,tx,ty; if(count>N*N) { output_solution();输出一个解 return; } for(i=0; i>
问题二：收集各类贪心算法（C语言编程）经典题目 tieba./...&tb=on网络的C语言贴吧。 全都是关于C的东西。
问题三：几种经典算法回顾 今天无意中从箱子里发现了大学时学算法的教材《算法设计与分析》，虽然工作这么几年没在什么地方用过算法，但算法的思想还是影响深刻的，可以在系统设计时提供一些思路。大致翻了翻，重温了一下几种几种经典的算法，做一下小结。分治法动态规划贪心算法回溯法分支限界法分治法1）基本思想将一个问题分解为多个规模较小的子问题，这些子问题互相独立并与原问题解决方法相同。递归解这些子问题，然后将这各子问题的解合并得到原问题的解。2）适用问题的特征该问题的规模缩小到一定的程度就可以容易地解决该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题3）关键如何将问题分解为规模较小并且解决方法相同的问题分解的粒度4）步骤分解->递归求解->合并 divide-and-conquer(P) { if ( | P | >
问题四：求三四个贪心算法的例题（配源程序代码，要带说明解释的）！非常感谢 贪心算法的名词解释
ke./view/298415
第一个贪心算法 （最小生成树）
ke./view/288214
第二个贪心算法 （Prim算法）
ke./view/671819
第三个贪心算法 （kruskal算法）
ke./view/247951
算法都有详细解释的
问题五：求 Java 一些经典例子算法 前n项阶乘分之一的和
public class jiecheng {
public static void main(String[] args)
{
double sum=0;
double j=1;
int n=10;
for(int i=1;i 问题六：关于编程的贪心法 定义
所谓贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。 贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。
[编辑本段]贪心算法的基本思路
1.建立数学模型来描述问题。 2.把求解的问题分成若干个子问题。 3.对每一子问题求解，得到子问题的局部最优解。 4.把子问题的解局部最优解合成原来解问题的一个解。 实现该算法的过程： 从问题的某一初始解出发； while 能朝给定总目标前进一步 do 求出可行解的一个解元素； 由所有解元素组合成问题的一个可行解。 下面是一个可以试用贪心算法解的题目，贪心解的确不错，可惜不是最优解。
[编辑本段]例题分析
[背包问题]有一个背包，背包容量是M=150。有7个物品，物品不可以分割成任意大小。 要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。 物品 A B C D E F G 重量 35 30 60 50 40 10 25 价值 10 40 30 50 35 40 30 分析： 目标函数： ∑pi最大 约束条件是装入的物品总重量不超过背包容量：∑wi>
问题七：求解一贪心算法问题 最快回答那个不懂别乱说，别误人子弟。
这题标准的贪心算法，甚至很多时候被当做贪心例题
要求平均等待时间，那么就得用 总等待时间 / 人数
所以只用关心总等待时间，
如果数据大的在前面，那么后面必然都要加一次这个时间，所以按从小到大排。
给你写了个，自己看吧。
#include stdafx.h
#include
#include
#include
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
int n;
float arr[105];
cin >> n;
for(int i = 0; i > arr[i];
sort(arr, arr+n);
int tnow = 0;
int tmax = 0;
for(int i = 0; i 问题八：分治算法的应用实例 下面通过实例加以说明： 给你一个装有1 6个硬币的袋子。1 6个硬币中有一个是伪造的，并且那个伪造的硬币比真的硬币要轻一些。你的任务是找出这个伪造的硬币。为了帮助你完成这一任务，将提供一台可用来比较两组硬币重量的仪器，利用这台仪器，可以知道两组硬币的重量是否相同。比较硬币1与硬币2的重量。假如硬币1比硬币2轻，则硬币1是伪造的；假如硬币2比硬币1轻，则硬币2是伪造的。这样就完成了任务。假如两硬币重量相等，则比较硬币3和硬币4。同样，假如有一个硬币轻一些，则寻找伪币的任务完成。假如两硬币重量相等，则继续比较硬币5和硬币6。按照这种方式，可以最多通过8次比较来判断伪币的存在并找出这一伪币。另外一种方法就是利用分而治之方法。假如把1 6硬币的例子看成一个大的问题。第一步，把这一问题分成两个小问题。随机选择8个硬币作为第一组称为A组，剩下的8个硬币作为第二组称为B组。这样，就把1 6个硬币的问题分成两个8硬币的问题来解决。第二步，判断A和B组中是否有伪币。可以利用仪器来比较A组硬币和B组硬币的重量。假如两组硬币重量相等，则可以判断伪币不存在。假如两组硬币重量不相等，则存在伪币，并且可以判断它位于较轻的那一组硬币中。最后，在第三步中，用第二步的结果得出原先1 6个硬币问题的答案。若仅仅判断硬币是否存在，则第三步非常简单。无论A组还是B组中有伪币，都可以推断这1 6个硬币中存在伪币。因此，仅仅通过一次重量的比较，就可以判断伪币是否存在。假设需要识别出这一伪币。把两个或三个硬币的情况作为不可再分的小问题。注意如果只有一个硬币，那么不能判断出它是否就是伪币。在一个小问题中，通过将一个硬币分别与其他两个硬币比较，最多比较两次就可以找到伪币。这样，1 6硬币的问题就被分为两个8硬币（A组和B组）的问题。通过比较这两组硬币的重量，可以判断伪币是否存在。如果没有伪币，则算法终止。否则，继续划分这两组硬币来寻找伪币。假设B是轻的那一组，因此再把它分成两组，每组有4个硬币。称其中一组为B1，另一组为B2。比较这两组，肯定有一组轻一些。如果B1轻，则伪币在B1中，再将B1又分成两组，每组有两个硬币，称其中一组为B1a，另一组为B1b。比较这两组，可以得到一个较轻的组。由于这个组只有两个硬币，因此不必再细分。比较组中两个硬币的重量，可以立即知道哪一个硬币轻一些。较轻的硬币就是所要找的伪币。 在n个元素中找出最大元素和最小元素。我们可以把这n个元素放在一个数组中，用直接比较法求出。算法如下：void maxmin1(int A[],int n,int *max,int *min){ int i;*min=*max=A[0];for(i=0;i *max) *max= A[i];if(A[i] >
问题九：回溯算法的典型例题 八皇后问题：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。
问题十：什么是算法，都什么，举个例子，谢谢 算法就是解决问题的具体的方法和步骤，所以具有以下性质：
1、有穷性： 一个算法必须保证执行有限步之后结束（如果步骤无限，问题就无法解决）
2、确切性：步骤必须明确，说清楚做什么。
3、输入：即解决问题前我们所掌握的条件。
4、输出：输出即我们需要得到的答案。
5、可行性：逻辑不能错误，步骤必须有限，必须得到结果。
算法通俗的讲：就是解决问题的方法和步骤。在计算机发明之前便已经存在。只不过在计算机发明后，其应用变得更为广泛。通过简单的算法，利用电脑的计算速度，可以让问题变得简单。
C. 用动态规划解决钢条切割问题时它的最优子结构是什么
1、两种重要算法思想： 动态规划，贪心算法
2、动态规划：
基本原理：动态规划英文名dynamic programming。其中pogramming指的是表格法，而非编写计算机程序。因此，可以初步得出动态规划的基本思想：将一个具有最优子结构性质的问题分成若干个子问题，在求解过程中，记录下子问题的结果，存储在一个表格中，使得公共的子问题只需要计算一次。书中给出的基本原理：动态规划将问题分成若干个相互重叠的子问题，递归的求解子问题，保存子问题的解，再将它们的解组合起来，求出原问题的解。
从基本原理中可以看出动态规划需要满足两个条件，最优子结构和子问题重叠。
最优子结构：书中定义：问题的最优解由相关子问题的最优解组合而成，一个问题的最优解包含其子问题的最优解。典型的有背包问题和钢条切割我问题。所谓子问题就是一中组合，将一个问题分成许多子问题的集合。某个子问题转化为问题时，所需要的代价是固定的。
一般这类问题的解题过程：（自己总结）
画出子问题图（类似于逆拓扑排序的图，子问题必须在问题前面完成）
用数学表达式构建出问题的最优解和子问题最优解之间的代数表达式
通常采用自底向上的方法进行递归地求解问题的解，自底下上的含义是从最小的子问题求起。
保存每一步求出的子问题的最优解
利用计算出的信息构造一个最优解
3、贪心算法：
基本原理：从初始状态出发，每步都经过贪心选择，最终得到问题的最优解。
含义： 将每一步都看成是当前最佳的选择，做到局部最优化，直到无法选择为止。寄希望于局部最优的选择能够导致全局最优解。
两个实例：最小生成树算法和单源最短路径算法，以及集合覆盖问题的贪心启发式算法。
prim算法：将集合A看成是一棵树，每次选择剩余的节点中与这棵树形成的边的权值最小的点加入到集合A中形成新的树，循坏调用该过程，知道所有的点都已经放入到集合A中。初始时随机选择一个节点放入到集合A中。
kruskal算法：在所有连接森林中两颗不同树的边里面，找到权重最小的边（u，v），并将其加入到集合A中，循环调用该过程，直到所有的点已经放入到集合A中
贪心选择：当进行选择时，我们直接作在当前问题看来是最优的选择，而不必考虑子问题的解。这与动态规划不同，动态规划当前问题依赖于较小的子问题。而贪心算法中做当前问题最优选择，这样每步之后只需要做一个子问题的解。
也必须满足最优子结构的性质，即一个问题的最优解包含其子问题的最优解。
那么，如何区分什么时候使用动态规划，什么时候使用贪心算法呢？
典型的两个问题，0-1背包和分数背包。两者都具有最优子结构性质，但是贪心算法只能用来求分数背包的问题，而不能用来求0-1背包的问题。即只有分数背包具有贪心选择性。
我得总结（不一定对）：具有贪心选择性的一类问题是：每次做选择时只有性能不同，而代价是一样的。那么这样每次的选择都是最好的，最终会得到最好的结果。
哈夫曼编码也使用贪心选择算法。每次选择待编码的字符都选择在剩余的字符中出现次数最多的
D. 贪心算法
#include <stdio.h>
#define M 100
void main()
{
int i,j,k,temp,m,n;
int t[M]={2,14,4,16,6,5,3},p[M]={1,2,3,4,5,6,7},s[M],d[M]={0};
m=3;n=7;
for(i=0;i<7;i++)
for(j=0;j<7-i;j++)
if(t[j]<t[j+1])
{
temp=t[j];
t[j]=t[j+1];
t[j+1]=temp;
temp=p[j];
p[j]=p[j+1];
p[j+1]=temp;
}
for(i=0;i<m;i++) //求时间。
{
s[i]=p[i];
d[i]=t[i];
}
for(k=0;k<m;k++)
printf(" %d",d[k]);
printf("\n");
for(i=m;i<n;i++)
{
for(k=0;k<m-1;k++) //求最小。
{
temp=d[k];
if(temp>d[k+1])
{temp=d[k+1];j=k+1;}
}
printf("这是最小下标的： %d\n",j);
printf("最小的值： %d\n",temp);
for(k=0;k<m;k++)
printf(" %d",d[k]);
printf("\n");
//j=temp;
s[j]=s[j]+p[i];
d[j]=d[j]+t[i];
}
printf("\n");
for(k=0;k<7;k++)
printf(" %d",t[k]);
printf("\n");
for(k=0;k<7;k++)
printf(" %d",p[k]);
printf("\n");
for(k=0;k<m;k++)
printf(" %d",s[k]);
printf("\n");
for(k=0;k<m;k++)
printf(" %d",d[k]);
printf("\n");
}
E. 求背包问题贪心算法实例结果
找零钱问题：以人民币1元，2元，5元，10元，20元，50元，100元为例，要求所找的张数最少
背包问题：假设物体重量W1，W2．．．Wn其对应的价值为P1，P2．．．Pn，物体可分割，求装入重量限制为m的背包中的物体价值最大．可用P/W来解答．
#include<iostream>
#include<algorithm>
using namespace std;
struct good//表示物品的结构体
{
double p;//价值
double w;//重量
double r;//价值与重量的比
}a[2000];
double s,value,m;
int i,n;
bool bigger(good a,good b)
{
return a.r>b.r;
}
int main()
{
scanf("%d",&n);//物品个数
for (i=0;i<n;i++)
{
scanf("%lf%lf",&a[i].w,&a[i].p);
a[i].r=a[i].p/a[i].w;
}
sort(a,a+n,bigger);//调用sort排序函数，你大概不介意吧，按照价值与重量比排序贪心
scanf("%lf",&m);//读入包的容量m
s=0;//包内现存货品的重量
value=0;//包内现存货品总价值
for (i=0;i<n&&s+a[i].w<=m;i++)
{
value+=a[i].p;
s+=a[i].w;
}
printf("The total value in the bag is %.2lf.\n",value);//输出结果
return 0;
}
F. 贪心算法几个经典例子
[背包问题]有一个背包，背包容量是M=150。有7个物品，物品可以分割成任意大小。
要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。
贪心算法是很常见的算法之一，这是由于它简单易行，构造贪心策略简单。但是，它需要证明后才能真正运用到题目的算法中。一般来说，贪心算法的证明围绕着整个问题的最优解一定由在贪心策略中存在的子问题的最优解得来的。
对于本例题中的3种贪心策略，都无法成立，即无法被证明。
G. 求解一道贪心算法
因为这个问题涉及到高维求解（大于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]