【专题】背包问题

导读

背包问题是动态规划中非常经典的一类问题，需要仔细地思考背包问题的每一个状态转移方程。

背包问题大致有以下几大类：

01背包问题
完全背包问题
多重背包问题
混合背包问题
二位费用的背包问题
分组背包问题
背包问题求方案数
求背包问题的方案
有依赖的背包问题

下面开始讨论背包问题的这些子问题：

*本文不会讨论后面三种子问题！

01背包问题

模板

有 $N$ 件物品和一个容量是 $V$ 的背包。每件物品只能使用一次。第 $i$ 件物品的体积是 $v[i]$，价值是 $w[i]$。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

解法分析

这是背包问题中最简单的一种子问题。其特点是: 每种物品仅有一件，可以选择放或不放。

我们首先确定状态：$f[i][j]$ 表示前 $i$ 个物品在背包容量 $j$ 的情况下能获得的最大价值。则其状态转移方程便是：$f[i][j]=std::max(f[i-1][j], f[i-1][j-v[i]]+w[i])$

这个方程非常重要，几乎所有的跟背包问题相关的问题的方程都是由它衍生出来的。希望读者能够完全理解它。

这里由于篇幅有限~~（其实就是懒）~~，给读者提供一个视频链接。这个老师讲的非常清楚。bilibili@codereasy 背包问题

本文将在上面的视频的基础上优化空间复杂度。

以上算法的时间复杂度为$O(N*V)$，空间复杂度也是$O(N*V)$。其中，时间复杂度已经基本不能再优化了，但是空间复杂度可以继续优化到$O(V)$。

在每一次第二维的循环中，$f[i][j]$ 是均由 $i-1$ 的状态得来的。$f[i][j]$ 与 $f[i-1][j]$ 是相互独立的。因此，我们可以考虑将 $i$ 这一维舍去。需要注意的是，舍弃掉第一维后，我们必须采用倒序循环的方式。如果仍然使用正序循环，那么就是从 $f[较小体积]$ 更新到 $f[较大体积]$。当循环到较大体积时，可能用的是第 $i$ 轮的状态而不是第 $i-1$ 轮的状态。

举个例子：当我们对一个体积为 $8$ 的物体进行决策时，$f[19]$ 应该由 $f[11]$ 更新得到。但此时的 $f[11]$ 却不是第 $i-1$ 轮的 $f[11]$ ，而是这一轮刚刚更新过的 $f[11]$ 。说的通俗一点，即 $f[11]$ 已经被污染了。而如果使用逆序循环，则不会有这样的问题。

最后，我们的状态转移方程就顺水推舟地写出来了：$f[j]=f[j-v[i]]+w[i]$

代码：

#include <iostream>
const int N = 39, M = 209;
int m, n;
int w[N], c[N], f[M];
// f[j] 表示 N 件物品，背包容量 j 下的最优解
int main()
{
    scanf("%d%d", &m, &n);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", w + i, c + i);
    for (int i = 1; i <= n; i++)
        for (int j = m; j >= w[i]; j--)
            f[j] = std::max(f[j], f[j-w[i]] + c[i]);
    printf("%d", f[m]);
    return 0;
}

例题：[NOIP2005 普及组] 采药

完全背包问题

模板

有 $N$ 种物品和一个容量是 $V$ 的背包，每种物品都有无限件可用。第 $i$ 种物品的体积是 $v[i]$，价值是 $w[i]$。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

解法分析

完全背包的状态转移方程可以由01背包的状态转移方程演变而来，即$f[i,j]=max\{f[i-1,j],f[i-1,j-v]+w,f[i-1,j-2*v]+2*w,f[i-1,j-3*v]+3*w,...\}$ 其中，$j>=k*v$

代码：

#include <iostream>
const int N = 1010;
int n, m, f[N][N], v[N], w[N];
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
		scanf("%d%d", v + i, w + i);
    for (int i = 1; i <= n; i++)
        for(int j = 0; j <= m; j++)
            for (int k = 0; k*v[i] <= j; k++)
                f[i][j] = std::max(f[i][j], f[i-1][j-k*v[i]] + k*w[i]);
	printf("%d", f[n][m]);
    return 0;
}

这样的代码可能会 TLE, 所以我们得想办法优化。

我们将两个方程放在一起看：

$f[i,j]=max\{f[i-1,j],f[i-1,j-v]+w,f[i-1,j-2*v]+2*w,f[i-1,j-3*v]+3*w,...\}$

