#include<bits/stdc++.h> using namespace std; const int maxn=5005; double S; int n; double v[maxn]; double w[maxn]; const unsigned int inf=~0U; typedef unsigned int U; U SX=335634763,SY=873658265,SZ=192849106,SW=746126501; U xorshift128(){ //快速随机数生成器 U tt=SX^(SX<<11); SX=SY; SY=SZ; SZ=SW; return SW=SW^(SW>>19)^tt^(tt>>8); } struct Genetic_algorithm { struct chromesome { vector<int> id;//一个01序列,表示状态,第i位为0表示不选取第i个物品,第i位为1表示选取 double weight;//表示选择算子(权重),权重越大,被选中的概率越大 double sop;//表示被选中的概率 double st,ed;//在轮盘赌算法中占据的位置,st表示起点,ed表示终点 chromesome () { } bool operator < (const chromesome &r) const { return weight>r.weight;//排序规则,只保留适应度较大的 } }; vector<chromesome> chr_list;//一个包含当前种群的列表 double cal_weight (vector<int> id) { double weight=0;//定义总权重 double sum=0;//定义当前体积 for (int i=0;i<id.size();i++) { if (id[i]==0) continue; sum+=v[i]; weight+=w[i]; } //printf("%lf ",sum); if (sum>S) return 0;//如果超出背包容量,直接返回0 return weight; } void cal_sop () { double sum=0; for (int i=0;i<chr_list.size();i++) chr_list[i].weight=cal_weight(chr_list[i].id); for (int i=0;i<chr_list.size();i++) chr_list[i].sop=chr_list[i].weight/sum; double cc=0; for (int i=0;i<chr_list.size();i++) { chr_list[i].st=cc; chr_list[i].ed=cc+chr_list[i].sop-0.000001;//计算被选中的区间 } } chromesome cross (vector<chromesome> chr_list) { chromesome ans; chromesome t1=chr_list[0],t2=chr_list[0]; double x=xorshift128()*1.0/1000000000; for (int i=0;i<chr_list.size();i++) { if (x>=chr_list[i].st&&x<=chr_list[i].ed) { t1=chr_list[i]; break; } } double y=xorshift128()*1.0/1000000000; for (int i=0;i<chr_list.size();i++) { if (y>=chr_list[i].st&&y<=chr_list[i].ed) { t2=chr_list[i]; break; } } int p=xorshift128()%n;//随机生成一个交叉位置 for (int i=0;i<p;i++) ans.id.push_back(t1.id[i]); for (int i=p;i<t1.id.size();i++) ans.id.push_back(t2.id[i]); return ans; } chromesome variation (chromesome x) { vector<int> p; for (int i=0;i<5;i++) p.push_back(xorshift128()%n); for (int i=0;i<p.size();i++) { if (x.id[p[i]]==1) continue; x.id[p[i]]=1;//往好的方向变异 } return x; } vector<chromesome> diedai () { vector<chromesome> ans=chr_list; for (int i=0;i<200;i++) ans.push_back(cross(chr_list)); for (int i=0;i<chr_list.size();i++) ans.push_back(variation(chr_list[i])); sort(ans.begin(),ans.end()); int len=ans.size(); for (int i=0;i<len-200;i++) ans.pop_back(); return ans; } void init () { //随机生成200个01串进入序列 for (int i=0;i<200;i++) { chromesome tt; for (int j=0;j<n;j++) tt.id.push_back(xorshift128()%2); chr_list.push_back(tt); } } void start () { init(); for (int i=0;i<200;i++) { cal_sop(); chr_list=diedai(); } } }; int main () { scanf("%lf%d",&S,&n); for (int i=0;i<n;i++) scanf("%lf%lf",v+i,w+i); Genetic_algorithm zlc; zlc.start(); // for (int i=0;i<zlc.chr_list.size();i++) { // for (int j=0;j<zlc.chr_list[i].id.size();j++) printf("%d",zlc.chr_list[i].id[j]); // printf("%lf",zlc.chr_list[i].weight); // printf(" "); // } printf("%lf ",zlc.chr_list[0].weight); }