#include <stdio.h> #include <stdlib.h> #include <math.h> struct tt{ int w; int p; }; int main(){ int m,n; int dp[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 = m;j >= t[i].w;j--){ int w = (dp[j - t[i].w] + t[i].p > dp[j])? dp[j - t[i].w] + t[i].p:dp[j]; if(w > dp[j]){ dp[j] = w; } } } printf("%d\n",dp[m]); return 0; } |
Double click to view unformatted code.