$f[i , j-v]= max\{\qquad \ \ f[i-1,j-v] , f[i-1,j-2*v] + w , f[i-1,j-3*v]+2*w, ...\}$

将两方程整理后得到：$f[i][j]=max(f[i,j-v]+w,f[i-1][j]) $

那么，代码就可以优化成这样：

#include <iostream>
const int N = 1010;
int n, m, f[N][N], v[N], w[N];
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
		scanf("%d%d", v + i, w + i);
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= m; j++)
        {
            f[i][j] = f[i-1][j];
            if(j - v[i] >= 0)
                f[i][j]=max(f[i][j], f[i][j-v[i]]+w[i]);
        }
	printf("%d", f[n][m]);
    return 0;
}

与01背包一样，我们可以将空间复杂度优化成 $O(V)$

最终代码：

#include <iostream>
const int N = 209;
int m, n, f[N], w[N], c[N];
int main()
{
	scanf("%d%d", &m, &n);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", w + i, c + i);
    for (int i = 1; i <= n; i++)
        for (int j = w[i]; j <= m; j++)
            f[j] = std::max(f[j], f[j-w[i]] + c[i]);
    printf("%d", f[m]);
    return 0;
}

例题：[AHOI2001]质数和分解

多重背包

模板

有 $N$ 种物品和一个容量是 $V$ 的背包。第 $i$ 种物品最多有 $s[i]$ 件，每件体积是 $v[i]$，价值是 $w[i]$。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。

解法分析

第一种：朴素解法

代码好理解，就不做解释了。只要掌握了01背包的状态转移方程，这个代码问题不大。

#include <iostream>
const int N = 509;
int n, m, f[N];
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        int s, v, w;
        scanf("%d%d%d", &s, &v, &w);
        for (int j = m; j >= v; j--)
            for (int k = 0; k<=s and j>=k*v; k++)
                f[j] = std::max(f[j], f[j-k*v] + k*w);
    }
    printf("%d", f[m]);
    return 0;
}

注：这个代码是后来写的，将 s, v, w 数组改成了变量，应该能够看懂。

这个代码时间复杂度较高（$O(V\times \Sigma^N_{i=1}C_i)$），当数据较小时，该代码可以通过。但是，当数据很大时，这个代码就一定会 TLE。

所以，我们考虑改善时间复杂度。应当使用二进制拆分法来将多重背包转换成01背包，再求解，速度将大幅提高。

二进制拆分法的原理：从 $2^0,2^1,2^2,...,2^{k-1}$ 这 $k$ 个 $2$ 的整数次幂中选出若干个相加，可以表示出 $0\sim 2^k-1$ 之间任何一个整数。

例如：$1，2，4$可以表示 $1$ 至 $7$ 内所有的正整数。即 \[ 1=1\\ 2=2\\ 3=1+2\\ 4=4\\ 5=1+4\\ 6=2+4\\ 7=1+2+4 \] 按照这个思路，我们可以把数量为 $c[i]$ 的第 $i$ 种物品拆成若干个由二进制数组成的物品数量。例如，有一种物品有 $10$ 个，每个物品的价值为 $100$，体积为 $20$。那么，我们就要存：

第一轮：$w[++counter]=1*100,\ v[counter]=1*20$

第二轮：$w[++counter]=2*100,\ v[counter]=2*20$

第三轮：$w[++counter]=4*100,\ v[counter]=4*20$

第四轮：$w[++counter]=3*100,\ v[counter]=3*20$

这样，我们就把多重背包问题转化成了01背包问题，时间复杂度 $O(log\ C_i)$。

#include <iostream>
const int N = 509, M = 26009;
int n, nn, m, f[N], v[M], w[M];
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1, s, x, y; i <= n; i++)
    {
        int t = 1;
        scanf("%d%d%d", &s, &x, &y);
        while (s >= t)
        {
            v[++nn] = t * x, w[nn] = t * y;
            s -= t, t <<= 1;
        }
        if (s) { v[++nn] = s * x, w[nn] = s * y; }
    }
    for (int i = 1; i <= nn; i++)
        for (int j = m; j >= v[i]; j--)
            f[j] = std::max(f[j], f[j-v[i]] + w[i]);
    printf("%d", f[m]);
    return 0;
}

混合背包

混合背包即将上述的三种最基础的背包问题体型放在一种问题里。先来看模板题。

