ACboy needs your help

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 6959    Accepted Submission(s): 3857 Problem Description ACboy has N courses this term, and he plans to spend at most M days on study.Of course,the profit he will gain from different course depending on the days he spend on it.How to arrange the M days for the N courses to maximize the profit?   Input The input consists of multiple data sets. A data set starts with a line containing two positive integers N and M, N is the number of courses, M is the days ACboy has. Next follow a matrix A[i][j], (1<=i<=N<=100,1<=j<=M<=100).A[i][j] indicates if ACboy spend j days on ith course he will get profit of value A[i][j]. N = 0 and M = 0 ends the input.   Output For each data set, your program should output a line which contains the number of the max profit ACboy will gain.   Sample Input 2 2 1 2 1 3 2 2 2 1 2 1 2 3 3 2 1 3 2 1 0 0   Sample Output 3 4 6   Source HDU 2007-Spring Programming Contest   Recommend lcy  

题目大意:n门课程以及m天,每一天都有一个收益，收益最大为多少 解题思路:这是个比较标准的分组背包问题，她的特点在于同一组的只能选一个，不能多选，意味着互斥，也就是说对于这道题来说，一门学科不能即选择学习一天同时选择学习两天，这样是违背了分组背包问题，该问题的算法是利用三层循环，最外层的循环是组数，第二层循环是背包体积，第三层循环是每组的数据，顺序不能颠倒，由于只做了一题，有些片面，所以以后遇到了分组背包，再多总结一些 #include<iostream> #include<cstdio> #include<stdio.h> #include<cstring> #include<cstdio> #include<climits> #include<cmath> #include<vector> #include <bitset> #include<algorithm> #include <queue> #include<map> using namespace std; int a[105][105], dp[105]; int n, m, i, j, k; int main() { for (;;) { cin >> n >> m; if (n == 0 && m == 0) { return 0; } memset(a, 0, sizeof(a)); memset(dp, 0, sizeof(dp)); for (i = 1; i <= n; i++) { for (j = 1; j <= m; j++) { cin >> a[i][j]; } } for (i = 1; i <= n; i++) { for (j = m; j >= 0; j--) { for (k = 0; k <= j; k++) { dp[j] = max(dp[j],dp[j - k] + a[i][k]); } } } cout << dp[m] << endl; } }