多重背包问题

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

题目描述

有 N 种物品和一个容量是 V 的背包。
第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。

输入描述

第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。
接下来有 N 行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i 种物品的体积、价值和数量。

输出描述

输出一个整数，表示最大价值。
0<N≤1000
0<V≤2000
0<vi,wi,si≤2000

示例

输入

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

输出

10

分析

约定

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

状态表示

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

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

状态划分

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

• 没选第i件物品
• 选了第i件物品，要考虑选了几件，1、2、3直到上限都应该考虑

状态转移方程

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

• f(i,j)=f(i-1,j)
• f(i,j)=max(f[i-1][j-k*v[i]]+k*w[i])   (k*v[i]<=j,k<=s[i])

注意，第二行方程中的第一维为i-1，因为该种大情况将选了几件第i件物品剥离开再求和处理的。

显然，我们要取的f(i,j)应当是两大种情况的最大值，将二者形式统一，最终的状态转移方程如下：
f(i,j)=max(f(i-1,j-k*v[i])+k*w[i])   (k*v[i]<=j,k<=s[i])

总结与思考

对于多重背包问题，基本的解决思路与完全背包相同，这时我们会理所当然向着完全背包的优化思路上走，究竟行不行呢？我们来试一试。
按照完全背包的优化思路，我们寻找状态转移方程的特性：

• f(i,j)=max(f(i-1,j),f(i-1,j-v[i])+w[i],f(i-1,j-2*v[i])+2*w[i],f(i-1,j-3*v[i])+3*w[i],···,f(i-1,j-s[i]*v[i])+s[i]*w[i])
• f(i,j-v[i])=max(f(i-1,j-v[i]),f(i-1,j-2*v[i])+w[i],f(i-1,j-3*v[i])+2*w[i],···,f(i-1,j-s[i]*v[i])+s[i]*w[i],f(i-1,j-(s[i]+1)*v[i])+(s[i]+1)*w[i])

注意加粗部分，完全背包中加粗部分项数一致，每项均差w[i]，但观察上面两个式子，项数是不一致的，无法得到下面的状态转移方程：
f(i,j)=max(f(i-1,j)+f(i,j-v[i])+w[i])   (j-v[i]>=0)
因此，老的优化思路是走不通的。

二进制优化

二进制优化是多重背包的一个经典优化方法。
对于第i件物品，我们将其分组为1、2、4、8、···、2^n，最后一组如果不够2的整数次幂则直接单算一组。
易证，对于任意选择小于等于s[i]件第i件物品的方案，都可以通过上述分组的组合等价得到。
将上述每一个分组都当作一个物品，该物品体积为该组物品体技之和，价值为该组物品价值之和，这样就将多重背包问题转化为了0-1背包问题，从而将时间复杂度从NVS降低到了NVlogS(大致表示)。

朴素解法AC代码

---

#include <iostream>
#include <algorithm>

using namespace std;

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

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

	for (int i = 1; i <= n; i++)
		cin >> v[i] >> w[i] >> s[i];

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

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

二进制优化AC代码

---

#include <iostream>
#include <algorithm>

using namespace std;

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

int main()
{
	cin >> n >> V;
	int cnt = 0;
	for (int i = 1; i <= n; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		int k = 1;
		while (k <= c)
		{
			cnt++;
			v[cnt] = k * a;
			w[cnt] = k * b;
			c -= k;
			k *= 2;
		}
		if (c)
		{
			cnt++;
			v[cnt] = c * a;
			w[cnt] = c * b;
		}
	}
	n = cnt;
	for (int i = 1; i <= n; i++)
	{
		for (int j = V; j >= v[i]; j--)
		{
			f[j] = max(f[j], f[j - v[i]] + w[i]);
		}
	}

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