最裸的分组背包
记住枚举顺序
for(枚举组数){
for(从大到小枚举体积){
for(枚举这一组中的个体){
和01背包的滚动数组代码完全一致
}
}
}
如果不知道为什么，强烈推荐百度一下 背包九讲，里面说的非常的清楚~
#include<cstdio>
#include<cmath>
#include<cstring>
#include<queue>
#include<vector>
#include<ctime>
#include<functional>
#include<algorithm>using namespace std;
typedef long long LL;
typedef pair<int, int> PII;const int MX = 1e2 + 5;
const int INF = 0x3f3f3f3f;int dp[MX], A[MX][MX];int main() {int n, m;while(~scanf("%d%d", &n, &m), m + n) {memset(dp, 0, sizeof(dp));for(int i = 1; i <= n; i++) {for(int j = 1; j <= m; j++) {scanf("%d", &A[i][j]);}}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]);}}}printf("%d\n", dp[m]);}return 0;
}