多重背包

前言

多重背包问题，和完全背包问题相比，其实就是每个物品可以取的数目是限定的。

一、经典多重背包

有 n(n ≤ 100)种物品和一个容量为 m(m ≤ 10000) 的背包。第 i 种物品的容量是 c[i]，价值是 w[i]。现在需要选择一些物品放入背包，每种物品可以选择 x[i] 件，并且总容量不能超过背包容量，求能够达到的物品的最大总价值。

1、状态设计

状态(i, j)表示前i种物品恰好放入容量为j的背包 (0 ≤ i < n，0 ≤ j ≤ m)；

令dp[i][j]表示状态(i, j)下该背包得到的最大价值，即前i种物品（每种物品可以选择x[i]件）恰好放入容量为j的背包所得到的最大总价值；

2、状态转移方程

dp[i][j]=max(dp[i−1][j−c[i]×k]+w[i]×k)   (0≤k≤x[i])dp[i][j]=max(dp[i-1][j-c[i] \times k]+w[i] \times k) \ \ \ (0 \le k \le x[i])

因为每种物品有x[i]种可放置，将它归类为以下两种情况：

1）不放：如果 “第 i 种物品不放入容量为 j 的背包”，那么问题转化成求 “前 i-1 种物品放入容量为 j 的背包” 的问题；由于不放，所以最大价值就等于 “前 i-1 种物品放入容量为 j 的背包” 的最大价值，对应状态转移方程中k = 0的情况， 即dp[i-1][j]；

2）放 k 个：如果 “第 i 种物品放入容量为 j 的背包”，那么问题转化成求 “前 i-1 种物品放入容量为 j-c[i]*k 的背包” 的问题；那么此时最大价值就等于 “前 i-1 种物品放入容量为 j-c[i]*k 的背包” 的最大价值加上放入 k 个第 i 种物品的价值，即 dp[i-1][j - c[i]*k] + w[i]*k；

枚举所有满足条件的 k 就是我们所求的 “前 i 种物品恰好放入容量为 j 的背包” 的最大价值。

3、对比 0/1 背包、完全背包问题

多重背包问题是背包问题的一般情况，每种物品有自己的值域限制。如果从状态转移方程出发，我们可以把三种背包问题进行归纳统一，得到一个统一的状态转移方程如下：

dp[i][j]=max(dp[i−1][j−c[i]×k]+w[i]×k)dp[i][j]=max(dp[i-1][j-c[i] \times k]+w[i] \times k)

对于 0/1 背包问题，k 的取值为 0,1；

对于完全背包问题，k 的取值为

0,1,2,3,...,⌊jc[i]⌋0,1,2,3,..., \left \lfloor \frac{j}{c[i]} \right \rfloor

对于多重背包问题，k 的取值为

0,1,2,3,...,x[i]0,1,2,3,...,x[i]

4、时间复杂度分析

对于 n 种物品放入一个容量为 m 的背包，状态数为 O(nm)，每次状态转移的消耗为 O(x[i])，所以整个状态转移的过程时间复杂度是大于O(nm) 的，那么实际是多少呢？

考虑最坏情况下，即x[i] = m时，那么要计算的 dp[i][j] 的转移数为 j，总的状态转移次数就是 m(m+1)/2，所以整个算法的时间复杂度是 O(nm^2) 的。

显然不够高效对吧？那接下来就是传统艺能了（）

二、多重背包问题的优化

1、空间复杂度优化

一个容易想到的优化是：我们可以将每种物品拆成x[i]个，这样变成了

∑i=1nx[i]\sum_{i=1}^{n}x[i]

个物品的 0/1 背包问题，我们知道 0/1 背包问题优化完以后，空间复杂度只和容量有关，即 O(m)。

有十分甚至九分的简洁（）

2、时间复杂度优化

然而， 如果这样拆分，时间复杂度还是没有变化，但是给我们提供了一个思路，就是每种物品是可以拆分的。

假设有 x[i] 个物品，我们可以按照 2 的幂进行拆分，把它拆分成：

1,2,4,...,2k−1,x[i]−2k+11,2,4,...,2^{k-1},x[i]-2^{k}+1

其中 k 是最大的满足 $$x[i]-2^{k}+1 \ge 0$$ 的非负整数。

这样，1 到 x[i] 之间的所有整数都能通过以上k+1 个数字组合出来，所以只要拆成以上 k+1 个物品，所有取 k (0 ≤ k ≤ x[i]) 个物品的情况都能被考虑进来。

举例说明，当 x[i] = 14 时，可以拆分成 1,2,4,7 个物品，那么当我们要取 13 个这类物品的时候，相当于选择 2、4、7，容量分别为 c[i]*2, c[i]*4, c[i]* 7, 价值分别为 w[i]*2, w[i]*4, w[i]*7。

通过这种拆分方式，x[i] 最多被拆分成 log x[i] 个物品，然后再用 0/1 背包求解，时间复杂度如下：

O(m∑i=1nlog2x[i])O(m\sum_{i=1}^{n}log_{2}x[i] )

啊~果然优化过后的就是舒服呢❤

三、题目

这问题真不好找，在各种OJ平台找了半天没有一道经典题或直接变式，都需要夹带私货……下面这道也一样。

Eden 的新背包问题 - 洛谷

