多重背包笔记

多重背包笔记 前置芝士

在看本文之前，需要掌握：

基础dp背包算法;
单调队列

多重背包问题是什么

多重背包是指这样一类问题：给定\(n\)种物体，每种物体具有三个属性\(v\)，\(w\)，\(c\)，分别代表其体积，价值和数量。要求在其中选出一些，满足第\(i\)种物品最多选择\(c_i\)个，体积总和\(sum_v \leq m\)，使得价值总和\(sum_w\)最大。
输入数据一般形如：

第1行输入两个数\(n\)和\(m\)
第\(2\)~\((n+1)\)行每行3个数\(v\)，\(w\)，\(c\)表示一个物体。

题目链接

朴素解法
常规解法：二进制拆分
最优解：单调队列优化

朴素解法

动态规划的状态\(f_{i,j}\)表示前\(i\)种物体刚好放满容量为\(j\)的背包中获得的最大价值。显然可以枚举i，j，对于\(i\)的每次转移都考虑选取该类物品中的多少个。其时间复杂度为\(O(m*sum_c)\)，基本不可接受。

代码

考虑到\(i\)的每次转移都只会用到上一次的状态，可以使用了滚动数组的方式进行优化。

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

int c[110];
LL v[110], w[110];
LL f[2][110];

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

    for (int i = 1; i <= n; ++i) {
        scanf("%lld%lld%d", &v[i], &w[i], &c[i]);
    }

    // 前面都是输入不多说，
    // 下面开始初始化状态

    memset(f, 0, sizeof(f));
    // 注意是刚好j体积
    for (int i = 0; i <= c[1] && i * v[1] <= m; ++i) {
        f[1][i * v[1]] = i * w[1];
    }

    for (int i = 2; i <= n; ++i) {
        for (int j = v[i]; j <= m; ++j) {
            for (int k = 0; k <= c[i] && k * v[i] <= j; ++k) {
                // 这里对二取模也就是滚动数组优化
                f[i % 2][j] = max(f[i % 2][j],
                  f[(i - 1) % 2][j - k * v[i]] + k * w[i]);
            }
        }
    }

    // 由于我们f数组是计算刚好j体积而不是小于等于，
    // 所以需要再进行一遍统计

    LL res = 0;
    for (int i = 0; i <= m; ++i) {
        res = max(res, f[n % 2][i]);
    }

    printf("%lld\n", res);

    return 0;
}

常规解法：二进制拆分

朴素解法的瓶颈在于，对于每一种物品，都要逐一枚举选取的数量，相当于把一种物品拆分成了c个一个一个取的01背包，这让时间爆炸增长。我们能不能优化这种拆分方式呢？答案是肯定的。

考虑二进制拆分的原理，任何一个整数都可以表示为许多2的幂次之和，并且每一个不同的二的幂次只会出现一次！这不就是01背包的限制条件吗？于是，我们得到了优化的拆分方案。

对于一种物品，我们先尽量拆成1，2，4，8大小的组，最后无法分出剩下的再单独分为一组，这样保证0~\(c\)之间所有的取法都能产生。此时的物体总数是\(O(\sum^{n}_{i = 1}{\log{c}})\)，总的时间复杂度就是它再乘上m。这个时间复杂度一般可以接受。

代码

第一部分是输入并用二进制分解物品：

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

vector<pair<LL, LL> > vec;
for (int i = 1; i <= n; ++i) {
    LL v, w;
    int c;
    scanf("%lld%lld%d", &v, &w, &c);

    int sum = 0;
    // 注意细节：预先判断，如果加入后会超过限制就不能加入
    for (int k = 1; sum + k <= c; k *= 2) {
        vec.push_back(make_pair(k * v, k * w));
        sum += k;
    }

    // 如果有剩余再将剩余单独打包成一个组
    if (c - sum > 0) {
        vec.push_back(make_pair((c - sum) * v, (c - sum) * w));
    }
}

接下来是常规的01背包解法：

// 注意细节：这里有可能会爆掉空间或者越界访问
if (!vec.empty() && vec[0].first <= m) {
    f[0][vec[0].first] = vec[0].second;
}

for (int i = 1; i < vec.size(); ++i) {
    for (int j = vec[i].first; j <= m; ++j) {
        // 同样的滚动数组优化
        f[i % 2][j] = max(f[(i - 1) % 2][j],
          f[(i - 1) % 2][j - vec[i].first] + vec[i].second);
    }
}

最后统计结果，和刚才一样，完整代码：

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

LL f[2][2010];

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

    vector<pair<LL, LL> > vec;
    for (int i = 1; i <= n; ++i) {
        LL v, w;
        int c;
        scanf("%lld%lld%d", &v, &w, &c);

        int sum = 0;
        for (int k = 1; sum + k <= c; k *= 2) {
            vec.push_back(make_pair(k * v, k * w));
            sum += k;
        }

        if (c - sum > 0) {
            vec.push_back(make_pair((c - sum) * v, (c - sum) * w));
        }
    }

    if (vec[0].first <= m) {
        f[0][vec[0].first] = vec[0].second;
    }

    for (int i = 1; i < vec.size(); ++i) {
        for (int j = vec[i].first; j <= m; ++j) {
            f[i % 2][j] = max(f[(i - 1) % 2][j],
              f[(i - 1) % 2][j - vec[i].first] + vec[i].second);
        }
    }

    LL res = 0;
    for (int i = 0; i <= m; ++i) {
        res = max(res, f[(vec.size() - 1) % 2][i]);
    }

    printf("%lld\n", res);

    return 0;
}

