多重背包究极版--单调队列优化

发表于2022-06-02更新于2022-06-02

题目描述

题面不多说 多重背包

样例

输入

1
2
3
4
5
4 5
1 2 3
2 4 1
3 4 3
4 5 2

输出 10

时间复杂度

如果把每种物品拆分成一个 当作01背包来处理 O（n * w *s）

二进制优化 O(n* w *log c)

单挑队列优化O(n * w) （差不多线性的了终极版）

不了解但单挑队列优化（滑动窗口）的同学可以先学习这题AcWing 135. 最大子序和 - AcWing

简单的多重背包 二维表示 d [i][j]表示 在体积j下 并且可以装第i种物品 最多能获得多大价值

然后这个显然 可以化成一维 加上滚动数组

假设 gn是上个状态的结果 （也是上述说的dp[i][j]） 然后 dp[j]表示当前状态下得到的结果

1
2
3
4
5
6
7
for(int i=1;i<=n;i++)

	{for(int j=1;j<=m;j++) 

		dp[j]=max{gn[i-v]+w,gn[i-2v]+2w, gn[i-3v]+3w ...gn[i-kv]+kw} k为min(j/v,s)也就是 在j最多能包含多少个第i个物品，这一步为毛要用gn而不是dp（这个dp是数组不是指算法）呢？因为如果用的是dp的话就变成了01完全背包。
      
}

假设同学你已经掌握了 滑动窗口的原理

我们发现 上述的这个循环有部分变量一直在重复

for(int j=1;j<=m;j++) 

    dp[j]=max{gn[i-v]+w,gn[i-2v]+2w, gn[i-3v]+3w ...gn[i-kv]+kw} k为min(j/v,s)

我们把这个循环拆开

首先 对于每一个物品的v循环 我们把它分为v类 每个j%v的值为一类

假设这个v为3(为什么是3，因为方便我码字)下面是拆开的部分

第一部分j%v==0 dp[j]=max{gn[0]+(j-0)/v * w ,gn[v]+(j-v)/v*w, gn[2v]+(j-2v) * w ,….gn[j-v]+w,gn[j] }

第二部分 j%v==1 dp[j]=max{gn[1]+(j-1)/v * w ,gn[v+1]+(j-v-1)/v*w, gn[2v+1]+(j-2v-1) * w ,….gn[j-v]+w,gn[j] }

第三部分 j%v==2 dp[j]=max{gn[2]+(j-2)/v * w ,gn[v+2]+(j-v-2)/v*w, gn[2v+2]+(j-2v-2) * w ,….gn[j-v]+w,gn[j] }

注意上面有不严谨的地方如果(j-xv)/v<s（x是自由变量 0，1，2。。。） 那是不够减的 所以要滑动窗口维护能减的数量下的最大值

同时我们把每个dp[j]的过程拆分一下
dp[j] = dp[j]
dp[j+v] = max{dp[j] + w, dp[j+v]}
dp[j+2v] = max{dp[j] + 2w, dp[j+v]+ w, dp[j+2v]}
dp[j+3v] = max{dp[j] + 3w, dp[j+v] + 2w, dp[j+2v] + w, dp[j+3v]}
…
但是，这个队列中前面的数，每次都会增加一个 w ，

所以我们只需要记录 gn[k-f]+(k-f)/v*w的最大值即可 由于 k-f+(k-f)/v*w可以求出 所以记录 最大gn[k-f]即可

C++ 代码

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
#include <iostream>`
`//#include <algorithm>`
`#include <cstring>`
`using namespace std;`

`int que[100000],dp[100000],gn[100000];//队列，结果 ，工具队列`

`signed main()`
`{`
    `int n,m;`
    `cin>>n>>m;`
    `for(int i=1; i<=n; i++)`
    `{`
        `int v,w,s;`
        `scanf("%d%d%d",&v,&w,&s);//体积 价值 数量`
        `memcpy(gn,dp,sizeof dp);`
        `for(int j=0; j<v; j++)`
        `{`
            `int hh=1,tt=0;`
            `for(int k=j; k<=m; k+=v)`
            `{`
                `if(que[hh]+s*v<k&&hh<=tt) hh++;
                while(tt>=hh&&gn[k]>=gn[que[tt]]+(k-que[tt])/v*w)tt--;`
                `que[++tt]=k;`
                `dp[k]=(k-que[hh])/v*w+gn[que[hh]];`
            `}`
        `}`
    `}`
     cout<<dp[m]<<endl;

return 0;

}


所以呢就别不快乐。