题解 | 点菜问题

#include<iostream>

using namespace std;
const int N = 110;

int f[N * 10];
int v[N], w[N];

int main() {
	int c, n;
	cin >> c >> n;
	for (int i = 1; i <= n; i++) {
		cin >> v[i] >> w[i];
	}
	//i是点菜编号，j是花销
	for(int i=1;i<=n;i++)
		for (int j = c; j >= v[i]; j--) {
			f[j] = max(f[j], f[j - v[i]] + w[i]);
		}
	cout << f[c];

	return 0;
}