多重背包

每件物品的个数有限制

朴素算法

与完全背包的朴素算法类似 时间复杂度 O ( N ∗ V ∗ S ) O(N*V*S) O(NVS)

状态转移方程 f [ i ] [ j ] = m a x ( f [ i ] [ j ] , f [ i − 1 ] [ j − k ∗ v [ i ] ] + k ∗ w [ i ] ) f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]) f[i][j]=max(f[i][j],f[i1][jkv[i]]+kw[i])

优化成一维时需要从大到小枚举 j j j

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

二进制优化

先对s件物品分组,再做01背包问题 时间复杂度 O ( N ∗ V ∗ l o g 2 S ) O(N*V*log_{2}S) O(NVlog2S)

s分组成: 1 , 2 , 4 , 8 , 16... 2 k , s − 2 k + 1 1,2,4,8,16...2^{k},s-2^{k+1} 1,2,4,8,16...2k,s2k+1 可以证明 0 − s 0-s 0s的每一个数都可以被以上数字表示出来 所以01背包对于每组物品的的选与不选 就表示所有可能的s的取值

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

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