均从以下角度考虑问题:状态表示(集合,集合属性),状态计算。
分享中$~k~$默认是整数。
01背包
状态表示
集合
发现题中变量有两个:物品和已选物品体积,两者影响已选物品价值。因此,用$~f[i][j]~$表示用小于等于 j 的体积装前 i 个物品的所有装法。
集合属性
显然为最大值。
状态计算
首先对$~f[i][j]~$进行集合划分,其蕴含的所有装法中可以分为两种:1.选第 i 个物品的,2.不选的。
于是可以得出转移方程
$$f[i][j] = \mathrm{max}(f[i - 1][j],~f[i - 1][j - v[i]] + w[i]$$
发现对于$~f[i][j]~$的计算,需要用到$~f[0–>i-1][0–>j-1]~$的一些数据,故须递推。
一维优化
我们发现,$~f[i][…]~$只使用了$~f[i - 1][…]~$的值,而我们不需要看过程产生的值,只需要看$~f[n][…]~$,也就是说,我们可以用滚动数组优化。
即用$~f[j]~$表示用小于等于 j 的体积最多装多大价值。
滚动数组是对空间优化的一种方式,即每次都使用固定的几个存储空间储存,用新的数据不断覆盖旧的数据,从而降低空间复杂度(甚至时间),多用于dp
注意:压缩后体积 $j$ 应当从最高往最低枚举
我们在看$~f[j]~$时,需要用到 j “左边”的且为更新前的部分数据,所以我们不能先更新左边,先从右边更新。
注:读者若不理解可以自己模拟
核心代码
朴素解法:
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= V; j ++ )
{
f[i][j] = f[i - 1][j];
if (j >= v[i])
f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
}
一维优化:
for (int i = 1; i <= n; i ++ )
for (int j = V; j >= v[i]; j -- )
f[j] = max(f[j], f[j - v[i]] + w[i]);
请思考:为什么朴素解法中 j 枚举范围是 1 - V,而优化后是 V - v[i]呢?
完全背包
完全背包和01背包只有状态计算上不同,其余不多赘述。
我们发现,第 i 个物品可以不选,也可以选 1 个,2 个,直到不能多选一个,于是得到转移方程:
$$f[i][j] = \mathrm{max}(f[i - 1][j - k\times v[i]] + k\times w[i])~~~~ ~0\le k\le ⌊\frac{j}{v[i]}⌋,~k\in \mathbb{Z}$$
优化
观察$~f[i][j]~$与$~f[i][j-v[i]]~$的关系,发现:
$$f[i][j] = \mathrm{max}(f[i-1][j],~f[i-1][j-v[i]]+w[i],~f[i-1][j-2v[i]]+2w[i],…)$$
$$f[i][j - v[i]] = \mathrm{max}(f[i-1][j - v[i]],~~~f[i-1][j-2v[i]]+w[i],…)$$
发现了上面同列之间只差$~w[i]~$,故易得新方程:
$$f[i][j] = \mathrm{max}(f[i - 1][j], f[i][j - v[i]] + w[i])$$
与01背包类似用滚动数组优化,不过01背包需要“左边”上一步的数据,这里需要本次处理的数据,故顺向枚举。
核心代码
朴素版
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= V; j ++ )
for (int k = 0; k <= j / v[i]; k ++ )
f[i][j] = max(f[i][j], f[i - 1][j - v[i] * k] + w[i] * k);
优化1
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= V; j ++ )
{
f[i][j] = f[i - 1][j];
if (j >= v[i])
f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);
}
优化2
for (int i = 1; i <= n; i ++ )
for (int j = v[i]; j <= V; j ++ )
f[j] = max(f[j], f[j - v[i]] + w[i]);
多重背包
朴素思路易知:
在01背包的基础上加一层for循环控制选择的个数即可
正确性易证,不赘述。
核心代码
for (int i = 1; i <= n; i ++ )
for (int j = 0; j <= V; j ++ )
for (int k = 0; k <= s[i] && k * v[i] <= j; k ++ )
f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
多重背包的二进制优化
在此之前,我们要知道一个结论:
任何一个正整数均可以被2的次幂的和表示出来
此结论二进制易证,即当数的二进制第 $k$ 位是 $1$ 时,就加 $2^{k-1}$
基于倍增思想,我们可以将$~s[i]~$分解为多个零碎的数目,它们是:
$$0, ~1, ~2, ~2^2, ~2^3, ~2^4, …, ~2^k, ~s[i] - 2^k$$
其中 k 是满足$~s[i] - 2 ^k \ge 0~$的最大值。
根据这些数据,我们可以构造出从 0 到 $~s[i]~$ 的所有数字。
读者可以自己举例验证。
至于如何组合这些数,我们只需要交给01背包即可。(将数据分成若干独立的“簇”)
由此,我们将时间复杂度降低到$~\mathrm O(nV\mathrm{log}_2s)~$,s 是所有种类个数之和。
这里同样可用一维优化,不赘述。
代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 25000;
// 2000 * log1000 ≈ 22000
int f[N], v[N], w[N];
int cnt;
int main()
{
int n, V;
cin >> n >> V;
while (n -- )
{
int a, b, c;
cin >> a >> b >> c;
int k = 1;
while (k <= c)
{
v[++ cnt] = k * a;
w[cnt] = k * b;
c -= k;
k *= 2;
}
if (c)
v[++ cnt] = c * a, w[cnt] = c * b;
}
for (int i = 1; i <= cnt; i ++ )
for (int j = V; j >= v[i]; j -- )
f[j] = max(f[j], f[j - v[i]] + w[i]);
cout << f[V];
return 0;
}
}
注意:数组要开大一些
分组背包
将一个组别看作一个整体,使用01背包的方式,对于第 i 组,再细分枚举即可。
代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110;
int v[N][N], w[N][N], cnt[N];
int f[N];
int main()
{
int n, V;
cin >> n >> V;
for (int i = 1; i <= n; i ++ )
{
cin >> cnt[i];
for (int j = 1; j <= cnt[i]; j ++ )
cin >> v[i][j] >> w[i][j];
}
for (int i = 1; i <= n; i ++ )
for (int j = V; j >= 1; j -- )
for (int k = 1; k <= cnt[i]; k ++ )
if (j >= v[i][k])
f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
cout << f[V];
return 0;
}