组合背包问题

题目链接：https://www.acwing.com/problem/content/9/

题目描述

有 N 组物品和一个容量是 V 的背包。
每组物品有若干个，同一组内的物品最多只能选一个。
每件物品的体积是 vij，价值是 wij，其中 i 是组号，j 是组内编号。
求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。
输出最大价值。

输入描述

第一行有两个整数 N，V，用空格隔开，分别表示物品组数和背包容量。
接下来有 N 组数据：
每组数据第一行有一个整数 Si，表示第 i 个物品组的物品数量；
每组数据接下来有 Si 行，每行有两个整数 vij,wij，用空格隔开，分别表示第 i 个物品组的第 j 个物品的体积和价值；

输出描述

输出一个整数，表示最大价值。
0<N,V≤100
0<Si≤100
0<vij,wij≤100

示例

输入

3 5
2
1 2
2 4
1
3 4
1
4 5

输出

8

分析

约定

我们记第i组第j件物品的体积，价值和数量为v[i][j],w[i][j],v[i][0]

状态表示

f(i,j)表示满足如下条件的方案的最大价值：

• 仅从前i组物品中选择
• 所选取的物品体积小于等于j

状态划分

对于f(i,j),存在两大种情况：

• 没选第i组物品
• 选了第i组物品

状态转移方程

对应状态划分，我们便可以得到相应的状态转移方程：

• f(i,j)=f(i-1,j)
• f(i,j)=max(f(i-1,j-v[i][k])+w[i][k])   (j-v[i][k]>=0,k=1,2,···,v[i][0])

总结

分组背包就是0-1背包问题的变种，按照相似的方法和划分状态进行计算即可。
且此处分组背包可以用0-1背包中的方法优化，直接改为一维即可，此处不再赘述。

AC代码

---

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 101;
int n, V;
int v[N][N], w[N][N], s[N][N];
int f[N];

int main()
{
	cin >> n >> V;

	for (int i = 1; i <= n; i++)
	{
		cin >> v[i][0];			//用v[i][0]存储每组物品的数量
		for (int j = 1; j <= v[i][0]; j++)
		{
			cin >> v[i][j] >> w[i][j];
		}
	}

	for (int i = 1; i <= n; i++)
	{
		for (int j = V; j > 0; j--)
		{
			for (int k = 1; k <= v[i][0]; k++)
			{
				if (j - v[i][k] >= 0)
					f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
			}
		}
	}

	cout << f[V] << endl;
	return 0;
}