背包问题

简介

背包问题（英语：Knapsack problem）是一种组合优化的NP完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中，背包的空间有限，但我们需要最大化背包内所装物品的价值。背包问题通常出现在资源分配中，决策者必须分别从一组不可分割的项目或任务中进行选择，而这些项目又有时间或预算的限制。

背包问题历史悠久，甚至可以追溯到1897年。“背包问题” 一词最早出现于数学家托比阿斯·丹齐格的早期研究中，他研究的问题是如何打包行李，要求最大化所选行李的价值且不能超载。

背包问题出现在现实世界很多领域的决策过程中，诸如寻找节约原料的生产方式、选择投资项目及投资组合、选择证券化的资产以及为默克尔-赫尔曼和其他背包密码系统生成密钥。

背包问题中基础的大致分为一下几类：

0-1背包

解释

例题中已知条件有第 $i$ 个物品的重量 $w_i$ ，价值 $v_i$ ，以及背包的总容量 $W$。

设 DP 状态 $f_{ i , j }$ 为在只能放前 $i$ 个物品的情况下，容量为 $j$ 的背包所能达到的最大总价值。

考虑转移。假设当前已经处理好了前 $i-1$ 个物品的所有状态，那么对于第 i 个物品，当其不放入
背包时，背包的剩余容量不变，背包中物品的总价值也不变，故这种情况的最大价值为 $f_{i-1, j}$ ；当
其放入背包时，背包的剩余容量会减小 $w_i$，背包中物品的总价值会增大 $v_i$ ，故这种情况的最大价
值为 $f_{i-1,j-w_{i}} + v_i$ 。由此可以得出状态转移方程：

$$
f_{i,j}= max(f_{i-1,j},f_{i-1,j-w_{i}}+ v_i)
$$

这里如果直接采用二维数组对状态进行记录，会出现 MLE。可以考虑改用滚动数组的形式来优
化。（将二维数组优化写成一维数组）

由于对 $f_i$ 有影响的只有 $f_{i-1}$，可以去掉第一维，直接用 $f_i$ 来表示处理到当前物品时背包容量为 $i$
的最大价值，得出以下方程:

$$
f_j=max(f_j, f_{j-w_{i}} + v_i)
$$

核心代码：

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

需要注意的是，第二个循环的枚举的顺序是从 $W$ 枚举到 $w_i$ 。为什么呢？

如果从 $w_i$ 枚举到 $W$ 在 $j>w_i$ 时，$f_{i,j}$ 是会被 $f_{i,j-w_{i}}$所影响的，如果前面 $f_{i,j-w_{i}}$ 放入物品 $i$ 是价值更大，我们会将其放入并更新，在后面 $f_{i,j}$ 时如果再次选择放入会用到 $f_{i,j}$ 这就相当于物品 $i$ 可以多次被放入背包，与题意不符。（事实上，这正是完全背包问题的解法）。

如果二维 DP 不会爆 MLE 我们也可以用二维 DP 来处理，此时第二个循环的枚举顺序不影响结果，因为对于任意的 $f_{i,j}$ 并不会修改 $f_{i-1,j}$ 或者 $f_{i-1,j-w_{i}}$ 的结果。代码如下：

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

完全背包

解释

完全背包模型与 0-1背包 类似，与 0-1背包 的区别仅在于一个物品可以选取无限次.。

我们可以借鉴 0-1背包的思路，进行状态定义：设 $f_{i,j}$ 为只能选前 $i$ 个物品时，容量为 $j$ 的背包可
以达到的最大价值。

可以考虑一个朴素的做法：对于第 $i$ 件物品，枚举其选了多少个来转移。这样做的时间复杂度是
$O(n^3)$ 的。状态转移方程如下：

$$
f_{i,j} = \max_{k=0}^{+\infty}(f_{i-1,j-k*w_{i}}+v_{i}*k)
$$

考虑做一个简单的优化。可以发现，对于 $f_{i,j}$ ，只要通过 $f_{i,j-w_{i}}+v_{i}$ 转移就可以了。当我们这样转移时，$f_{i,j-w_{i}}$ 已经由 $f_{i,j-2*w_{i}}$ 更新过，那么 $f_{i,j-w_{i}}$ 就是充分考虑了第i件物品
所选次数后得到的最优结果。换言之，我们通过局部最优子结构的性质重复使用了之前的枚举过
程，优化了枚举的复杂度。因此状态转移方程为:

$$
f_{i,j}= max(f_{i-1,j}, f_{i-1,j-w_{i}}+ v_i)
$$

与 0-1背包相同，我们可以将第一维去掉来优化空间复杂度。

