signed

QiShunwang

“诚信为本、客户至上”

多重背包笔记

2021/1/28 15:07:38   来源:

前置芝士

在看这篇Blog之前,你需要掌握:

dp-01背包算法、二进制拆分思想、单调队列;
一定的数学公式推导能力。

多重背包问题是什么

多重背包是指这样一类问题:给定\(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\)的每次转移都只会用到上一次的状态,这里我参考01背包,使用了滚动数组的方式进行优化。

#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}\} \]

\[...... \]

这也就是单调队列所需的形式!于是我们考虑将原始中的“尾巴”想办法处理掉,让它们也可以用单调队列来优化。考虑将\(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;
}

注:由于AcWing评测机质量极高,所以使用了stl deque的代码并不能A掉,但是加上火车头以后就可以了(或者你手写双端队列勇士)。不知道火车头的可以参考这个。