多重背包问题
有限制的选择:在n个物品中选择总体积不超过V的物品,使得所有物品的价值最大.与01背包不同的是
每个物品可以选择0~si次.
样例
输入样例:
N V
4 5
i|vi wi si
1|1 2 3
2|2 4 1
3|3 4 3
4|4 5 2
输出样例:
10
样例解释:
选择3个物品1和1个物品2
朴素dp
解题思路
dp
状态定义
dp[i][j]
集合:选择总体积不超过j的前i个物品的所有方案
属性Max
举例:dp[2][4]
集合:{ {},{1},{1,1},{1,1,1},{1,2},{1,1,2},{2} }
属性:8
状态划分
f[i-1][j']的状态取决于第i个物品的选择,多重背包问题在完全背包的基础上有加上一个
限制即 0<=k<=min(s[i],j/vi).那么j' = j - k * vi. 之所以这么选因为集合的属性是Max,
而选择k个物品已经是确定的,那么可变部分为满足属性要选最大,所以j'选择满足条件的最大值,而dp[i-1][j']
也是按照符合Max属性推导而来的,所以可变部分的最大就是dp[i-1][j'].
用递推式表示:
dp[i][j] = max(dp[i-1][j], dp[i-1][j-vi]+wi, dp[i-1][j-2vi]+2wi, .... )
= max( dp[i-1][j-k*vi]+k*wi)(0<=k<=min(s[i],j/vi))
(思路和完全背包基本相同,只是加入了s[i]的限制).
时间复杂度
状态个数 * 状态转移 = nV * S = 1e3 * 2e3 * 2e3 = 4e9 超时
C++ 代码
#include<iostream>
#include<algorithm>
using namespace std;
const int Max_N = 1e3 + 10;
const int Max_M = 2e3 + 10;
int n, m;
int v[Max_N], w[Max_N], s[Max_N];
int dp[Max_N][Max_M];
int main()
{
cin >> n >> m;
for( int i=1; i<=n; i++ ) cin >> v[i] >> w[i] >> s[i];
for( int i=1; i<=n; i++ )
{
for( int j=0; j<=m; j++ )
{
for(int k=0; k<=j/v[i]&&k<=s[i]; k++ )
{
dp[i][j] = max( dp[i][j], dp[i-1][j-k*v[i]]+k*w[i] );
}
}
}
cout << dp[n][m] << endl;
return 0;
}
二进制优化
解题思路
1.为什么不能用完全背包的方式优化:
观察多重背包递推式
dp[i][j] = max(dp[i-1][j],dp[i-1][j-v]+w,dp[i-1][j-2v]+2w,...,dp[i-1][j-sv]+sw
dp[i][j-v] = max( dp[i-1][j-v] ,dp[i-1][j-2v]+w ,...,dp[i-1][j-sv]+(s-1)w + dp[i-1][j-(s+1)c=v]+sw )
可以看到两个式子基本一样,但蛋疼的是dp[i][j-v]多了一项dp[i-1][j-(s+1)v]+sw,也就是容量为
j-v的背包最多也能选s个物品(在体积条件满足时),这就是无法用完全背包优化的方式优化.
2.二进制优化以及为什么能用二进制优化:
2.1优化思路是把完全背包问题转变为01背包问题.最暴力的思路就是把第i个物品拆分成si份.但这么做
对时间复杂度没有影响.
这时神奇的二进制登场,对si快速拆分.
以si = 7为例,我们可以将i拆分成:
(v,w);(2v,2w),(4v,4w)三个物品,也就是说1,2,4可以构成[1,7]间任意一个数
首先1可以构成 0~1 加入2后 -> 2~3 取并集->
0~3 -> 加入4后 -> 4~7 取并集0~7.
简单理解就是0~7的二进制表示对应为1的位选取对应属性的物品.再看一个一般性的数
设S可以拆分成1,2,4, ..., 2^k, c. 其中0<=c<2^(k+1) 因为如果c>=2^(k+1) 那么s的拆分成
1,2,4,...,2^(k+1),c;即我们设这里的k是可以取到的最大的2次幂
那么对于1 ~ 2^k 我们用上面的思路知道能构成 0~2^(k+1)-1
-> 加上c后 构成c~S .那么关键就是0~2^(k+1)-和c~S的并集能否覆盖0~S. 而c<2^(k+1)<=2^(k+1)-1,所以当然可以啦.
2.2那么如何理解用二进制拆分si后就转换成了01背包问题,或者也许你会疑惑为什么这样拆分后就考虑了所有
可能呢?
举个简单的例子,输入1个物品,最多选S个.用上述思路将S拆分成1,2,...,2^k,c(c>0时考虑)
因为01背包考虑的是每个i物品的选与不选,也就是对应拆分项选和不选在01背包的过程中都考虑
了一遍,在这个过程中自然S的所有可能都考虑到了.
对拆分理解不够的时候想到另一个拆分方式
while( s )
if( s&1 )
vi = v*2^k
wi = w*2^k
s >>= 1
k++
类似于快速幂的思想.当时非常开心以为想到一个新方法.但这种办法就不可以保证能凑成0~s.
时间复杂度
si->logsi , 时间复杂度从 NVS -> NVlogs = 1e3 * 2e3 * log(2e3) 约为2e7
C++ 代码
#include<iostream>
#include<algorithm>
using namespace std;
const int Max_N = 1010 * 11;//保存s拆分后的物品
const int Max_M = 2e3 + 10;
int n, m;
int v[Max_N],w[Max_N];
int dp[Max_M];
int main()
{
cin >> n >> m;
int cnt = 0;
for( int i=1; i<=n; i++ )
{
int v_, w_, s_;
cin >> v_ >> w_ >> s_;
int k = 1; //2^k
while( k<=s_ )
{
cnt++;
v[cnt] = k * v_;
w[cnt] = k * w_;
s_ -= k;
k *= 2;
}
if( s_>0 )
{//剩余值c>0
cnt++;
v[cnt] = s_ * v_;
w[cnt] = s_ * w_;
}
}
n = cnt;
for(int i=1; i<=n; i++ )
{
for( int j=m; j>=v[i]; j-- )
{
dp[j] = max( dp[j], dp[j-v[i]]+w[i] );
}
}
cout << dp[m] << endl;
return 0;
}