ACboy needs your help
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
题目类型：分组背包
算法分析： 每一个人分为一组，每组中的物品由不同时间(花费)来区分，然后直接使用分组背包求解即可，注意一定要先判断j >= k !!!!!!
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 |
#include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> #define lson rt << 1, l, m #define rson rt << 1 | 1, m + 1, r using namespace std; const int INF = 0x7FFFFFFF; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int MOD = 7; const int maxn = 500 + 66; int ans[maxn][maxn], dp[maxn]; int main() { // ifstream cin ("aaa.txt"); int n, m; while (cin >> n >> m) { if (n == 0 && m == 0) break; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> ans[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] + ans[i][k]); } } } int maxval = -INF; for (int i = 0; i <= m; i++) maxval = max (maxval, dp[i]); cout << maxval << endl; } return 0; } |