分组背包
【题目链接】https://cn.vjudge.net/problem/HDU-1712
【题目类型】分组背包
&题解:
3层for 第一层:循环分成组的组数
第二层:倒着循环你有的钱数
第三层:循环每个组里面的个数
【时间复杂度】(O(n^3))
&代码:
#include <cstdio>
#include <bitset>
#include <iostream>
#include <set>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <map>
#include <queue>
#include <vector>
using namespace std;
#define INF 0x3f3f3f3f
#define ll long long
#define fo(i,a,b) for(int i=(a);i<=(b);i++)
#define fd(i,a,b) for(int i=(a);i>=(b);i--)
const int maxn = 1e2 + 7;
int n, m, a[maxn][maxn], dp[maxn];
int main() {
freopen("E:1.in", "r", stdin);
while(cin >> n >> m && n) {
memset(dp, 0, sizeof(dp));
fo(i, 1, n) fo(j, 1, m) scanf("%d", &a[i][j]);
fo(k, 1, n) {
fd(v, m, 0) {
fo(i, 1, m) {
if(v >= i)
dp[v] = max(dp[v], dp[v - i] + a[k][i]);
}
}
}
cout << dp[m] << endl;
}
return 0;
}