点菜问题(北京大学考研机试题01背包)
北大网络实验室经常有活动需要叫外卖，但是每次叫外卖的报销经费的总额最大为 CC 元，有 NN 种菜可以点，经过长时间的点菜，网络实验室对于每种菜 ii 都有一个量化的评价分数（表示这个菜可口程度），为 ViVi，每种菜的价格为 PiPi, 问如何选择各种菜，使得在报销额度范围内能使点到的菜的总评价分数最大。
注意：由于需要营养多样化，每种菜只能点一次。
输入格式
输入的第一行有两个整数 CC 和 NN，CC 代表总共能够报销的额度， NN 代表能点菜的数目。
接下来的 NN 行每行包括两个整数 PiPi 和 ViVi，分别表示第 ii 道菜的价格和评价分数。
输出格式
输出共一行，一个整数，表示在报销额度范围内，所点的菜能够得到的最大评价分数。
数据范围
1≤C≤10001≤C≤1000,
1≤N≤1001≤N≤100,
1≤Pi,Vi≤1001≤Pi,Vi≤100
输入样例：
90 4
20 25
30 20
40 50
10 18
输出样例：
95#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int f[N][N];
int c,n;
int p[N],v[N];
int main()
{
cin>>c>>n;
for(int i=1;i<=n;i++) cin>>p[i],cin>>v[i];
for(int i=1;i<=n;i++)
{
for(int j=1;j<=c;j++)
{
f[i][j]=f[i-1][j];
if(j>=p[i]) f[i][j]=max(f[i-1][j],f[i-1][j-p[i]]+v[i]);
}
}
cout<<f[n][c];
return 0;
}