题解 | #点菜问题#

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;
int p[N]; //价格
int v[N]; // 可口程度
int f[N][N];
// f[i][j] 从前i种样品中取，不超过j元的最大评分 

int main(){
	int c; // 报销最大额度 
	int n; // 菜种类 
	while(cin >> c >> n){
	
		for (int i=1; i<=n; i++) {
			cin >> p[i] >> v[i]; 
		}
		
		for (int i=1; i<=n; i++){
			for (int j=0; j<=c; j++){
				if (j < p[i]){
					f[i][j] = f[i-1][j];
				}
				else{
					f[i][j] = max(f[i-1][j], f[i-1][j-p[i]]+v[i]);
				}
			}
		}
		
		printf("%d\n", f[n][c]);
		
	}
	return 0;
}