About 单调队列优化多重背包

20230921

About 单调队列优化多重背包

前言

之前打了给代码，隐隐约约知道了意思。

但不完全明白~

于是经过自己的钻研，终于理解。

模板题（P1776 宝物筛选）

Statement

传送门

01 背包中每个数只能选一次改成可以选 \(s_i\) 次。

Solution

直接 dp 可以做到 \(O(n^3)\) ，

很显然，三次分别枚举哪一个物品，背包质量是多少和选的个数即可。

在此基础上，还可以进行二进制优化，但没有什么思维含量，这里不赘述。

怎么就和单调队列扯上关系了？

考虑先列出 \(dp\) 方程式：

设 \(f_{i,j}\) 表示选到第 \(i\) 个物品，容量为 \(j\) 的最大价值， \(w,v\) 分别是重量和价值

于是 \(f_{i,j}=\max(f_{i-1,j},f_{i-1,j-w}+v,f_{i-1,j-2w}+2v,\dots)\)，

同理我们可以得到 \(f_{i,j-w}=\max(f_{i-1,j-w},f_{i-1,j-2w}+v,f_{i-1,j-3w}+2v,\dots)\)

以此类推一直就会推到 \(f_{i,r}=f_{i-1,r}\) 这里的 \(r=j \mod w\)。

很容易发现其实这里的 \(j,j-w,j-2w,\dots,r\) 都是 \(\mod w\) 同余的，

而我们又是想找到这中间的最大值——

不难想到用单调队列维护。

对于每一个同余的组，我们都考虑去枚举 \(0w,1w,2w,\dots\) ，

从而在每一次单调队列中进行更新，

整个时间复杂度是 \(O(n^2)\) 的，

看代码会更容易理解：

/*单调队列优化*/ 
#include <bits/stdc++.h>
using namespace std;

const int N=4e4+5;
int n,W,val,w,c,k,d,q[N],h,t,q2[N],dp[N],ans;
//单调队列 q[] 维护下标，q2[] 维护值
int read(){//读入优化
  int x=0,f=1;char ch=getchar();
  while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
  while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
  return x*f;
}

int main(){
  /*2023.9.13 H_W_Y P1776 宝物筛选 多重背包*/ 
  n=read();W=read();
  for(int i=1;i<=n;i++){
  	val=read();w=read();c=read();//读入价值，重量和可以选的次数
  	if(w==0){ans+=val*c;continue;}//特判重量为 0 时直接选完
  	k=W/w;//计算把所有体积选满最多能选多少次
  	c=min(c,k);//更新可以选的次数，让 c 变得合理一些（可以优化一点点），避免了无用的枚举
  	for(int d=0;d<w;d++){//枚举 r ，余数
  	  h=t=0;k=(W-d)/w;//清空队列，k 是最多能选的个数
	  for(int j=0;j<=k;j++){//枚举选了多少个
	  	while(h<t&&dp[d+j*w]-j*val>=q2[t-1]) t--;
	  	q[t]=j;q2[t++]=dp[d+j*w]-j*val;
	  	while(h<t&&q[h]<j-c) h++;
	  	dp[d+j*w]=max(dp[d+j*w],q2[h]+j*val);
 	  }	//单调队列里每次把 j*val 减去了方便计算答案，可以意会一下
	}
  }
  printf("%d\n",ans+dp[W]);
  return 0;
}

再来一道例题（P4241 采摘毒瘤）

Statement

传送门

\(n\) 个物品，每种 \(c_i\) 个，占据 \(w_i\) 的空间。背包容量为 \(m\)。现在要求装不下任何一个没装的物品的方案数（对 \(19260817\) 取模）。

\(1 \le n,k_i,d_i \le 500,1 \le m \le 10^5\)

Solution

我们考虑没有被放进去的最小体积的那个物品，

于是这个数对答案的贡献就是 \(\sum_{j=m-sum-w_i+1}^{m-sum} f[i][j]\)，

所以我们考虑从大到小枚举每一个物品，

对其进行多重背包，其实就每一次加入一个物品。

发现在对于最小的没选的物品 \(i\) ，比他小的是选完了的。

于是对于每次枚举我们直接用单调队列加入就可以了。

时间复杂度 \(O(nm)\)

考虑这道题是求方案数，于是实际上只用维护 \(f\) 的和而不用求最大值。

#include<bits/stdc++.h>
using namespace std;

const int N=505,M=1e5+5,mod=19260817;
int n,m,f[2][M],rev=0,sum=0,ans=0; 
struct node{
  int w,c;//重量和次数
  bool operator <(const node &rhs) const{
    return w>rhs.w;
  } 
}a[N];

int read(){
  int x=0,f=1;char ch=getchar();
  while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
  while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
  return x*f;
}

void wrk(int cnt,int w){
  int k,nw=0;
  for(int d=0;d<w;d++){
  	k=(m-d)/w;nw=0;
  	for(int j=0;j<=k;j++){
  	  if(j>cnt) nw=(nw-f[rev^1][d+(j-cnt-1)*w]+mod)%mod;	
  	  f[rev][d+j*w]=nw=(nw+f[rev^1][d+j*w])%mod;
	}
  }
}

int main(){
  /*2023.9.21 H_W_Y P4241 采摘毒瘤 多重背包*/ 
  n=read();m=read();
  for(int i=1;i<=n;i++) a[i].c=read(),a[i].w=read(),sum+=a[i].c*a[i].w;
  if(sum<=m){puts("1");return 0;}
  sort(a+1,a+n+1);
  memset(f,0,sizeof(f));
  f[0][0]=1;
  for(int i=1;i<=n;i++){
  	sum-=a[i].c*a[i].w;rev^=1;
  	wrk(a[i].c-1,a[i].w);
  	for(int j=max(0,m-sum-a[i].w+1);j<=m-sum;j++) ans=(ans+f[rev][j])%mod;
  	wrk(a[i].c,a[i].w);
  }
  printf("%d\n",ans);
  return 0;
}

Conclusion

单调队列优化多重背包基于对余数的讨论，再用单调队列维护最大值

速度很快，能做到 \(O(nW)\)