背包笔记整理

常规
1

万物皆可dp

背包

背包的范围实在是太广了， 对我这种普及组的蒟蒻来说，真的只知道 01背包， 完全背包， 多重背包 或者是其他乱七八糟的 杂背包

01背包

所谓01背包， 背包的状态就只有0和1， 即一件物品只有拿和不拿两种状态。我们定义 f[i][j] 表示当前遍历到第 i 件物品， 所剩的背包容量为 j 。由此可以得出状态转移方程

f[i][j] = \max(f[i-1][j], f[i-1][j-w[i]]+v[i])

其中 f[i-1][j] 表示不拿当前这个物品， 故背包容量不变， 背包内总价值继承 当前物品的上一个物品 的总价值。 而 f[i-1][j-w[i]]+v[i] 表示拿当前物品， 故背包容量减去第 i 个物品的质量 w[i] ， 包内总价值加上第 i 件物品的价值 v[i] 。

c++模板：

for(int i = 1; i <= n; i ++)//枚举物品
{
    for(int j = w[i]; j <= m; j ++)//枚举背包容量，j要大于w[i]，不然放不下这个物品
	{
        f[i][j] = max(f[i-1][j], f[i-1][j-w[i]] + v[i]);
	}
}

细心的你可能发现了， 无论我们对当前物品的操作是拿还是不拿， 转移方程的转来方向第一维总是 i-1 ， 也就是说， 枚举到当前物品的状态只能由 上一件物品 转移过来， i-1 之前的物品都不会参与转移， 浪费了许多空间， 那怎么办呢？当我听说要压缩一维的时候， 第一反应就是把dp数组定义为 f[2][N] ， 但结果竟是…

for(int i = 1; i <= n; i ++)//枚举物品
{
    for(int j = m; j >= w[i]; j --)//枚举背包容量
	{
        f[j] = max(f[j], f[j-w[i]] + v[i]);
	}
}

没想到吧， 第二维要 倒序遍历！

在 f[i][j] = \max(f[i-1][j], f[i-1][j-w[i]]+v[i]) 中， 第二维永远从容量小于等于j的地方转移过来， 如果我们把第二维顺序遍历， f[1]...f[j-1] 会先存到遍历到当前这个物品的最大价值， 从二维的转移方程来看就变成了 f[i][j] = \max(f[i][j], f[i][j-w[i]]+v[i]) 。也就是说， 顺序遍历时的 f[j] 一旦确定就会影响到 f[j] 之后的状态。而倒序遍历就可以规避这种情况。因为当 f[j] 往前取时， f[j-w[i]] 还保存着 i-1 时的状态， 这就符合上文的状态转移方程了。

完全背包

和01背包不同， 完全背包问题中，每个物品都可以取无限个， 也就是 f[i][j] 可以从自己的状态转移过来， 即 f[i][j-w[i]]+v[i] ， 那么状态转移方程就是

f[i][j] = \max(f[i][j], f[i-w[i]]+v[i])

嗯？有点眼熟？这不就是顺序做第二维的01背包压维的“错误”写法吗？那代码还不好写？

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

这样看来， 完全背包的代码和01背包也就差了一维是顺序还是倒序嘛。

多重背包

多重背包也是01背包的一个变式， 区别在于多重背包里每一个物品可以取 k 个， 那么状态转移方程也就 顺理成章 地出来了

f[j] = \max(f[j], f[j-w[i]\times k]+v[i]\times k)

然而，我们并不确定 k 件物品是否全部要取， 因此我们还要开一重循环来枚举 k

上代码:

for(int i = 1; i <= n; i ++)
{
	for(int j = m; j >= 0; j --)
	{
		for(int u = 1;  u <= k[i] && u * v[i] <= j; u ++)//枚举取的个数
		{
			if(j >= u * w[i])
				f[j] = max(f[j], f[j-w[i]*k]+v[i]*k);
		}
	}
}

不难发现， 当 u 的数据量级与 n, m, 同级时， 算法的复杂度就到了 O(n^3), 我们就要考虑恶心的优化问题了。

提供一种经典的优化方法：对 k 进行二进制拆分，如当 k=10 时， k 被拆分为 1, 2, 4, 3 接着把$vi\times ki$ 分别存入 v[++cnt] 中，$w$ 数组同理操作， 多重背包就被我们转化成了简单的01背包问题：

for(int i = 1; i <= n; i ++)
{
    int k = 1;
    while(k <= mi)
    {
        mi -= k;
        v[++cnt] = vi*k;
        w[cnt] = wi*k;
        k *= 2;
    }
    if(mi > 0)
    {
        v[++cnt] = vi * mi;
        w[cnt] = wi * mi;
    }
}
//二进制拆分

for(int i = 1; i <= cnt; i ++)//正常的01背包问题
{
    for(int j = bag; j >= w[i]; j --)
    {
        f[j] = max(f[j], f[j-w[i]] + v[i]);
    }
}

总结

背包问题是经典的动态规划问题， 我们在做背包问题时要注意观察题目中的 v[i] 和 w[i] 分别代表那一些量， 判断题目所属的背包类型， 清晰的思路是做好题目的前提！

2 个赞