题解 | #点菜问题#

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

const int maxm=1001;
const int maxn=101;
int dp[maxm];
int price[maxn];
int point[maxn];

int main(){
	int C,N;
	while(~scanf("%d%d",&C,&N)){
		for(int i=0;i<N;i++){
			scanf("%d%d",&price[i],&point[i]);
		}
		fill(dp,dp+C+1,0);
		for(int i=0;i<N;i++){
			for(int j=C;j>=price[i];j--){	//注意需要从右向左遍历，以免dp[j-price[i]]未被修改。 
				dp[j]=max(dp[j],dp[j-price[i]]+point[i]);
			}
		}
		printf("%d\n",dp[C]);
	}
	return 0;
}