#include <stdio.h> #include <stdlib.h> #include <math.h> struct tt{ int w; int p; }; int max(int a,int b){ return (a > b)? a : b; } int main(){ int m,n; int dp[101][1000] = {0}; struct tt t[101]; scanf("%d %d",&m,&n); for(int i = 1;i <= n;i++){ scanf("%d %d",&t[i].w,&t[i].p); } for(int i = 1;i <= n;i++){ for(int j = 1;j <= m;j++){ if(j >= t[i].w){ dp[i][j] = max(dp[i - 1][j],dp[i - 1][j - t[i].w] + t[i].p); }else{ dp[i][j] = dp[i - 1][j]; } } } printf("%d\n",dp[n][m]); return 0; } |
Double click to view unformatted code.