【学习笔记】多重背包优化

· · 算法·理论

basic tips

多重背包可以看做 \texttt{01} 背包和完全背包的结合。

例题：P1776 宝物筛选

这道题完全就是多重背包板子，多重背包就是在 \texttt{01} 背包与完全背包两者间取了个折中，对于每个体积 V_i，价值 W_i 的物品多了一个限制，每种物品有且仅有 C_i 个。

朴素做法

在背包不能装下当前枚举的第 i 个物品的所有 C_i 个时，直接转换成完全背包对当前物品进行求解。反之，则转换成 \texttt{01} 背包，枚举第 i 个物品的个数。

这样的复杂度即为 O(nm\sum{C_i})，一旦数据稍微大一点就无法接受。

二进制优化

基于倍增思想，举个例子，当我们想拿 1024 个物品时，我们会去枚举 1 到 1024，但是若我们 1,2,4,8...512,1024 这样去拿，最终结果仍然与朴素做法一样，但是仅仅 10 次就可以得出答案，所以我们是把 C_i 拆成 2^0 + 2^1 + 2^2 + \ldots + 2^{\log_2{C_i} - 1} + x 的形式。

所以背包在当前第 i 个装得下时，我们在枚举个数时直接每次拿 2^k 个物品去跑 \texttt{01} 背包，这样的复杂度 O(nm\sum\log{C_i})，可以接受。

code

#include<bits/stdc++.h>
// #define int long long

using namespace std;
const int MAXN = 1e5 + 10;
int n,W,v[MAXN],w[MAXN],m[MAXN],dp[MAXN];
signed main()
{
    scanf("%d %d",&n,&W);
    int ind = 0;
    for(int i = 1;i <= n;i ++)
    {
        int a,b,c;
        scanf("%d %d %d",&a,&b,&c);
        int ret = 1;
        while(ret <= c)
        {
            v[++ ind] = ret * a;
            w[ind] = ret * b;
            c -= ret;
            ret <<= 1;
        }
        if(c > 0)
        {
            v[++ ind] = c * a;
            w[ind] = c * b;
        }
    }
    for(int i = 1;i <= ind;i ++)
    {
        for(int j = W;j >= w[i];j --)
            dp[j] = max(dp[j],dp[j - w[i]] + v[i]);
    }
    printf("%d\n",dp[W]);
    return 0;
}

单调队列优化

对于转移方程：dp_{i,j} = \max\{dp_{i-1,j-k \times v_i} + k \times w_i\}，所以 dp_{i,j-k \times v_i} 的值定会被 dp_{i,j-(k+1) \times v_i} 所影响，举例:

当 v_i = 4，j 的值如下：1,2,3,4,5,6,7,8,9,10,11,12 \dots

可以发现 1 \equiv 4 (\text{mod } v_i),2 \equiv 5(\text{mod } v_i)，以此类推。

因此，我们可以根据 j 对 v_i 的模数对物品进行分类，所以可以得到 j = num + k \times v_i，其中 num 为 j 对 v_i 的模数，移项得 k = \lfloor\frac{j - num}{v_i}\rfloor，修改转移方程得：dp_{j + k \times v_i} = \max\{dp_{j'+ k \times v_i} + (j - j') \times w_i\}，其中 j' \in [\max\{0,j - C_i\},j)，就可以把 \max 里那一坨用单调队列优化，复杂度 O(nm)。

code

#include<bits/stdc++.h>
// #define int long long

using namespace std;
int n,W,v,w,c,q1[100005],q2[100005],head,tail,dp[100005];
signed main()
{
    scanf("%d %d",&n,&W);
    for(int i = 1;i <= n;i ++)
    {
        scanf("%d %d %d",&v,&w,&c);
        int tmp = min(c,W / w);
        for(int j = 0;j < w;j ++)
        {
            head = 1,tail = 0;
            int k = (W - j) / w;
            for(int t = 0;t <= k;t ++)
            {
                while(head <= tail && dp[j + t * w] - t * v > q2[tail]) tail --;
                q1[++ tail] = t;
                q2[tail] = dp[j + t * w] - t * v;
                while(q1[head] < t - tmp) head ++;
                dp[j + t * w] = max(dp[j + t * w],q2[head] + t * v);
            }
        }
    }
    printf("%d\n",dp[W]);
    return 0;
}

例题

P1782 旅行商的背包

P1833 樱花

P2760 科技庄园

P7381 [COCI2018-2019#6] Sličice