题解 | #点菜问题#

#include<iostream>
using namespace std;
const int MAXN=1000+10;
int weight[MAXN];//钱数
int value[MAXN];//评价
int dp[MAXN];
int main(){
    int c,n;//n数量
    while(cin>>c>>n){
        for(int i=1;i<=n;i++){
            cin>>weight[i]>>value[i];
        }
        for(int j=0;j<=c;j++){
            dp[j]=0;
        }
        for(int i=1;i<=n;i++){
            for(int j=c;j>=weight[i];j--){
                dp[j]=max(dp[j],dp[j-weight[i]]+value[i]);
            }
        }
        cout<<dp[c]<<endl;
    }
    return 0;
}