题解 | #点菜问题#优化成一维

#include <iostream>
#include <cstdio>
using namespace std;

int weight[2000];
int value[2000];
int dp[2000]; //dp[j]容量还有j, 当前价值为dp[j]


int main() {
    int n, m; //n件物品， m为总容量
    while (scanf("%d%d", &m, &n) != EOF) {
        for (int i = 1; i <= n; i++) { //从1开始
            scanf("%d%d", &weight[i], &value[i]);
        }
        for (int i = 0; i <= m;
                i++) { //当啥都不选的时候，就算有再多的容量也没用
            dp[i] = 0;
        }
        for (int i = 1; i <= n; i++) { 
            for (int j = m; j >= weight[i]; j--) {
                dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
            }
        }
        printf("%d\n", dp[m]);
    }
}