核心代码：

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

多重背包

解释

多重背包是 0-1背包的一个变式。与 0-1背包的区别在于每种物品有 $k_i$ 个，而非一个。

一个很朴素的想法就是：我们把 $k_i$ 个相同的物品看成 $k_i$ 个重量价值相同但是不同的物品，即对 $\sum_{i=1}^{n} k_{i}$ 个物品做 0-1背包。

时间复杂度 $O(W \sum_{i=1}^{n} k_{i})$ 。

核心代码：

for (int i = 1; i <= n; i++)
{
    for (int weight = W; weight >= w[i]; weight--)
    {
        // 多遍历一层物品数量
        for (int k = 1; k * w[i] <= weight && k <= cnt[i]; k++)
        {
            dp[weight] = max(dp[weight], dp[weight - k * w[i]] + k * v[i]);
        }
    }
}

二进制分组优化

显然，复杂度中的 $O(nW)$ 部分无法再优化了，我们只能从 $O(\sum_{i=1}^{n} k_{i})$ 处入手。

为了表述方便，我们用 $A_{i,j}$ 代表第 $i$ 种物品拆分出的第 $j$ 个物品。

在朴素的做法中，$\forall j \le ki$ ，$A_{i,j}$ 均表示相同物品。那么我们效率低的原因主要在于我们进行了大量的重复性的工作。举例来说，我们考虑了同时选 $A_{i,1}$ ，$A_{i,2}$ 与同时选 $A_{i,2}$ ，$A_{i,3}$ 这两个完全等效的情况。这样的重复性工作我们进行了许多次。那么优化拆分方式就成为了解决问题的突破口。

我们可以通过二进制分组的方式使拆分方式更加优美。
具体地说就是令 $A_{i,j},(j\in [0,\lfloor log_2(k_i+ 1) \rfloor - 1])$ 分别表示由 $2^j$ 个单个物品捆绑而成的大物
品。特殊地，若 $ki+1$ 不是 $2$ 的整数次幂，则需要在最后添加一个由 $k_i-2^{\lfloor log_2(k_i+ 1) \rfloor - 1}$ 个单个物品捆绑而成的大物品用于补足。

例如：

• 8=1+2+4+1
• 18=1+2+4+8+3
• 31=1+2+4+8+16

显然，通过上述拆分方式，可以表示任意 $\le k_i$ 个物品的等效选择方式。将每种物品按照上述方式
拆分后，使用 0-1背包的方法解决即可。

时间复杂度 $O(W\sum_{i=1}^{n} log_2k_{i})$ 。

index = 0;
for (int i = 1; i <= m; i++)
{
    int c = 1, p, h, k;
    cin >> p >> h >> k;
    while (k > c)
    {
        k -= c;
        list[++index].w = c * p;
        list[index].v = c * h;
        c *= 2;
    }
    list[++index].w = p * k;
    list[index].v = h * k;
}

分组背包

解释

有 $i$ 件物品和一个大小为 $m$ 的背包，第 $i$ 个物品的价值为 $v_i$ ，体积为 $w_i$ 。同时，每个物品只属于一个组，同组内最多只能选择一个物品，求背包能装载物品的最大总价值。

其实是从在所有物品中选择一件变成了从当前组中选择一件，于是就对每一组进行一次 0-1 背包就可以了，再说一说如何进行存储。我们可以将t表示第k组的第i件物品的编号是多少，再用 $cnt$ 表示第 $k$ 组物品有多少个。

核心代码：

for (int k = 1; k <= ts; k++) // 循环每一组
{
    for (int i = m; i >= 0; i--)
    {
        for (int j = 1; j <= cnt[k]; j++) // 循环该组的每一个物品
        {
            if (i >= w[t[k][j]])
            {
                dp[i] = max(dp[i],dp[i - w[t[k][j]]] + c[t[k][j]]);
            }
        }
    }
}

混合背包

解释

混合背包是 0-1背包、完全背包以及多重背包的组合，会出现其中的几种背包。有些可以无限取，有些物品只可以取有限次。

把不同情况分开：

• 能无限选 → 按完全背包处理。
• 选择次数有限 → 按多重（0-1）背包处理。

分情况分别解决，最后合并即可。

for (int i = 1; i <= n; i++)
{
    if (是 0 - 1 背包)
    {
        //套用 0 - 1 背包代码;
    }
    else if (是完全背包)
    {
        //套用完全背包代码;
    }
    else if (是多重背包)
    {
        //套用多重背包代码;
    }
}

前言 · 背包问题九讲 · 看云 (kancloud.cn)