背包乱学

01背包

$n$ 件物品带体积 $c_i$ 价值 $w_i$ ，选择若干个体积和 $\leq V$ 的物品价值最大。

for(rint i=1;i<=n;i++)
for(rint j=all;j>=c[i];j--) f[j]=max(f[j],f[j-c[i]]+w[i]);

时间 $O(nV)$ ，空间 $O(V)$ 。

完全背包

$n$ 种物品带体积 $c_i$ 价值 $w_i$ 无限个，选择若干个体积和 $\leq V$ 的物品价值最大。

for(rint i=1;i<=n;i++)
for(rint j=c[i];j<=all;j++) f[j]=max(f[j],f[j-c[i]]+w[i]);

时间 $O(nV)$ ，空间 $O(V)$ 。

多重背包

$n$ 种物品带体积 $c_i$ 价值 $w_i$ 有 $num_i$ 个，选择若干个体积和 $\leq V$ 的物品价值最大。

可以把数量二进制拆分后跑01背包，时间 $O(V\sum \log num_i)$ ，空间 $O(V)$ 。

for(rint i=1;i<=n;i++)
{
    int cc=read(),ww=read(),num=read();
    for(rint j=1;j<num;j<<=1) num-=j,c[++nn]=cc*j,w[nn]=ww*j;
    c[++nn]=cc*num,w[nn]=ww*num;
}

也可以对于每种物品通过枚举%体积的余数分开转移，利用单调队列优化转移，时间 $O(nV)$，空间 $O(V )$ 。

for(rint i=1,ii=1;i<=n;i++,ii^=1)
{
    int c=read(),w=read(),num=read();
    for(rint j=0;j<c;j++)
    for(rint k=0,hh=0,tt=-1;j+k*c<=all;k++)
    {
        while(hh<=tt&&k-q[hh]>num) hh++;
        if(hh<=tt) f[ii][j+k*c]=max(f[!ii][j+k*c],f[!ii][j+q[hh]*c]+(k-q[hh])*w);
        else f[ii][j+k*c]=f[!ii][j+k*c];
        while(hh<=tt&&f[!ii][j+q[tt]*c]-q[tt]*w<=f[!ii][j+k*c]-k*w) tt--;
        q[++tt]=k;
    }
}

混合背包

就是背包有1、若干、无限个，按类型转移即可。

二维费用背包

多加一维即可。

bool 背包

例如求子集和之类的，bitset 优化，时空复杂度除 $\omega$ 。

分组背包

每组最多选一件物品，内层枚举组内即可。

树形背包

树上的背包，能否选择依赖树上的关系，朴素定义状态一般为 $f[u][i]$ 表示 $u$ 子树选 $i$ 个点的价值，朴素转移为 $f[u][i+j]=\sum f[u][i]\times f[v][j]$ ，展开列项计算或是考虑每个点对只会在 LCA 贡献 $O(1)$ 都可以得出 $O(nk^2)$ 的复杂度，物品大小为1的话去掉不必要的转移则为 $O(nk)$。

1. 树上选容量为 $k$ 的带体积权值点且属于根连通块的最大权值和，朴素 $O(nk^2)$ ，考虑对原树后序遍历后可以依次添加，$f[i][j]=max(f[i-1][j-c[i]]+w[i],f[i-sz[i]][j])$ ，省去了合并操作，就可以做到 $O(nk)$ 。
2. 树上选容量为 $k$ 的带体积权值点且属于一个连通块的最大权值和，上述做法+点分治，根据主定理仍然 $O(nk)$ 。
3. 有 trick 是维护前后缀背包，可以快速计算排除某个节点不选的情况。

背包方案

具体方案和方案数都是先做一遍背包再倒过来搜。

总数量小的背包

$O(2^{n/2})$ 折半搜索。

滚动前后缀背包

前缀背包显然可以滚动，滚动后缀背包考虑先求出总背包然后依次撤回，容易发现撤回其实就是倒着去掉物品的贡献。

总体积小的子集和

可以证明二进制拆分后物品总数量级别为 $O(\sqrt V)$ ，然后跑01背包，时间 $O(n+V\sqrt V)$ ，空间 $O(n+C)$ 。

单体积小的背包

