本文为大型题解集。

X1268 【例 9.12】 完全背包问题
X1269 【例 9.13】 庆功会
X1270 【例 9.14】 混合背包

一句话说的好：背包问题都可转化为 01 背包与分组背包问题。

X1268 【例 9.12】完全背包问题

here

每种物品的数量是无限的。

这个问题可以转化为 01 背包问题或分组背包问题。

01 背包

转化

每个物品肯定不能取无数件，最多取 $max_i=\lfloor m/w_i \rfloor$ 件（ $m$ ， $w$ 的意义已在前文提及）。

于是，将 $max_i$ 件物品看作独立的每一个物品，进行 01 背包。

优化：

二进制拆分。

前文的转化方法会耗费过高的时间和空间复杂度。

假设最多可以取 $5$ 个物品，只需转化为这三个物品即可：

$1$ 个单独物品， $2$ 个捆在一起的物品， $4$ 个捆在一起的物品。

因为，这 $3$ 捆物品可以表示出取了 $1$ 至 $5$ 之间的任何一个数量的物品。

即，只需储存 $\times2^0$ ， $\times2^1$ ， $\times2^2$ …， $\times2^{maxn_i}$ 的物品（ $maxn_i$ 在满足 $2^{maxn_i}<=max_i$ 条件下最大）！

这样，物品只有 $cnt$ 个（ $cnt$ 指拆分的物品总量）！

伪代码:

for(i : 1 -> n)
{
	read(tmpw,tmpc),max=m/a;
	for(maxn=0;pow(2,maxn)<=max;maxn++)
		cnt++,w[cnt]=a*pow(2,maxn),c[cnt]=b*pow(2,maxn);
}
01-背包();

时间复杂度： $O(nm \times \log^{NUM})$

分组背包

设有 $n$ 组物品，每组物品有 $max_i$ 个，编号 $1$ 至 $max_i$ ，费用、价值分别为 $w_i \times j$ ， $c_i \times j$ （ $j$ 指物品在此组的编号）。这样每组物品只能取一件。

进行分组背包。过于简单，不贴 CODE。

时间复杂度： $O(m \times NUM)$ 。

“美丽的错误”

	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]);

上边的 CODE 类似于 01 背包。只是内层循环变为正序。

前文提到过，这样会对后面的决策造成影响。

利用这种影响，恰恰可以解决完全背包：造成影响时，相当于又选了这个物品。

时间复杂度： $O(nm)$ 。

X1269 【例 9.13】庆功会

here。

多重背包。与上题一样，只是 $max_i=min(s_i,\lfloor m/w_i\rfloor)$ 。（ $s_i$ 指输入数据中的物品数）

X1270 【例 9.14】混合背包

here。

混合背包。与上题一样，只是 $max_i=\begin{cases} min(s_i,\lfloor m/w_i\rfloor)& s_i>0 \\\ \lfloor m/w_i\rfloor & s_i=0\end{cases}$ 。

本文作者：Yurchiu

本文链接：https://yz-hs.github.io/68a748aa690d/

版权声明：本博客中所有原创文章除特别声明外，均允许规范转载，转载请注明出处。所有非原创文章，按照原作者要求转载。

OI 动态规划背包

最后更新：2023-08-21, 23:18:21

By Yurchiu.

随机文章回味旧文

博客信息

文章数目

158

背包问题系列题解 II

X1268 【例 9.12】 完全背包问题