不能
by 142857cs @ 2018-11-03 17:28:42
用dp
by ghy21 @ 2018-11-03 17:29:05
可以
by あおあんどん @ 2018-11-03 17:30:55
记搜吧
by WorldBest丶牛顿 @ 2018-11-03 17:34:23
可以
by 绵中大佬 @ 2018-11-03 17:40:33
@[chenyingchao](/space/show?uid=135515) 可以，你可以看一下第二页万象天引的搜索（打个广告），不过本人建议DP还是要学
by cnyali_hjh @ 2018-11-03 17:49:43
~~用dp~~
by smallfang @ 2018-11-03 17:54:00
记忆化搜~~（其实背包实在不会把模板背下来都没关系）~~
by goodlearndaydayup @ 2018-11-03 17:54:24
大佬...
by chenyingchao @ 2018-11-03 19:32:48
@[chenyingchao](/space/show?uid=135515) 用遗传算法
```cpp
#include<bits/stdc++.h>
using namespace std;
#define IL inline
#define RG register
#define gi getint()
#define pi(k) putint(k)
#define gc getchar()
IL int getint()
{
RG int xi=0;
RG char ch=gc;
bool f=0;
while((ch<'0')|(ch>'9'))ch=='-'?f=1:f,ch=gc;
while((ch>='0')&(ch<='9'))xi=(xi<<1)+(xi<<3)+ch-48,ch=gc;
return f?-xi:xi;
}
IL void putint(int k)
{
if(k<0)k=-k,putchar('-');
if(k>=10)putint(k/10);
putchar(k%10+'0');
}
int n,m,ans;
struct object
{
int weigh;
int val;
} pl[25];
double mutation=0.94*RAND_MAX;
double crossover=0.4*RAND_MAX;
const int NUM=20;
struct DNA
{
// vector<bool>s;
bool s[25];
int val;
inline void init(int n)
{
//s.resize(n+1);
for(register int i=1; i<=n; i++)s[i]=rand()&1;
val=getval();
}
inline int getval() //计算答案
{
int ans=0,bag=m;
for(register int i=1; i<=n; i++)
{
if(s[i]&&bag>=pl[i].weigh)
{
ans+=pl[i].val;
bag-=pl[i].weigh;
}
}
return ans;
}
/* inline void clear()
{
vector<bool>().swap(s);
}*/
}lif[2][NUM+1];
DNA * life=lif[0];
long long sum;
double P[NUM+1];
bool now;
inline void init()
{
for(register int i=1; i<=NUM; i++)life[i].init(n);
}
inline int choice()
{
double m=0;
double r=(double)rand()/RAND_MAX;
for(int i=1;i<=n;i++){m+=P[i];if(r<=m)return i;}
return n;
}
DNA fa,mo;
inline void competition()
{
sum=0;
int xmax=0,xval=0,xxmax;
for(int i=1;i<=NUM;i++)
{
sum+=life[i].val;
if(life[i].val>ans)ans=life[i].val;
if(life[i].val>xval)xxmax=xmax,xmax=i,xval=life[i].val;
}
for(int i=1;i<=NUM;i++)P[i]=(double)life[i].val/sum;
int cnt=0;now=!now;
lif[now][++cnt]=life[xmax],lif[now][++cnt]=life[xxmax];
do{
fa=life[choice()],mo=life[choice()];
if(crossover>rand())
{
int midl=rand()%n+1,midr=rand()%(n-midl+1)+midl;
for(int i=midl;i<=midr;i++){bool tmp=fa.s[i];fa.s[i]=mo.s[i],mo.s[i]=tmp;}
}
if(mutation>rand()){int ars=rand()%n+1;fa.s[ars]=!fa.s[ars],mo.s[ars]=!mo.s[ars];}
fa.val=fa.getval(),mo.val=mo.getval();
lif[now][++cnt]=fa,lif[now][++cnt]=mo;
//fa.clear(),mo.clear();
}while(cnt<NUM);
life=lif[now];
}
inline void work()
{
m=gi,n=gi;
for(register int i=1; i<=n; i++)
{
pl[i].weigh=gi;
pl[i].val=gi*pl[i].weigh;
}
int l=5000;
while(l--)competition();
printf("%d",ans);
}
int main(void)
{
srand(time(0));
work();
return 0;
}
```
by あおあんどん @ 2018-11-03 22:34:29