最优解：单调队列优化动态规划

正片开始！

首先考虑朴素解中的状态转移方程：

\[f_{i, j} = \max_{k = 0}^{\min\{c_i, \lfloor \frac{j}{v_i} \rfloor\}}\{f_{i - 1, j - kv_i} + kw_i\} \]

对这个式子进行一下分析，可以发现以下性质：

1. 在一次\(i\)转移内部，许多东西是不变的。具体地，\(c_i\), \(w_i\), \(v_i\)始终不变；\(j\)的范围不变：\(v_i\)到\(m\)。这些性质使得我们的处理方便了许多，然而实际上没有在算法中起到决定性作用 。

2. 对于每一个\(j\)，它只可能是从上个\(i\)转移的\(j\)，\(j - 2v_i\)，…，\(j-kv_i\)转移而来，也就是说，所有会互相影响的\(j\)转移都模\(v_i\)同余。这就给我们一个启发：根据模\(v_i\)的余数进行分组，分成\(v_i\)组。

由性质一，我们在以后的讨论中省略\(i\)下标（对于\(\max\)符号中的\(f\)，一定是\(i-1\)，对于其它是\(i\)）。另外设\(k\)的范围\(t = \min\{c_i, \lfloor \frac{j}{v_i} \rfloor\}\)。

由性质二，我们将每一个\(j\)拆分成\(pv + q\)，其中的q就是分组的依据，在每一组内，它是一个定值。于是状态转移方程变为了：

\[f_{pv+q} = \max_{k = 0}^{t}\{f_{(p-k)v} + kw\} \]

看上去好像进行不下去了呢。我们来举一个例子便于推导。假设对于所有的\(j\)，\(t\)都是2，并取\(q = 1\)。那么显然有一下式子（\(p\)太小的就不列出来了）：

\[f_{3v+1} = \max\{f_{3v+1}, f_{2v+1}+w, f_{v+1}+2w\} \]

\[f_{4v+1} = \max\{f_{4v+1}, f_{3v+1}+w, f_{2v+1}+2w\} \]

\[f_{5v+1} = \max\{f_{5v+1}, f_{4v+1}+w, f_{3v+1}+2w\} \]

\[f_{6v+1} = \max\{f_{6v+1}, f_{5v+1}+w, f_{4v+1}+2w\} \]

\[...... \]

看上去好像还是不能优化呢。但我们如果忽略掉\(\max\)符号内的这些\(w\)尾巴呢？再列一次：

\[\{f_{3v+1}, f_{2v+1}, f_{v+1}\} \]

\[\{f_{4v+1}, f_{3v+1}, f_{2v+1}\} \]

\[\{f_{5v+1}, f_{4v+1}, f_{3v+1}\} \]

\[\{f_{6v+1}, f_{5v+1}, f_{4v+1}\} \]

\[...... \]

这也就是单调队列所需的形式。于是我们考虑将原式中的\(w\)“尾巴”想办法处理掉，让它们也可以用单调队列来优化。考虑将\(f_{pv+1}\)这一行中的这些项都减掉\(pw\)，再在末尾加上去，就变成了：

\[f_{3v+1} = \max\{f_{3v+1}-3w, f_{2v+1}-2w, f_{v+1}-w\}+3w \]

\[f_{4v+1} = \max\{f_{4v+1}-4w, f_{3v+1}-3w, f_{2v+1}-2w\}+4w \]

\[f_{5v+1} = \max\{f_{5v+1}-5w, f_{4v+1}-4w, f_{3v+1}-3w\}+5w \]

\[f_{6v+1} = \max\{f_{6v+1}-6w, f_{5v+1}-5w, f_{4v+1}-4w\}+6w \]

\[...... \]

这样的形式就可以使用单调队列来维护，这个问题得到了完美解决。

代码

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

int c[1010];
LL v[1010], w[1010];

LL f[2][20010];

int main(void) {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        scanf("%lld%lld%d", &v[i], &w[i], &c[i]);
    }

    for (int i = 1; i <= c[1] && i * v[1] <= m; ++i) {
        f[1][i * v[1]] = i * w[1];
    }

    for (int i = 2; i <= n; ++i) {
        for (int q = 0; q < v[i]; ++q) {
            deque<pair<int, LL> > que;
            for (int p = 0; p * v[i] + q <= m; ++p) {
                int j = p * v[i] + q, t = min(c[i], p);

                while (!que.empty() &&
                  p - que.front().first > t) {
                    que.pop_front();
                }

                while (!que.empty() &&
                  que.back().second <= f[(i - 1) % 2][j] - p * w[i]) {
                    que.pop_back();
                }
                que.push_back(make_pair(p, f[(i - 1) % 2][j] - p * w[i]));

                f[i % 2][j] = que.front().second + p * w[i];
            }
        }
    }

    LL res = 0;
    for (int i = 0; i <= m; ++i) {
        res = max(res, f[n % 2][i]);
    }

    printf("%lld\n", res);

    return 0;
}