hdu1712

maksyuki 发表于 oj 分类，标签: DP-背包

15 9月 2015

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 3

3 2 1

0 0

Sample Output

Source

HDU 2007-Spring Programming Contest

题目类型：分组背包

算法分析： 每一个人分为一组，每组中的物品由不同时间(花费)来区分，然后直接使用分组背包求解即可，注意一定要先判断j >= k !!!!!!

#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;
}

#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;

}

hdu1698

hdu1754

一	二	三	四	五	六	日
« 6月
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

超客的水墨烟雨

hdu1712

ACboy needs your help

分类目录

标签云

书签

近期评论