- #include <stdio.h>
- int max(int x,int y){return x>y?x:y;}
- int main(){
- int n,m,w[101],c[101],dp[1001]={0};
- scanf("%d%d",&m,&n);
- for(int i=1;i<=n;i++)
- scanf("%d%d",c+i,w+i);
- for(int i=1;i<=n;i++)
- for(int j=c[i];j<=n;j++)
- dp[j]=max(dp[j],dp[j-c[i]]+w[i]);
- printf("%d\n",dp[m]);
- return 0;
- }
复制代码 |