模板

有 $N$ 种物品和一个容量是 $V$ 的背包。

物品一共有三类：

第一类物品只能用1次（01背包）；
第二类物品可以用无限次（完全背包）；
第三类物品最多只能用 $s[i]$ 次（多重背包）；

每种体积是 $v[i]$，价值是 $w[i]$。求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。

解法分析

当该物品有无限个时，则按照完全背包的解法来处理；

当该物品有有限个时，则按照多重背包或者01背包的解法来处理。

代码：

#include <iostream>
const int N = 209;
int v, n, f[N];
int main()
{
    scanf("%d%d", &v, &n);
    for (int i = 1, w, c, p; i <= n; i++)
    {
        scanf("%d%d%d", &w, &c, &p);
        if (p == 0)
            for (int j = w; j <= v; j++)
                f[j] = std::max(f[j], f[j-w] + c);
        else
            for (int k = 1; k <= p; k++)
                for (int j = v; j >= w; j--)
                    f[j] = std::max(f[j], f[j-w] + c);
    }
    printf("%d", f[v]);
    return 0;
}

二维费用的背包问题

模板

有 $N$ 件物品和一个容量是 $V$ 的背包，背包能承受的最大重量是 $M$。

每件物品只能用一次。体积是 $v_i$，重量是 $m_i$，价值是 $w_i$。

求解将哪些物品装入背包，可使物品总体积不超过背包容量，总重量不超过背包可承受的最大重量，且价值总和最大。

解法分析

这种题与前三种常规背包问题几乎相同，只是多了一个限定条件而已。

回顾一维费用的背包问题，状态准是：$f[j]$ 表示在背包容量为 $j$ 的情况下能获得的最大价值

此时，多了一个限定条件，那么我们就自然想到多增一维，即：$f[j][k]$ 表示在第一个限制条件为 $j$ ，第二个限制条件为 $k$ 的情况下能获得的最大价值

同样类比一维费用的背包问题的状态转移方程，二维的状态转移方程应该这么写： \[ f_{j, k} = max(f_{j − v_i,\ k − m_i},\ f_{j,\ k}) \] 状态转移方程出来了，那么写代码也就轻松了。

#include <iostream>
const int N = 400;
int g, v, n, f[N][N];
int main() {
    scanf("%d%d%d", &g, &v, &n);
    for (int i = 1, value, w1, w2; i <= n; i++)
    {
        scanf("%d%d%d", &value, &w1, &w2);
        for (int j = g; j >= w1; j--)
            for (int l = v; l >= w2; l--)
                f[j][l] = std::max(f[j][l], f[j - w1][l - w2] + value);
    }
    printf("%d", f[g][v]);
    return 0;
}

分组背包

模板

有 $N$ 组物品和一个容量是 $V$ 的背包。

每组物品有若干个，同一组内的物品最多只能选一个。每件物品的体积是 $v_{i,j}$，价值是 $w_{i,j}$，其中 $i$ 是组号，$j$ 是组内编号。求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。

解法分析

这个问题变成了每组物品有若干个策略：是选择本组的某一件，还是不选。

状态转移方程：$f[k][v]=max\{f[k-1][v],\ f[k-1][v-w[i]]+c[i]\bigg| 物品i\in 第k组 \}$

代码：

#include <iostream>
const int N = 109;
int n, m, s[N], v[N][N], w[N][N], f[N];
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", s + i);
        for (int j = 1; j <= s[i]; j++)
            scanf("%d%d", &v[i][j], &w[i][j]);
    }
    for (int i = 1; i <= n; i++)
        for (int j = m; j >= 0; j--)
            for (int k = 1; k <= s[i]; k++)
                if (j >= v[i][k])
                    f[j] = std::max(f[j], f[j-v[i][k]] + w[i][k]);
    printf("%d", f[m]);
    return 0;
}

秘笈

$f$ 数组的大小一定由限制条件的大小决定
循环处理背包问题时，第一层循环永远一一是枚举物品个数或组别（重要）

int f[N]; // N 为价值或重量(即限定条件)的最大值
int main() {
    // ...;
    for (int i = 1; i <= %物品个数或组数%; i++)
        for (int j = %背包容量或价值最大值%; j >= %第i件物品的价值或体积%; j--) // 这一行不绝对，可能会正序循环或者其他。
            f[j] = std::max(f[j], f[j-w[i]] + c[i]);
}