背包9讲（大概

0/1背包

模型

多种物品,每种物品只有一个.求能获得的最大总价值.
思路

不选择第 $i$ 件物品,就相当用 $i-1$ 件物品,填充了体积为 $v$ 的背包.

选择第 $i$ 件物品，相当于对 $i-1$ 件物品填充得到的体积为 $v-c[i]$ 的背包,再填充第 $i$ 个物品得到体积为 $v$ 的背包.
转移方程
$f[i][v]=\max(f[i-1][v],f[i-1][v-c[i]]+w[i])$
$f[i][v]$ 代表用 $i$ 件物品填充为体积为 $v$ 的背包得到的最大价值.
注

一般考虑倒序枚举

这样 $f_i$ 不会被 $i$ 以前的状态影响,更新也不会影响其他位置的状态.

-代码

1
2
3

for(rei i=1;i<=n;i++)//枚举物品
    for(rei j=V;j>=c[i];j--)//枚举体积
        f[j]=max(f[j],f[j-c[i]]+w[i]);//状态转移方程.

完全背包

模型

每种物品有无限多个,可重复选取.

~~- 思路没有了（与0/1类似（逃~~

转移方程
$f[i][v]=\max(f[i-1][v],f[i-1][j-k\ast c[i]]+k\ast w[i])$
注

顺序枚举

01背包与完全背包的枚举顺序的不同处
代码

1
2
3

for(rei i=1;i<=n;i++)//枚举物品
    for(rei j=c[i];j<=V;j++)//枚举体积
        f[j]=max(f[j],f[j-c[i]]]+w[i]);//状态转移.

多重背包

模型

有了个数的限制

~~- 思路不想写了~~

朴素做法就是把每种物品都拆成 size 个物品跑0/1背包

优化

二进制拆分

易知 $size_i=2^0+2^1+2^2+2^3…+2^x+y$

其 $k$ 是任意数，$y$ 是一个不为2的整数次幂的数

所以在多重背包中，可以将个数的限制如此分解

每个分解看成一个物品

(如： $2^2$ 看成 $1$ 个物品，该物品 $val=4\cdot val_i \space, \space w=4\cdot w_i$)

如此进行后就是 $\log (size)$

代码

struct Good{
    int v,w;
};
vector<Good> g;

···
//对每个读入的v,w,s
for(rei k=1;k<=s;k*=2){
    s-=k;
    g.push_back({v*k,w*k});
}
if(s) g.push_back({v*s,w*s});

//总dp
for(auto good:g){
    for(rei j=m;j>=good.v;--j){
        f[j]=max(f[j],f[j-good.v]+good.w);
    }
}

单调队列优化

这是一个最基本的转移式子

$f[i][j]=\max\left(f[i−1][j],f[i−1][j−k\ast c[i]]+k\ast w[i]\right)$

其中 $k \in \left[1,\min\left(\left\lfloor\frac{V}{c[i]}\right\rfloor,num[i]\right)\right]$

下面用 $lim$ 表示 $\min\left(\left\lfloor\frac{V}{c[i]}\right\rfloor,num[i]\right)$

易得 $f[i][j−k\cdot c[i]]$ 会被 $f[i][j−(k+1)\cdot c[i]]$ 影响

(体积为 $c[i]$ 的物品填充体积为 $j−(k+1)\cdot c[i]$ 的背包,会得到体积为 $j−k\cdot c[i]$ 的背包)

$f[i][j]$ 将会影响 $f[i][j+k\cdot c[i]]　\left(j+k\cdot c[i]\leq V\right)$

注意这里影响的传导，往取模上想

所以我们可以根据对 $c[i]$ 取模得到的余数进行分组.

即可分为 $0,1,2,3…c[i]−1$ 共 $c[i]$ 组

每组之间的状态互相没有影响

且每组中位置靠后的受前面的影响

进行一些推导

注： $\left\lfloor \frac{j}{c[i]} \right\rfloor即是全选状态下的物品个数$
$\because j=\left\lfloor \frac{j}{c[i]} \right\rfloor \ \cdot \ c[i] \ +\ j\% c[i]$ $\begin{aligned} j−k∗c[i]&=\left\lfloor \frac{j}{c[i]} \right\rfloor\cdot c[i] \ +\ j\% c[i] \ −\ k\cdot c[i] \\ &=\left(\left\lfloor \frac{j}{c[i]} \right\rfloor \ −\ k\right)\cdot c[i]+j \% c[i] \end{aligned}$
令 $\left(\left\lfloor \frac{j}{c[i]} \right\rfloor−k\right)=k^{‘}$

最原始的状态转移方程中第二状态 :

$f[i][j−k\cdot c[i]\ ]+k\cdot w[i]$ 代表选择 $k$ 个当前 $i$ 物品

根据单步容斥：全选−不选=选

