HDU3535 AreYouBusy 混合背包

题目大意

给出几组物品的体积和价值，每组分为三种：0.组内物品至少选一个；1.组内物品最多选一个；2.组内物品任意选。给出背包容量，求所能得到的最大价值。

注意

仔细审题，把样例好好看完了再答题，否则非常浪费时间！

混合背包

定义DP(i,j)为轮到第1~i组背包内物品总体积严格为j时所能得到的最大价值，实现用滚动数组。（以下i或i-1后都&1）

种类2

把当前的DP(i,..)当作一个关于背包的一维覆盖数组（因为是关于整个背包的数组，所以要把DP(i-1,...)的值拷贝到一维覆盖数组中），对该组内所有物品在背包内进行01背包即可。递归式DP(k,j)=max{DP(k-1, j), DP(k-1, j-v[k])+w[k]}.

注意

因为DP在一个一维覆盖数组内进行，所以DP内的第一个参数永远是i。

种类1

在整个背包内进行一遍分组背包即可。递归式为DP(i,j)=max{DP(i-1, j), max{DP(i-1,j-v[i][k])+W[i][k] | k属于组i}}

注意

DP中第一个参数的值总是i-1。

种类0

01背包中，如果DP(i-1, j)>DP(k=1, j-v[k])+w[k]且每个DP(k-1, j)>DP(k,j-v[k]+w[k])可能会导致该组的物品一个都不选，但是DP值小一点不要求最大可能也能满足题意。此时就要对每一个k提供几个总价值小一点的选择，包括k-1所代表的稍小值（规定k-1的较小值是1~k-1中较小值中最大的），或不要k-1等物品，直接在i-1组放入k所代表的较小值（两个较小值不一定谁大呢）。

对于每个物品k，三种操作：选：1.在k之前的物品的基础上放入k，2.在i-1组内的基础上放入k。3.不选（k以前物品选出了一个则有解，否则再也没办法有解了）

即使不存在一开始所说的情况，1，3也是标准的01背包。以上取最大值即可。

注意

一开始数组是清空的。

注意

只在一开始对DP[0][0]设为0，其余设为-INF。对于每个组不要设置DP[i][0]。
循环体积要一直循环到0，因为有体积为0的物体。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cassert>
using namespace std;

const int MAX_GROUP = 110, MAX_V = 110, MAX_EACH_OBJ = 100, MAX_TYPE = 3;
int V[MAX_GROUP][MAX_EACH_OBJ], W[MAX_GROUP][MAX_EACH_OBJ], Type[MAX_GROUP], ObjCnt[MAX_GROUP];
int totGroup, totV;

int Proceed()
{
	static int DP[2][MAX_V];
	memset(DP, 0xcf, sizeof(DP));
	DP[0][0] = 0;
	for (int i = 1; i <= totGroup; i++)
	{
		memset(DP[i & 1], 0xcf, sizeof(DP[i & 1]));
		switch (Type[i])
		{
		case 0://至少选一个
			for (int k = 1; k <= ObjCnt[i]; k++)
			{
				for (int j = totV; j >= V[i][k]; j--)
				{
					DP[i & 1][j] = max(DP[i & 1][j], DP[i & 1][j - V[i][k]] + W[i][k]);
					DP[i & 1][j] = max(DP[i & 1][j], DP[(i - 1) & 1][j - V[i][k]] + W[i][k]);
				}
			}
			break;
		case 1://最多选一个
			memcpy(DP[i & 1], DP[i - 1 & 1], sizeof(DP[i - 1 & 1]));
			for (int j = totV; j >= 0; j--)
				for (int k = 1; k <= ObjCnt[i]; k++)
					if (j >= V[i][k])
						DP[i & 1][j] = max(DP[i & 1][j], DP[i - 1 & 1][j - V[i][k]]+W[i][k]);
			break;
		case 2://随便
			memcpy(DP[i & 1], DP[i - 1 & 1], sizeof(DP[i - 1 & 1]));
			for (int k = 1; k <= ObjCnt[i]; k++)
				for (int j = totV; j >= V[i][k]; j--)
					DP[i & 1][j] = max(DP[i & 1][j], DP[i & 1][j - V[i][k]] + W[i][k]);
			break;
		default:
			assert(0);
		}
	}
	int ans = -1;
	for (int j = 0; j <= totV; j++)
		ans = max(ans, DP[totGroup&1][j]);
	return ans;
}

int main()
{
#ifdef _DEBUG
	freopen("c:\noi\source\input.txt", "r", stdin);
	freopen("c:\noi\test\output.txt", "w", stdout);
#endif
	while (~scanf("%d%d", &totGroup, &totV))
	{
		for (int group = 1; group <= totGroup; group++)
		{
			scanf("%d%d", group + ObjCnt, group + Type);
			for (int obj = 1; obj <= ObjCnt[group]; obj++)
				scanf("%d%d", obj + V[group], obj + W[group]);
		}
		printf("%d
", Proceed());
	}
}