xhp956614463 2013-07-19 02:58:00
点我顶贴
收藏
删除
#include<stdio.h>
long int max(long int a,long int b)
{
if(a>b)return a;
else return b;
}
int main()
{
int N,m,v[26],p[26],i,j;
long int s[26][3000]={0};
scanf("%d%d",&N,&m);
for(i=1;i<=m;i++)
scanf("%d%d",&v[i],&p[i]);
for(i=1;i<=m;i++)
{
for(j=N;j>=0;j--)
{
if(j-v[i]>=0)
s[i][j]=max(s[i-1][j],s[i-1][j-v[i]]+v[i]*p[i]);
else
s[i][j]=s[i-1][j];
}
}
printf("%d\n",s[m][N]);
}