点菜问题(北京大学考研机试题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;
}