【泛化物品】【HDU1712】【ACboy needs your help】

时间：2023-03-08 22:00:17

ACboy needs your help

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 4491    Accepted Submission(s): 2403

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

背包九讲中已经很好的介绍了这种问题：

复杂度（n*m*m)

泛化物品

定义 

考虑这样一种物品，它并没有固定的费用和价值，而是它的价值随着你分配给它的费用而变化。这就是泛化物品的概念。 



更严格的定义之。在背包容量为V的背包问题中，泛化物品是一个定义域为0..V中的整数的函数h，当分配给它的费用为v时，能得到的价值就是h(v)。 



这个定义有一点点抽象，另一种理解是一个泛化物品就是一个数组h[0..V]，给它费用v，可得到价值h[V]。 



一个费用为c价值为w的物品，如果它是01背包中的物品，那么把它看成泛化物品，它就是除了h(c)=w其它函数值都为0的一个函数。如果它是完全背包中的物品，那么它可以看成这样一个函数，仅当v被c整除时有h(v)=v/c*w，其它函数值均为0。如果它是多重背包中重复次数最多为n的物品，那么它对应的泛化物品的函数有h(v)=v/c*w仅当v被c整除且v/c<=n，其它情况函数值均为0。 



一个物品组可以看作一个泛化物品h。对于一个0..V中的v，若物品组中不存在费用为v的的物品，则h(v)=0，否则h(v)为所有费用为v的物品的最大价值。P07中每个主件及其附件集合等价于一个物品组，自然也可看作一个泛化物品。 



泛化物品的和 

如果面对两个泛化物品h和l，要用给定的费用从这两个泛化物品中得到最大的价值，怎么求呢？事实上，对于一个给定的费用v，只需枚举将这个费用如何分配给两个泛化物品就可以了。同样的，对于0..V的每一个整数v，可以求得费用v分配到h和l中的最大价值f(v)。也即f(v)=max{h(k)
+l(v-k)|0<=k<=v}。可以看到，f也是一个由泛化物品h和l决定的定义域为0..V的函数，也就是说，f是一个由泛化物品h和 l决定的泛化物品。 



由此可以定义泛化物品的和：h、l都是泛化物品，若泛化物品f满足f(v)=max{h(k)+l(v-k)|0<=k<=v}，则称f是h与l的和，即f=h+l。这个运算的时间复杂度是O(V^2)。

泛化物品的定义表明：在一个背包问题中，若将两个泛化物品代以它们的和，不影响问题的答案。事实上，对于其中的物品都是泛化物品的背包问题，求它的答案的过程也就是求所有这些泛化物品之和的过程。设此和为s，则答案就是s[0..V]中的最大值。

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <cstring>

#include <ctime>

#include <algorithm>

#include <iostream>

#include <sstream>

#include <string>

#define oo 0x13131313

using namespace std;

int n,m;

int A[101][101];

void input()

{

	for(int i=1;i<=n;i++)

	 for(int j=1;j<=m;j++)

	 	scanf("%d",&A[i][j]);

}

void init()

{

	freopen("a.in","r",stdin);

	freopen("a.out","w",stdout);

}

void ADD(int *ans,int *a,int *b)

{

	for(int i=0;i<=m;i++)

	{

		ans[i]=0;

		for(int j=0;j<=i;j++)

		{

			ans[i]=max(ans[i],a[j]+b[i-j]);

		}

	}

}

void solve()

{

	int ans=0;

	if(n>=2)

	{

		ADD(A[0],A[1],A[2]);

		for(int i=3;i<=n;i++)

		ADD(A[i-2],A[i-3],A[i]);

		for(int i=1;i<=m;i++)

		ans=max(ans,A[n-2][i]);

		printf("%d\n",ans);

	}

	else

	{

		for(int i=1;i<=m;i++)

		ans=max(ans,A[1][i]);

		printf("%d\n",ans);

	}

}

int main()

{

//	init();

	while(cin>>n>>m&&(n||m))

	{

		input();

		solve();

	}

}