本文为大型题解集。

X1267 【例 9.11】 01 背包问题
X1272 【例 9.16】 分组背包

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

X1267 【例 9.11】 01 背包问题

here

设 $f_{i,j}$ 表示前 $i$ 个物品在限重为 $j$ 的情况下所能取得的最大价值。

状态转移方程：

f_{i,j}=max\{f_{i-1,j},f_{i-1,j-w_i}+c_i\}

其中， $w_i$ ， $c_i$ 指第 $i$ 号物品的费用与价值（后文不再赘述）。

code：

for(int i=1;i<=n;i++)//n为物品数，m为限重。以下不再赘述。
		for(int j=1;j<=m;j++)
			if(j>=w[i])
				f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+c[i]);
			else
				f[i][j]=f[i-1][j];

对于一个物品，它只有两种状态：选与不选。

对于 $ ⌈$ 前 $i$ 个物品在限重为 $j$ 的情况下所能取得的最大价值 $⌋$ 这个子问题，若仅考虑：

第 $i$ 个物品选，那前 $i$ 个物品在限重为 $j$ 的情况下的价值转化为前 $i-1$ 个物品在限重为 $j-w_i$ 的情况下所能取得的最大价值加此物品的价值。
第 $i$ 个物品不选，那前 $i$ 个物品在限重为 $j$ 的情况下的价值价值转化为前 $i-1$ 个物品在限重为 $j$ 的情况下所能取得的最大价值。

在此两种状态中，取最大值。

样例：

这是在样例下的状态表：

f | 0 1 2 3 4 5 6 7 8 9 10 j
--+----------------------
0 | 0 0 0 0 0 0 0 0 0 0 0
1 | 0 0 1 1 1 1 1 1 1 1 1
2 | 0 0 1 3 3 4 4 4 4 4 4
3 | 0 0 1 3 5 5 6 8 8 9 9
4 | 0 0 1 3 5 5 6 9 9 10 12
i

看一下各个状态是如何转移的。

问题：第 $2$ 层 for 循环能否逆序？ $1,2$ 层循环能否颠倒？

答案都是肯定的。

因为对于状态 $f_{i,j}$ 来言，它的状态只可能由 $[f_{i-1,0}~f_{i-1,j}]$ 转移来。

就像这样：

f | 0 1 2 3 4 5 6 7 8 9 10 j
--+----------------------
0 |
1 |
2 | 0 0 0 0 0 0 0
3 |             ?<= 
4 | 
i

逆序、颠倒都保证这个矩阵能提前求出。

思考：第 $2$ 层 for 循环逆序同时两层循环颠倒是否可行？

时间复杂度与空间复杂度皆为 $O(nm)$ ，时间复杂度已无法优化，但空间复杂度可降为 $O(m)$ 。

前文提到，要求 $f_{i,j}$ ，只要知道 $[f_{i-1,0},f_{i-1,j}]$ 即可。

所以，可以进行滚动数组优化，将 $i$ 的那一维打掉，循环时可以滚动地一层一层覆盖数组的值~~降维打击~~。

code：

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

问题：第 $2$ 层 for 循环能否逆序？

答案是否定的。

因为，

要求 $f_{i,j}$ ，只要知道 $[f_{i-1,0},f_{i-1,j}]$ 即可

若为正向，则 $[f_{i-1,0},f_{i-1,j}]$ 已被改变，影响了递推。

其实，利用这个 $⌈$ 错误 $⌋$ ，可以求解完全背包。

思考： $1,2$ 层循环能否颠倒（不考虑 CE）？

X1272 【例 9.16】分组背包

code：

for(int i=1;i<=t;i++)//组数
		for(int j=m;j>=1;j--)
			for(int k=1;k<=num[i];k++)//各组内的物品
				if(j>=w[i][k])
					f[j]=max(f[j],f[j-w[i][k]]+c[i][k]);

这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。

内层的循环保证了每组中物品只会选一件。

问题：能否让第 $2$ 层循环作为第 $3$ 层循环？

答案是否定的。

这样就相当于先枚举所有物品，再枚举容量，变成了 01 背包。

思考：各层循环能否逆序？

本文作者：Yurchiu

本文链接：https://yz-hs.github.io/21589395ecd5/

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

OI 动态规划背包

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

By Yurchiu.

随机文章回味旧文

博客信息

文章数目

158

背包问题系列题解 I

X1267 【例 9.11】 01 背包问题

X1272 【例 9.16】 分组背包

X1272 【例 9.16】分组背包