背包专题

01背包

原理

dp[i][j]表示考虑到第i个元素时，背包容量为j的情况下的最大价值。初始条件为dp[0][i] = 0，表示当考虑前0个物品时，无论背包容量为多少，最大价值都是0。状态转移方程可以通过定义得到，当前状态由前一个状态拿当前物品i或者不拿当前物品i转移过来。一维空间形式循环顺序要从m到v[i]，原因是省略了i - 1维度。

$dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i])$ $dp[j] = max(dp[j], dp[j - v[i] + w[i]]), j ∈(m,v[i])$

模板

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

例题

AW.2 01背包问题（简单）

AW.278 数字组合（简单）

01背包求可能方案种数

完全背包

原理

如果按照01背包的状态定义和状态转移方程思维方式，我们不难得出如下的状态转移方程。

$dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i], ... , dp[i - 1][j - s * v[i]] + s * w[i]);$

如果直接循环则需要3重循环来实现，但是我们发现上述部分项已经计算过了。

$dp[i][j - v[i]] + w[i] = max(dp[i - 1][j - v[i]] + w[i], dp[i - 1][j - 2 * v[i]] + 2 * w[i] , ... , dp[i - 1][j - s * v[i]] + s * w[i]);$

所以dp[i][j]可以进行简化为：

$dp[i][j] = max(dp[i - 1][j], dp[i][j - v[i]] + w[i]), j∈(v[i], m)$

如果化简为一维形式，由于需要简化的是dp[i][j - v[i]]，应该体积从小到大循环。这里可以优化的原因是，体积一定的情况下，如果可以随意拿取，那么拿取的s件一定是固定值，注意和下边的多重背包区分。

模板

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

例题

AW. 完全背包问题（简单）

AW.1021 货币系统（简单）

完全背包求可能方案种数

LC.322 零钱兑换（中等）

多重背包

原理

多重背包问题可以使用三重循环直接暴力求解，也可以使用二进制优化。暴力求解和上述完全背包问题相似，在于每次要确定s个物品，这里无法进行完全背包的优化，因为每次求解的s并不是固定值。
二进制优化的原理是将多个物品打包成一个物品来看，将最多选s个物品的问题转化成log(s)个物品的 01背包问题，从而降低复杂度。可以证明每次选取1,2,4,8,16…(s- 2^k - 1)个物品打包之后，每个物品选与不选的组合（看做01背包）可以得到s种结果。这里二进制优化的思想很有意思，可以类比快速幂和龟速乘。时间复杂度为O(N logS M)
多重背包的终极优化方式是单调队列优化。在将多重背包的公式展开之后，类比完全背包可以发现对于f[i][j]的计算相当于是j之前s大小滑动窗口内极值的计算，因此可以用线性方法直接计算，将时间复杂度从O(ns)优化到O(n)，最终的整体时间复杂度为O(nm)。

多重背包的单调队列优化中，可以将背包体积展开成如下公式，其中公式二中的（s + 1）是因为本身体积为j - v但是还可以选择s个物品，因此最终剩下的体积就是j - (s + 1) * v。公式三种的r表示总体积对v取余之后的值，所以其实r = j % v，在代码中需要枚举所有的r，因为最终的余数可以是0到j % v的所有数，题目没有要求一定用完体积。

$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 - s * v] + s * w)①\\ f[i][j - v] = max(f[i - 1][j - v], f[i - 1][j - 2 * v] + w), f[i - 1][j - 3*v] + 2 * w, ... ,f[i - 1][j - (s + 1)* v] + s*w)②\\ ...\\ f[i][r + v] = max(f[i - 1][r + v], f[i - 1][r] + w)③\\ f[i][r] = max(f[i - 1][r])④$

可以对比公式1和公式2，发现公式1比2所求的极值多了一个f[i - 1][j],少了一个f[i - 1][j - (s + 1) * v] + s * w，类比之后所有项都有同样的规律，因此可以用单调队列优化。但是仔细观察，每一项虽然是相同的，但是每次会多一个w的偏移量，所以每次比较的都只能是前边的项，刚好减去j * w可以实现，在求值的时候可以再加上获得正确结果。

模板

//暴力求解多重背包问题
for (int i = 1; i <= n; i ++ )
    for (int j = 0; j <= m; j ++ )
        for (int t = 0; t <= s[i]; t ++ )
            if (j - s * v[i] >= 0)
                f[i][j] = max(f[i][j], f[i - 1][j - s * v[i]] + s * w[i]);
//二进制优化
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 12010, M = 2010;

int V[N], W[N];
int idx;
int n, m;

int f[M];

int main()
{
    scanf("%d%d", &n, &m);

    //对于每一个物品将s件拆解成log(s)件打包的物品
    for (int i = 0; i < n; i ++ )
    {
        int v, w, s;
        scanf("%d%d%d", &v, &w, &s);
        int k = 1;
        while (k <= s)
        {
            ++ idx;
            V[idx] = k * v;
            W[idx] = k * w;
            s -= k;
            k *= 2;
        }
        //如果还有剩余不满足2的幂次也要打包
        if (s)
        {
            ++ idx;
            V[idx] = s * v;
            W[idx] = s * w;
        }
    }

    //用01背包求解
    for (int i = 1; i <= idx; i ++ )
        for (int j = m; j >= V[i]; j -- )
            f[j] = max(f[j], f[j - V[i]] + W[i]);

    cout << f[m] << endl;

    return 0;
}

