题解 | 点菜问题

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>

using namespace std;
int f[1001][102];
int main() {
    int c, n;
    int p[101];
    int v[101];
    
    while (scanf("%d%d", &c, &n) != EOF) {
        for (int i = 0; i < n; i++) {
            scanf("%d%d", &p[i], &v[i]);
        }
        for (int i = 0; i <= n; i++) {
            f[0][i] = 0;
        }
        for (int i = 0; i <= c; i++) {
            f[i][0] = 0;
        }
        for (int i = 1; i <= c; i++) {
            for (int j = 1; j <= n; j++) {
                if (p[j - 1] > i) {
                    f[i][j] = f[i][j - 1];//买不起最后一件商品
                }
                else {
                    f[i][j] = max(f[i][j - 1], f[i - p[j - 1]][j - 1] + v[j - 1]);//在买最后一件商品和不买最后一件商品中选择能获得最大价值的一种
                }
            }
        }
        printf("%d\n", f[c][n]);
    }
    return 0;
}
//注:出现了读取位置时发生了异常,问题可能出现在scanf处,如本题%s写成了%%s