题解 | #点菜问题#

#include <iostream>
using namespace std;
int dp[101][1001];
int main() {
   int n,c;
   while(cin >> c >> n){
     for(int i = 0; i < 101; i ++){
        for(int j = 0; j < 1001; j ++) dp[i][j] = 0;
     }
     int *w = (int*)malloc(sizeof(int)*(n+1));
     int *v = (int*)malloc(sizeof(int)*(n+1));
     for(int i = 1; i <= n; i ++) cin >> w[i] >> v[i];
     for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= c; j ++){
            if(j < w[i]) dp[i][j] = dp[i-1][j];
            else dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]);
        }
     }
     cout << dp[n][c] << endl;
   }
   return 0;
}