题解 | #点菜问题#
点菜问题
https://www.nowcoder.com/practice/b44f5be34a9143aa84c478d79401e22a
0-1背包问题；
#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;
}