题解 | #点菜问题#

#include <bits/stdc++.h>
#define MAX 1000
using namespace std;
int main() {
    int dp[MAX], w[MAX], v[MAX];
    int C, N;   //C报销额度，N数量
    while (cin >> C >> N) {
        for (int i = 0; i < N; i++)
            cin >> w[i] >> v[i];
        memset(dp, 0, sizeof(dp));
        for (int i = 0; i < N; i++)
            for (int j = C; j >= w[i]; j--) {
                dp[j] = max(dp[j - w[i]] + v[i], dp[j]);
            }
        cout << dp[C] << endl;
    }

}