题目链接
#include<iostream>
#include<cstdio>
using namespace std;
const int N=105,M=1e3+5;
int n,m;
int f[N][M],v[N],w[N];
int ans;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>m>>n;
for(int i=1;i<=n;i++)cin>>w[i]>>v[i];
for(int i=1;i<=n;i++){
for(int j=w[i]-1;~j;j--)
f[i][j]=f[i-1][j];
for(int j=m;j>=w[i];j--)
f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i]);
}
for(int i=1;i<=m;i++)ans=max(ans,f[n][i]);
cout<<ans<<endl;
return 0;
}
//coder:Iictiw
//date:23/07/15
#include<iostream>
#include<cstdio>
using namespace std;
const int N=105,M=1e3+5;
int n,m;
int f[M],v[N],w[N];
int ans;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>m>>n;
for(int i=1;i<=n;i++)cin>>w[i]>>v[i];
for(int i=1;i<=n;i++)
for(int j=m;j>=w[i];j--)
f[j]=max(f[j],f[j-w[i]]+v[i]);
for(int i=1;i<=m;i++)ans=max(ans,f[i]);
cout<<ans<<endl;
return 0;
}
//coder:Iictiw
//date:23/07/15