因此 $\left\lfloor \frac{j}{c[i]} \right\rfloor \ −\ \left(\left\lfloor \frac{j}{c[i]} \right\rfloor−k\right)=k$
$\because \left(\left\lfloor \frac{j}{c[i]} \right\rfloor−k\right)=k^{'}$ $\therefore f[i][j]=\max\left( \ f[i−1][\ k^{'}\cdot c[i]+j \% c[i] \ ] \ + \ \left\lfloor \frac{j}{c[i]} \right\rfloor\cdot w[i]−k^{'}\cdot w[i]\right)$
而其中 $\left\lfloor \frac{j}{c[i]} \right\rfloor\cdot w[i]$ 为一个常量(因为 $\left\lfloor \frac{j}{c[i]} \right\rfloor$ 已知)

要求的状态变为
$f[i][j]=\max\left(f[i−1][ \ k^{'}\cdot c[i]+j\% c[i] \ ]−k^{'}\cdot w[i]\right)+\left\lfloor \frac{j}{c[i]} \right\rfloor\cdot w[i]$ $\because k \in [1,lim]$ $\therefore k^{'} \in \left[\left\lfloor \frac{j}{c[i]} \right\rfloor−k,\left\lfloor \frac{j}{c[i]} \right\rfloor\right]$
当前的 $f[i][j]$ 求解的就是为 $lim+1$ 个数对应的 $f[i−1][k^{‘}\cdot c[i]+j\% c[i] \ ]−k^{‘}\cdot w[i]$ 的最大值.

(之所以为 $lim+1$ 个数,是包括当前这个 $j$ ,还有前面的物品数量)

将 $f[i][j]$ 前面所有的 $f[i−1][k^{‘}\cdot c[i]+j\% c[i]\ ]−k^{‘}\cdot w[i]$ 放入一个队列.

问题转化为求这个最长为 $lim+1$ 的队列的最大值 $+\left\lfloor \frac{j}{c[i]} \right\rfloor\cdot w[i]$

代码

for(rei i=1;i<=n;i++){//枚举物品种类
    cin>>c[i]>>w[i]>>num[i];//c,w,num分别对应 体积,价值,个数
    if(V/c[i] < num[i]) num[i]=V/c[i];//求lim
    for(rei p=0;p<c[i];p++){//枚举余数
        head=tail=0;//队列初始化
        for(rei k=0;k<=(V-p)/c[i];k++){
            rei x=k;
            rei y=f[k*c[i]+p]-k*w[i];
            while(head<tail && q[head].pos<k-num) ++head;//限制长度
            while(head<tail && q[tail-1].value<=y) --tail;
            q[tail].value=y,q[tail].pos=x;
            ++tail;
            f[k*c[i]+p]=q[head].value+k*w[i];
            //单调队列维护的是前i-1种的状态最大值.
            //因此这里加上k*w[i].
        }
    }
}

混合背包

思路

拆开分别算即可

代码

for(rei i=0;i<n;++i){
    rei v,w,s;
    scanf("%d%d%d",&v,&w,&s);
    if(s<0) things.push_back({-1,v,w});
    else if(!s) things.push_back({0,v,w});
    else{
        for(rei k=1;k<=s;k*=2){
            s-=k;
            things.push_back({-1,v*k,w*k});
        }
        if(s>0) things.push_back({-1,v*s,w*s});
    }
}
for(auto thing : things){
    if(thing.kind<0){
        for(rei j=m;j>=thing.v;--j)
            f[j]=max(f[j],f[j-thing.v]+thing.w);
    }
    else{
        for(rei j=thing.v;j<=m;++j)
            f[j]=max(f[j],f[j-thing.v]+thing.w);
    }
}

二维费用背包

模型

有容量 $v$ 与重量 $w$ 两个限制
思路

限制扩展到二维即可

代码

for(rei i=0;i<n;++i){
    rei a,b,c;
    scanf("%d%d%d",&a,&b,&c);
    for(rei j=v;j>=a;--j)
        for(rei k=m;k>=b;--k)
            f[j][k]=max(f[j][k],f[j-a][k-b]+c);
}

分组背包

模型

每组若干个物品，每个物品组内的物品互斥（只能选一个）
转移方程
$f[k][v]=\max(f[k-1][v],f[k-1][v-c[i]]+w[i])$

代码

for(rei i=0;i<n;++i){//每一组
    rei s;
    scanf("%d",&s);
    for(rei j=0;j<s;++j) scanf("%d%d",&v[j],&w[j]);
    for(rei j=m;j>=0;--j)//枚举体积
        for(rei k=0;k<s;++k)//枚举物品
            if(j>=v[k])
                f[j]=max(f[j],f[j-v[k]]+w[k]);
}

有依赖的背包

模型

物品间有依赖关系，且依赖关系组成一棵树

为选取某节点，必须选取该节点的父节点

eg:选课问题
思路

对每个点，$\text{dfs}$ 其子节点再 $\text{dp}$

特别注意子节点 $\text{dp}$ 体积时要给父节点留下空间

详见代码

代码

void dfs(int u){
    for(rei i=head[u];i!=-1;i=Next[i]){
        rei son=ver[i];
        dfs(son);
        for(rei j=m-v[u];j>=0;--j)//注意，这里要留出当前点的体积再去dp其子节点
            for(rei k=0;k<=j;++k)
                f[u][j]=max(f[u][j],f[u][j-k]+f[son][k]);
    }
    for(rei i=m;i>=v[u];--i) f[u][i]=f[u][i-v[u]]+w[u];//加上当前点
    for(rei i=0;i<v[u];++i) f[u][i]=0;
}

noone___'s blog

背包问题