//多重背包二进制优化的一种更好的写法
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 2010;

int f[N];

int n, m;

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++ )
    {
        int v, w, s;
        cin >> v >> w >> s;
        for (int k = 1; k <= s; k *= 2)
        {
            for (int j = m; j >= k * v; j -- )
                f[j] = max(f[j], f[j - k * v] + k * w);
            s -= k;
        }

            if (s)
                for (int j = m; j >= s * v; j -- )
                    f[j] = max(f[j], f[j - s * v] + s * w);
    }

    cout << f[m] << endl;
    return 0;
}

//单调队列优化
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010, M = 20010;

int n, m;
int f[M], g[M]; //滚动数组优化空间复杂度
int q[M];

int main()
{
    cin >> n >> m;

    for (int i = 0; i < n; i ++ )
    {
        int v, w, s;
        cin >> v >> w >> s;

        memcpy(g, f, sizeof f);
        int R = m % v;
        //枚举余数
        for (int r = 0; r <= R; r ++ )
        {
            int hh = 0, tt = -1;
            //枚举当前体积下需要计算的每一项
            //每次要记得减去j * w进行比较，因为窗口在滑动过程中，每次值都在增大，无法比较
            for (int j = 0; j <= (m - r) / v; j ++ )
            {
                //如果单调队列的滑动窗口已经超过s了就向前
                if (hh <= tt && j - q[hh] > s) hh ++ ;
                //如果当前值大于单调队列的末尾，则出队
                while (hh <= tt && g[r + j * v] - j * w > g[r + q[tt] * v] - q[tt] * w) tt -- ;
                //无条件入队当前元素
                q[++ tt] = j;
                //用当前最大值更新f数组得到当前结果
                //f[r + j * v] = g[r + q[hh] * v] - q[hh] * w + j * w;
                f[r + j * v] = g[r + q[hh] * v] + (j - q[hh]) * w;
            }
        }
    }

    cout << f[m] << endl;

    return 0;
}

AW.4 多重背包问题I（简单）

AW.5 多重背包问题II（中等）

第二题主要考察二进制优化

AW.6 多重背包问题III（困难）

第三题考察多重背包问题的单调队列优化

分组背包

原理

分组背包问题指有很多物品组，从每组中只能挑选一个物品，求最大价值。相当于每组之内物品互斥，且每组之间可以看成01背包问题。分组背包是有依赖的背包问题的前序问题。

模板

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;
int f[N];
int v[N][N], w[N][N];
int s[N];
int n, m;

int main()
{
    cin >> n >> m;

    for (int i = 1; i <= n; i ++ )
    {
        cin >> s[i];
        for (int j = 0; j < s[i]; j ++ )
            cin >> v[i][j] >> w[i][j];
    }

    //先循环物品组，再循环体积，再循环组内物品
    for (int i = 1; i <= n; i ++ )
        for (int j = m; j >= 0; j -- )
            for (int k = 0; k < s[i]; k ++ )
                if (j >= v[i][k])
                    f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
                    //这里枚举最后一个的时候是互斥的，因为确定了体积

    cout << f[m] << endl;

    return 0;
}

例题

AW.9 分组背包问题（中等）

二维费用背包

原理

二维费用背包在一维费用背包基础上，多一维度费用的判断，必须满足两者的费用均满足转移条件时，才可以转移。

模板

int f[N][M];
int v1[K], v2[K], w[K];

for (int i = 1; i <= n; i ++ )
    for (int j = m1; j >= v1[i]; j -- )
        for (int k = m2; j >= v2[i]; j -- )
            f[j][k] = max(f[j][k], f[j - v1[i]][k - v2[i]] + w[i]);

例题

AW.8 二维费用背包问题（中等）

AW.1022 宠物小精灵之收服（简单）

混合背包

原理

输入很多个物品，每个物品可能有三种情况，01物品，无限次用物品和只能取用s个物品。其实可以将01背包看成多重背包的特例，之后分开进行状态转移。甚至完全背包也是多重背包的特例，每次可以取用的物品数一定不超过m / v + 1个。

模板

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;
int f[N];
int n, m;

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ )
    {
        int v, w, s;
        cin >> v >> w >> s;
        if (s == -1) s = 1;
        else if (s == 0) s = m / v + 1;

        //二进制优化一种更好的写法
        for (int k = 1; k <= s; k *= 2)
        {
            for (int j = m; j >= k * v; j -- )
                f[j] = max(f[j], f[j - k * v] + k * w);
            s -= k;
        }

        if (s)
        {
            for (int j = m; j >= s * v; j -- )
                f[j] = max(f[j], f[j - s * v] + s * w);
        }
    }

    cout << f[m] << endl;
    return 0;
}

例题

AW.7 混合背包问题（中等）

动态规划（一）背包专题