多重背包的单调队列优化

发表于 | 分类于 |

前置知识:背包dp+单调队列

多重背包中，每个物品有三个属性，w[i]即价值，c[i]即费用，s[i]即个数。

若直接转化成01背包处理，则时间复杂度为O(nml)

易知，转化成01背包处理时，选取多件同一种物品的情况会被重复计算多次（1与2,2与3等等）

故引入二进制优化：

4=1+2+1

6=1+2+3

将物品拆分成logs[i]种物品，即可保证物品被选择的个数都被考虑到，又可减少上述重复情况，时间复杂度为O(n*m*logl)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int tot=0;
void logdp()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int log=1;
        cin>>cost>>wealth>>num;
        while(num-log>0)
        {
            c[tot]=cost*log;
            w[tot]=wealth*log;
            tot++;
            num-=log;
            log*=2;
        }
        if(num>0)
        {
            c[tot]=cost*num;
            c[tot]=wealth*num;
            tot++;
        }
        
    }
}

继续观察，f[i][j]可从f[i-1][j-k*c]中转移过来，可视作:

f[i][j]=max(f[i-1][j-k*c]+kw),同理f[i][j+c]=max(f[i-1][j+c-kc]+k*w)

两者的状态转移方程中存在重叠部分，重叠部分的值只相差一个w，而重叠部分的大小关系不会改变

故我们可以将j从0~m，根据对c的余数分割成c个部分：

0、c、2c、3c:%c=0

1、1+c、1+2c:%c=1

….

每一次转态转移时，对每一组分别维护一个单调队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
int solve()
{
    int N,M;
    cin>>N>>M;
    int q[20005];//用数组模拟队列
    vector<int>dp[2];
    dp[0].resize(M+1);
    dp[1].resize(M+1);
    for(int i=1;i<=N;i++)
    {
        cin>>c>>w>>s;
        for(int j=0;j<c;j++)//分组
        {
            int l=1,r=0;//清空队列
            for(int k=j;k<=M;k+=c)
            {
                while(r>=l&&k-s*c>q[l])
                {//若队列首元素不在可转移范围内
                    l++;
                }
                if(r>=l)
                {
                    dp[fl][k]=max(dp[fl][k],dp[fl^1][q[l]]+(k-q[l])/c*w);
                }
                while(r>=l&&dp[fl^1][q[r]]+(k-q[r]/c*w<=dp[fl^1][k])
                {//维护单调队列
                    r--;
                }
                q[++r]=k;
            }
        }
        fl^=1;//调换数组
    }
    return dp[fl^1][M];
}

时间复杂度为O(n*m)

一点小附加：

如果要求输出方案：

用一个二维bool数组used[i][v]表示:使用了v容量时的最佳策略，是否使用了第i个物品

故输出方案时(以01背包为例)：

1
2
3
4
5
6
7
8
9
10
11
for(int i=N,v=M;i>=1;i--)//M为最终所用容量
{
    if(g[i][v])
    {
        cout<<i<<" ";
        v-=c[i];
    }else
    {
        continue;
    }
}

如果要求输出方案数：

  1. 求装到一定容量的方案数，直接枚举物品进行状态转移(dp[0][0]=1,表示什么都不装有一种方案)
  2. 求达到最佳方案时的方案数，从i-1转移到i时，设sum[i][j]为考虑前i件物品，耗费为j时最佳方案的方案数，则若dp[i-1][j]dp[i-1][j-c[i]]+w[i]，则此时最佳方案不变，sum[i][j]=sum[i-1][j];若dp[i-1][j]=dp[i-1][j-c[i]]+w[i]，则上述两种方案都能转移到最佳方案，则sum[i][j]=sum[i-1][j]+sum[i-1][j-c[i]](sum[0][0]=1)

如果要求第k优解:

添加一维表示第k优解，f[i][j][k]表示考虑前i种物品，容量为j时的第k优解。

则状态转移时，用两个数组a[i][j][k]、b[i][j][k]，a[i][j][k]存储选择了第i个物品,容量为j的第k优解，b[i][j][k]存储不选择第i个物品时容量为j的第k优解，然后使用双指针，将两个数组统计结果中的前k优解转移到f[i][j][k]中，复杂度为O(nmk)

注意，f、a、b的第一维i可省略，a、b的第二维j可省略(统计a、b时容量都一定)

参考:

https://oi-wiki.org/dp/knapsack/#_12

https://zhuanlan.zhihu.com/p/144789126