失忆的 Eden 总想努力地回忆起过去，然而总是只能清晰地记得那种思念的感觉，却不能回忆起她的音容笑貌。

记忆中，她总是喜欢给 Eden 出谜题：在 valentine’s day 的夜晚，两人在闹市中闲逛时，望着礼品店里精巧玲珑的各式玩偶，她突发奇想，问了 Eden 这样的一个问题：有 n 个玩偶，每个玩偶有对应的价值、价钱，每个玩偶都可以被买有限次，在携带的价钱 m 固定的情况下，如何选择买哪些玩偶以及每个玩偶买多少个，才能使得选择的玩偶总价钱不超过 m，且价值和最大。

众所周知的，这是一个很经典的多重背包问题，Eden 很快解决了，不过她似乎因为自己的问题被飞快解决感到了一丝不高兴，于是她希望把问题加难：多次询问，每次询问都将给出新的总价钱，并且会去掉某个玩偶（即这个玩偶不能被选择），再问此时的多重背包的答案（即前一段所叙述的问题）。

这下 Eden 犯难了，不过 Eden 不希望自己被难住，你能帮帮他么？

一眼丁真，这题一看显然是个多重背包二进制拆分转成01背包，即上面提到的时间复杂度优化过后的多重背包。

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
31
32
33
34
35
36
37
38
39
40
41
42
#include<bits/stdc++.h>
using namespace std;
int n,m,c,ji,f[100005];
struct node{
	int s,id;
}w[100000],v[100000];
inline int read(){ //inline 是为了优化时间哦，RTFM please~
	register int x=0;
	register char ch=getchar();
	while(ch>'9'||ch<'0')ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return x;
}
int main(){
	cin>>n;
	for(register int i=1;i<=n;++i){
		register int cw=read(),cv=read(),c=read();
		register int now=1;
		while(now<=c){
			w[++ji].s=cw*now,v[ji].s=cv*now;
			w[ji].id=i,v[ji].id=i;
			c-=now,now*=2;
		}
		if(c){
			w[++ji].s=cw*c,v[ji].s=cv*c;
			w[ji].id=i,v[ji].id=i;
		}
	}
	cin>>m;n=ji;
	for(register int l=1;l<=m;++l){
		register int cn=read()+1,V=read();
		for(register int i=1;i<=n;++i){
			if(w[i].id!=cn){
				for(register int j=V;j>=w[i].s;--j){
					f[j]=max(f[j],f[j-w[i].s]+v[i].s);
				}
			}
		}
		printf("%d\n",f[V]);
		memset(f,0,sizeof(f));
	}
}

然后就TLE了。优化的方法很多，这里找了一位大犇的题解（官方题解页第一位）：

我们知道背包其实就是把每一种放法都考虑一遍，我们设的状态是f[i][j]表示考虑到第i个总体积为j的最大价值

而我们要求的是不考虑第i种物品时的最大价值

诶 这不就是f[i-1][V]么～～～

不对其实这样后面的物品就没有被考虑到

那怎么办呢

于是我们可以从后往前再DP一次表示从后面往前面考虑的最大价值

把两个背包的结果合并就是所求啦

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,m,c,ji;
ll f1[100005][1005],f2[100005][1005];
struct node{
    int id;ll s;
}w[300005],v[300005];
inline int read(){
	register int x=0;
	register char ch=getchar();
	while(ch>'9'||ch<'0')ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return x;
}
int main(){
	cin>>n;
	for(register int i=1;i<=n;++i){
		register int cw=read(),cv=read(),c=read();
		register int now=1;
		while(now<=c){//二进制拆分，不懂的可以记住
			w[++ji].s=cw*now,v[ji].s=cv*now;
            w[ji].id=i,v[ji].id=i;
			c-=now,now*=2;
		}
		if(c){
			w[++ji].s=cw*c,v[ji].s=cv*c;
            w[ji].id=i,v[ji].id=i;
		}//拆分结束
	}
	cin>>m;
	n=ji;//更新物品数量
	for(int i=1;i<=n;i++){//正向01背包
		for(int j=0;j<=1000;j++)f1[i][j]=f1[i-1][j];
		for(int j=1000;j>=w[i].s;j--){
			f1[i][j]=max(f1[i][j],f1[i-1][j-w[i].s]+v[i].s);
		}
		
	}
	for(int i=n;i>=1;i--){//反向01背包
		for(int j=0;j<=1000;j++)f2[i][j]=f2[i+1][j];
		for(int j=1000;j>=w[i].s;j--){
			f2[i][j]=max(f2[i][j],f2[i+1][j-w[i].s]+v[i].s);
		}
		
	}
	for(int k=1;k<=m;k++){
		int cn=read()+1,V=read();
		ll ans=0;
        int l=0,r=0;//因为同一种物品可能已被拆成多件物品而这种物品都不能被考虑于是我们要找到不包括这种物品的f1和f2
        while(w[l+1].id<cn&&l<n)++l;
        r=l;
        while(w[r+1].id<=cn&&r<n)++r;
		for(int j=0;j<=V;j++){//这是枚举分配给该种物品之前的物品多少空间
			ans=max(ans,f1[l][j]+f2[r+1][V-j]);//不懂的可以拿样例模拟一下，温馨提示：样例可被拆分成9件物品
		}
		printf("%lld\n",ans);
	}
}
找到了好题目可以留在评论区哦~