题目链接：点击打开链接
题意：
有个学生要复习 n 个功课；
每个功课有 m 种复习方式；
每复习一个功课就会得到一定的回报；
即：满足一个矩阵；
即：第 i 种功课需要花费 j 天并得到 v[i][j] 的回报；
问怎样分配才能得到最大回报；
理解：
原以为是 01背包；
结果发现有个问题；
即：如果用 1 天复习了该功课， 那么就不能再复习该功课了；
那么就是分组背包的问题了。。。
且看此图片：
图片说的很详细，便不再赘述；
代码如下：
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <ctime> #include <iostream> #include <algorithm> #include <vector> #include <string> #include <map> #include <set> #include <queue> #include <stack> using namespace std; typedef long long LL; typedef pair<int, int> PII; const int MIN_INF = 1e-7; const int MAX_INF = (1e9) + 7; #define X first #define Y second int dp[1111]; //dp 表示前 k 组在 j 的花费下取得的最大值； int v[111][111]; int main() { int n, m; while (cin >> n >> m && n + m) { int k = 0; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { scanf("%d", &v[i][j]); } } memset(dp, 0, sizeof(dp)); for (int k = 1; k <= n; ++k) { // k 表示每一组 for (int j = m; j >= 0; --j) { // j 表示一维 dp 下的花费费用 for (int i = 1; i <= m; ++i) { // i 表示每一组的每一项 if (j >= i) { dp[j] = max(dp[j], dp[j - i] + v[k][i]); } } } } cout << dp[m] << endl; } return 0; }
