一个简单的分组背包问题 大概是这个意思 让你选取m天来复习n门功课 每门功课复习的时间不同收益也不一样 可以有功课没有被复习 让我们找到收益最高的选法
还不懂分组背包的童鞋可以参考下 背包九讲什么的 我看了这个人的博客 点击打开链接
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int main()
{
int dp[105][105], a[105][105];
int n, m;
while (cin >> n >> m && (n + m)) {
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= m; j ++)
cin >> a[i][j];
memset(dp,0,sizeof(dp));
for (int i = 1; i <= n; i ++) {
for (int j = m; j >= 0; j --) {
for(int k = 1; k <= m; k ++) {
if(j >= k)
dp[j] = max(dp[j] , dp[j - k] + a[i][k]);
}
}
}
cout << dp[m] << endl;
}
}
