背包

标签：件物品 容量 max leq 背包 物品

01背包

给定 \(n\) 件物品，每个物品有重量 \(w_{i}\) 和价值 \(c_{i}\)，一个物品只有一件，求容量不超过 \(m\) 的背包最多可以装多少价值物品

定义 \(f_{i,j}\) 表示前 \(i\) 件物品在容量不超过 \(j\) 的背包下可以获得的最大价值则有 \(f_{i,j}=\max\{f_{i-1,j},f_{i-1,j-w_{i}}+c_i\}\)

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

考虑优化空间复杂度，我们会发现对于一个 \(f_{i,j}\)，与其有关的状态 \(f_{x,y}\) 满足 \(x=i-1,y\leq j\)，所以不妨把表示物品件数的一维去掉然后倒序计算，因为结果只与容量小的那一部分有关。定义 \(f_j\) 表示在容量不超过 \(j\) 的背包中可以获得的最大价值，有\(f_j=\max\{f_j,f_{j-w_i}+c_i\}\)

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

---

完全背包

给定 \(n\) 件物品，每个物品有重量 \(w_{i}\) 和价值 \(c_{i}\)，一个物品有无限件，求容量不超过 \(m\) 的背包最多可以装多少价值物品

定义 \(f_{i,j}\) 表示前 \(i\) 件物品在容量不超过 \(j\) 的背包下可以获得的最大价值，有

\[f_{i,j}=\max\{f_{i-1,j},f_{i-1,j-k*w_i}+k*c_i\}, 0\leq k*c_i\leq j \]

其实就相当于把无限件转化为有限件做 01 背包

考虑优化，不妨看看 01 背包，定义 \(f_j\) 表示在容量不超过 \(j\) 的背包中可以获得的最大价值，有\(f_j=\max\{f_j,f_{j-w_i}+c_i\}\)，正好，顺序循环就可以了

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

---

多重背包

给定 \(n\) 件物品，每个物品有重量 \(w_{i}\) 和价值 \(c_{i}\)，一个物品有 \(s_i\) 件，求容量不超过 \(m\) 的背包最多可以装多少价值物品

定义 \(f_{i,j}\) 表示前 \(i\) 件物品在容量不超过 \(j\) 的背包下可以获得的最大价值，首先考虑像没有优化的完全背包一样暴力枚举取多少件当前物品，有

\[f_{i,j}=\max\{f_{i-1,j},f_{i-1,j-k*w_i}+k*c_i\}, 0\leq k\leq s_i \]

考虑优化，不妨将 \(s_i\) 拆分成 \(\{2^0,2^1,2^2,...,2^{k-1},s_i-2^k+1\}\) 件物品，其中 \(k\) 是满足 \(s_i-2^k+1>0\) 的最大整数，去做 01 背包，这样在凑的途中可以凑出 \([0,s_i]\) 中的正整数

标签：件物品,容量,max,leq,背包,物品
From： https://www.cnblogs.com/chelsyqwq/p/17625704.html