C++: 健康饮食最大蛋白质含量计算

///'C++: 题目描述//n寒假到了，为了能够更加健康地迎接新年的到来，王老师决定开始健康饮食，努力健身。 为了增肌，他希望吃到更多的蛋白质。然而也不能只吃高蛋白食品，那样的话就会导致缺少其他营养。他通过研究发现：真正的营养膳食规定某类食品不宜一次性吃超过若干份。比如就一顿饭来说，肉类不宜吃超过1份，鱼类不宜吃超过1份，蛋类不宜吃超过1份，蔬菜类不宜吃超过2份。王老师想要在营养膳食的情况下吃到更多的蛋白质，当然他的食量也是有限的。请你编写程序，帮他计算出可以吃到的最大蛋白含量总和。//n//n输入描述//n第一行包含三个正整数n, m和k。表示王老师每顿饭最多只能吃不超过m份食品，同时有n种食品供王老师选择，而这n种食品分为k类。//n//n第二行包含k个不超过10的正整数，表示可以吃1到k类食品的最大份数。//n//n接下来n行每行包括2个正整数，分别表示该食品的蛋白含量ai和所属的类别bi。//n//n输出描述//n共一行，一个数字即可以吃到的最大蛋白含量总和。//n//n样例1//n输入//n6 6 3//n3 3 2 //n15 1 //n15 2 //n10 2 //n15 2 //n10 2 //n5 3 //n输出//n60//n提示//nn≤200，m≤100，k≤100；ai≤100，bi≤k。//n//n内容：思路：//n首先，我们需要将食物按照类别进行分类，并将每个类别的食物按照蛋白质含量从大到小进行排序。//n//n然后，我们需要建立一个二维数组dp，其中dp[i][j]表示在前i种类别的食物中，选择不超过j份食物所能获得的最大蛋白质含量总和。//n//n对于dp[i][j]，可以有两种选择：//n1. 不选择第i种类别的食物，那么dp[i][j] = dp[i-1][j]；//n2. 选择第i种类别的食物，那么dp[i][j] = dp[i-1][j-k] + k * 蛋白质含量，其中k为不超过j份的第i种类别食物的份数。//n//n最后，我们需要找到dp[n][m]的最大值，即可得到可以吃到的最大蛋白质含量总和。//n//n具体实现如下：//n//n#include //n#include //n#include //nusing namespace std; //n//nstruct Food {//n int protein; //n int category; //n}; //n//nbool cmp(Food a, Food b) {//n return a.protein > b.protein; //n} //n//nint main() {//n int n, m, k; //n cin >> n >> m >> k; //n//n vector maxNum(k); //n for (int i = 0; i < k; i++) {//n cin >> maxNum[i]; //n } //n//n vector foods(n); //n for (int i = 0; i < n; i++) {//n cin >> foods[i].protein >> foods[i].category; //n } //n//n sort(foods.begin(), foods.end(), cmp); //n//n vector<vector> dp(n + 1, vector(m + 1, 0)); //n//n for (int i = 1; i <= n; i++) {//n int curCategory = foods[i - 1].category; //n int curProtein = foods[i - 1].protein; //n int maxCurNum = min(maxNum[curCategory - 1], m); //n for (int j = 1; j <= m; j++) {//n dp[i][j] = dp[i - 1][j]; //n for (int k = 1; k <= maxCurNum; k++) {//n if (j - k >= 0) {//n dp[i][j] = max(dp[i][j], dp[i - 1][j - k] + k * curProtein); //n } //n } //n } //n } //n//n cout << dp[n][m] << endl; //n//n return 0; //n} //n/