子集和

$n$ 个 $\leq D$ 的元素，求是否存在子集和为 $C$。

1. 首先找到满足 $\sum^k w_i\leq C$ 最大的 $k$ ，把前面的取负，这样 $C\leftarrow C-\sum^k w_i < D$ ，考虑定义 $can(tot,l,r)$ 表示是否存在 $\lambda \in\{0,1\}$ 使得 $\sum_{i=1}^{l-1}w_i+\sum^r_{i=l}\lambda _iw_i=tot$ ，发现固定 $tot,r$ 则 $can(tot,l,r)=1$ 的 $l$ 为一段前缀，同理固定 $tot,l$ 则 $can(tot,l,r)=1$ 的 $r$ 为一段后缀，定义 $f[tot][r]$ 表示满足 $can(tot,l,r)=1$ 的最大的 $l$ ，显然有 $f[tot][r]\leq f[tot][r+1]$ ，考虑转移有

   $$\left\{\begin{matrix}f[tot+w_{r+1}][r+1]\leftarrow f[tot][r] & & \\ f[tot][r+1]\leftarrow f[tot][r] & & \\ f[tot-w_l][r]\leftarrow l,l\in[f[tot][r-1],f[tot][r]) & & \end{matrix}\right.$$

   时间 $O(nD)$ ，空间 $O(n+D)$ 。

   for(rint i=N-W+1;i<=N;i++) dp[0][i]=0;
   for(rint i=N+1;i<=N+W;i++) dp[0][i]=1;
   dp[0][N-C+sum]=st;
   
   for(int i=st;i<=n;i++,ii^=1)
   {
       for(rint j=N-W+1;j<=N+W;j++) dp[ii][j]=dp[ii^1][j];
       for(rint j=N-W+1;j<=N;j++) dp[ii][j+w[i]]=max(dp[ii][j+w[i]],dp[ii^1][j]);
       
       for(rint j=N+w[i];j>N;j--)
       for(rint k=dp[ii][j]-1;k>=dp[ii^1][j];k--)
           dp[ii][j-w[k]]=max(dp[ii][j-w[k]],k);
   }
   

2. 随机打乱集合，期望过程中最值为 $O(\sqrt nD)$ ，直接 bitset 暴力背包，时间 $O(\frac {n\sqrt nD} {\omega})$ ，空间 $O(n+\frac {\sqrt nD} {\omega})$ 。

凸函数 max 卷积

前置知识：凸函数 $(max,+)$ 卷积，即求 $c_i=max(a_j+b_{i-j})$，且 $b$ 为凸函数 。记 $c_i$ 在 $b$ 的决策位置为 $pos_i$ ，那么有 $pos_{i-1}\leq pos_i$ ，可以分治做到 $O(n\log)$ 。

01背包

物品体积 $\leq D$，容量为 $C$ 。对于相同重量的物品，我们肯定将价值从大到小贪心取，图像为一个凸函数。因此我们将背包在模 $C$ 意义下分别做 $(max,+)$ 卷积即可，时间 $O(n\log+DC\log C)$，空间 $O(n+C)$。

完全背包

物品体积 $\leq D$，容量为 $C$ 。注意到对于 $i>D$，有 $dp_i=max_{j+k=i}(dp_j+dp_k)$，且如果 $|j−k|>D$，我们始终可以调整得到 $|j−k|≤D$。

因此通过 $[dp_{j−D/2},⋯,dp_{j+D/2}]$ 以及 $[dp_{k−D/2},⋯,dp_{k+D/2}]$，可以暴力卷积得到 $dp_{j+k}$ 的值。

现在，假如我们知道了 $[dp_{k−D},⋯,dp_{k+D}]$，它卷自己可以得到 $[dp_{2k−D},⋯,dp_{2k+D}]$，因此采用倍增的形式可以快速计算出 $[dp_{C−D},⋯,dp_C]$，答案即为其中的最大值。

初始化的地方，暴力计算 $[dp_0,⋯,dp_{2D}]$ 即可，时间 $O(D^2\log C)$，空间 $O(n+D)$。

---

Reference：背包，子集和以及 (max, +) 卷积在特殊情形下的求法 - wlzhouzhuan - 博客园