题解 | 点菜问题

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

const int MAXC=1001;
const int MAXN=101;
int main()
{
	int C,N;
	while(cin>>C>>N)
	{
		int price[MAXN];
		int score[MAXN];
		int dp[MAXC];//注意dp初始化长度是MAXC,dp[j]表示当报销额度为j时所选菜品的最大评价分数 
		for(int i=1;i<=N;i++)//ddd注意最好从下标1开始，并且=n结束(输入的物品信息从下标1开始，<=N结束） 
		{
			cin>>price[i]>>score[i]; 
		}
		for(int i=0;i<=C;i++) //这里注意一定是<=C!!!
		{
			dp[i]=0;
		}//其实这里也可以省略，直接int dp[MAXC]={0}也可以 
		
		for(int i=1;i<=N;i++)//因为上面ddd处从下标1开始，所以这里保持一致 
		{
			for(int j=C;j>=price[i];j--)
			{
				dp[j]=max(dp[j],dp[j-price[i]]+score[i]);
			}
		 } 
		cout<<dp[C]<<endl;//这里注意判断一下是否会出现无解 
	}
	return 0;
}