题解 | ACboy needs your help

题干解析

题设给予课程数N与学习天数M，且每门科目学习对应1-M天均有一定的收益，问如何分配学习时间使得最后的总收益最高，返回最高值。

算法思路

典型的分组背包DP问题。

我们定义状态值表示将前i类物品（这里是课程）放进容量为j的背包（这里是学习天数）可获得的最大价值。由此状态转移方程如下：

其中表示不装入第i类物品，表示依次装入第i类物品

对比普通0/1背包，只要内层循环增添关于k的一层即可。

实现代码

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, m;
    while (cin >> n >> m) {
        if (!n && !m) break;
        vector<vector<int>> w(n + 1, vector<int>(m + 1));
        vector<vector<int>> c(n + 1, vector<int>(m + 1));
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                cin >> w[i][j];
                c[i][j] = j;
            }
        }
        vector<int> dp(m + 1, 0);
        for (int i = 1; i <= n; ++i) {
            for (int j = m; j >= 0; --j) {
                for (int k = 1; k <= m; ++k) {
                    if (j >= c[i][k]) {
                        dp[j] = max(dp[j], dp[j - c[i][k]] + w[i][k]);
                    }
                }
            }
        }
        cout << dp[m] << '\n';
    }

    return 0;
}

复杂度分析

• 时间复杂度：三层嵌套循环为主时间复杂度为
• 空间复杂度：耗时数组与价值数组占主要，空间复杂度为