参数说明
n：物品个数
m：种群大小
W：背包容量
其中 a[i] 存储的物品信息 ，g[i]存储基因信息。
maxn ：物品数的最大值
maxm ：种群数的最大值
注意事项
m 最好是 n 的10倍及其以上，毕竟基因状态数高达 1<<n 种，m 太小的话初始种群如果都不满足 容量之和小于 W 的话，整个种群可能会消失。所以尽量设大一点。
代码
#include<bits/stdc++.h>using namespace std;#define maxn 105#define maxm 1006#define ll long long int#define INF 0x3f3f3f3f#define inc(i,l,r) for(int i=l;i<=r;i++)#define dec(i,r,l) for(int i=r;i>=l;i--)#define mem(a) memset(a,0,sizeof(a))#define sqr(x) (x*x)#define inf (ll)2e18+1#define PI acos(-1)#define mod 10007#define db double#define auto(i,x) for(int i=head[x];i;i=ed[i].nxt)ll read(){ll x=0,f=1ll;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();return f*x;}int n,m,W;db xiaorand(db low,db up,db jin){db down=min(0.0,low);low-=down,up-=down;int l=(int)low*jin,r=(int)up*jin;int len=r-l+1;int num=rand()%len + l;return 1.0*num/jin + down;}struct node{int w,v;}a[maxn];struct gen{bitset<maxn>dna;int pos;bool operator < (const gen &rid)const{return pos > rid.pos;}}g[maxm];void init_population(int x){inc(i,1,x)inc(j,1,n)g[i].dna[j]=rand()%2;}int f(gen x){ll sumv=0,sumw=0;inc(i,1,n)if(x.dna[i]){sumv+=a[i].v,sumw+=a[i].w;}return sumw <= W ? sumv : -INF;}void choose(db sum,int len,int num,int bian,int id){db posi=xiaorand(0,1,1000);int x=0,y=0;inc(i,1,len){posi-=1.0*g[i].pos/sum;if(posi<=0){x=i;break; }}posi=xiaorand(0,1,1000);inc(i,1,len){posi-=1.0*g[i].pos/sum;if(posi<=0){y=i;break; }}gen now=g[x];inc(i,1,n){if(rand()%2==1){now.dna[i]=g[y].dna[i];num--;}if(num==0)break;}inc(i,1,n){if(rand()%2==1){now.dna[i]=now.dna[i]^1;bian--;}if(bian==0)break;}g[id]=now;}void kill_and_evaluate(int x){inc(i,1,m)g[i].pos=f(g[i]);sort(g+1,g+m+1);int ccc=m;while(g[ccc].pos==-INF)ccc--;x=max(x,m-ccc);int len=m-x;inc(i,1,len)swap(g[i],g[(rand()%i)+1]);db sum=0;inc(i,1,len)sum+=1.0*g[i].pos;inc(i,len+1,m)choose(sum,len,m/2,(m/10)+1,i);}int main(){n=read();m=read();W=read();inc(i,1,n)a[i].w=read(),a[i].v=read();init_population(m);inc(i,1,100){kill_and_evaluate((m/5)+1);int ma=0;inc(j,1,m)ma=max(ma,f(g[j]));printf("%d : %d\n",i,ma);}return 0;}/*12 50 252 52 54 810 22 35 73 68 64 76 63 32 1*/
如果觉得《遗传算法之01背包问题 （C语言实现）》对你有帮助，请点赞、收藏，并留下你的观点哦！
