题解 | #点菜问题#

#include<stdio.h>
int max(int a, int b) {
    if (a > b)return a;
    return b;
}
int main() {
    int C, N, maxdp = -10000;
    scanf("%d %d", &C, &N);
    int i, j, weight[N], value[N], dp[101][1001];
    for (i = 0; i < N; i++)scanf("%d %d", &weight[i], &value[i]);
    for (i = 0; i < 101; i++) {
        for (j = 0; j < 1001; j++) {
            dp[i][j] = -9999;
        }
    }
    for (i = 0; i < N; i++)dp[i][0] = 0;
    for (j = 1; j <= C; j++) {
        dp[0][j] = value[0];
        if (j - weight[0] < 0)dp[0][j] = 0;
    }
    for (i = 1; i < N; i++) {
        for (j = 1; j <= C; j++) {
            dp[i][j] = max(dp[i - 1][j],
                           j - weight[i] < 0 ? 0 : value[i] + dp[i - 1][j - weight[i]]);
        }
    }
    for (i = 0; i < 101; i++) {
        for (j = 0; j < 1001; j++) {
            if (dp[i][j] > maxdp)maxdp = dp[i][j];
        }
    }
    printf("%d\n", maxdp);
  return 0;
}