C++ 算法：健康饮食最大蛋白含量计算 (不使用 VECTOR)

本篇文章介绍如何使用 C++ 算法解决一个健康饮食问题，帮助用户计算在限制条件下能吃到的最大蛋白含量总和。

问题描述：

寒假到了，为了能够更加健康地迎接新年的到来，王老师决定开始健康饮食，努力健身。 为了增肌，他希望吃到更多的蛋白质。然而也不能只吃高蛋白食品，那样的话就会导致缺少其他营养。他通过研究发现：真正的营养膳食规定某类食品不宜一次性吃超过若干份。比如就一顿饭来说，肉类不宜吃超过1份，鱼类不宜吃超过1份，蛋类不宜吃超过1份，蔬菜类不宜吃超过2份。王老师想要在营养膳食的情况下吃到更多的蛋白质，当然他的食量也是有限的。请你编写程序，帮他计算出可以吃到的最大蛋白含量总和。

输入描述:

第一行包含三个正整数 n, m 和 k。表示王老师每顿饭最多只能吃不超过 m 份食品，同时有 n 种食品供王老师选择，而这 n 种食品分为 k 类。

第二行包含 k 个不超过 10 的正整数，表示可以吃 1 到 k 类食品的最大份数。

接下来 n 行每行包括 2 个正整数，分别表示该食品的蛋白含量 ai 和所属的类别 bi。

输出描述:

共一行，一个数字即可以吃到的最大蛋白含量总和。

样例 1

输入 6 6 3 3 3 2 15 1 15 2 10 2 15 2 10 2 5 3 输出 60

提示

n≤200，m≤100，k≤100；ai≤100，bi≤k。

解决方法：

这个问题可以使用动态规划来解决。我们可以定义一个二维数组 dp，其中 dp[i][j] 表示在前 i 种食品中选择不超过 j 份食品时可以获得的最大蛋白含量总和。

我们可以使用以下递推关系来计算 dp[i][j]：

dp[i][j] = max(dp[i-1][j], dp[i-1][j-k] + k * 蛋白含量)，其中 k 不超过每类食品的最大份数，且 j-k 大于等于 0。

具体的实现如下：

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

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    int maxCount[k];
    for (int i = 0; i < k; i++) {
        cin >> maxCount[i];
    }
    
    int protein[n+1], category[n+1];
    for (int i = 1; i <= n; i++) {
        cin >> protein[i] >> category[i];
    }
    
    int dp[n+1][m+1];
    memset(dp, 0, sizeof(dp));
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            dp[i][j] = dp[i-1][j];
            for (int k = 1; k <= min(maxCount[category[i]-1], j); k++) {
                dp[i][j] = max(dp[i][j], dp[i-1][j-k] + k * protein[i]);
            }
        }
    }
    
    cout << dp[n][m] << endl;
    
    return 0;
}

时间复杂度：O(nmk) 空间复杂度：O(nm)