三种基本背包

01背包

$n$个物品，费用$c_i$，价值$w_i$，求最大价值，转移方程如下：

即只考虑第$i$个物品时，有放和不放两种策略，转移方程前一项为不放，后一项为放。

考虑优化空间：

for(int i=1;i<=n;++i)
    for(int v=maxv;v>=c[i];--v)// maxv为最大容量，注意递推顺序，从大到小
        dp[v]=max(dp[v],dp[v-c[i]]+w[i]);

此时$dp[v]$表示容量为$v$时能获得的最大价值。

实际上此时$dp[v]$等价于$dp[i-1][v]$，$dp[v-c_i]$等价于$dp[i-1][v-c_i]$。

相当于每个物品的状态只由上一个物品的各个状态推得。

而更新顺序则能保证每种物品只能被选一次，因为较大的容量不会被用当前物品更新过的小容量影响。

初始化的一些细节：

1. 恰好装满：$dp[0]=0$，其余为负无穷。此时$dp[maxv]$为最优解，若其等于负无穷，说明无论如何都不能恰好装满
2. 只希望价值最大：初始全设为$0$即可

事实上，初始态的dp数组表示没有任何物品时可以放入背包的合法状态。

如果要求装满，除了容量为$0$的背包可以被“装满”（容量为$0$背包的装满等价于什么都不装）之外，其他所有背包都不可能合法。

但是只希望价值最大的时候任何容量的背包都有不装的合法状态。

可以把$dp$数组理解成一个一个容量不同的背包，这在后面的某些特殊的多重背包会有用处。

01背包有一种常数优化：

for(int i=1;i<=n;++i) {
    int bound=max(maxv-(c[i]+...+c[n]),c[i])
    // (ci+...+cn)是当前物品以及其后所有物品的费用之和
    for(int v=maxv;v>=bound;--v)
    ...
}

考虑的是这样一种情况：即使$i$到$n$的所有物品都放入背包之后，剩余空间仍然大于$c_i$。

如果满足了优化条件，则对于$i+1$到$n$物品，其$v-c_i$的值最大也就只有$maxv-(c_i+…+c_n)$，所以只需要计算到这儿为止即可。

完全背包

每种物品有无限种，转移方程如下：

两个优化：

1. 如果两个物品$i$，$j$满足$c_i<=c_j$并且$w_i>=w_j$，则物品$j$不会起到任何作用，对于所有的$j$一定可以把它替换成更便宜的$i$
2. 可以直接去除所有费用大于$v$的物品，并且利用桶排序在$O(n)$内找到费用相同的物品当中价值最大的那一个

转化为01背包：

1. 把每个物品看成k个独立物品，$k=maxv/c_i$，$O(k)$时间内完成遍历
2. 把每个物品看成k个独立物品，$k=maxv/c_i$，对k进行二进制分解，可以在$O(logk)$内完成遍历（在多重背包当中有用）
3. 使用两重循环完成：

    for(int i=1;i<=n;++i)
        for(int v=c[i];v<=maxv;++v)// 注意遍历顺序，由小到大
            dp[v]=max(dp[v],dp[v-c[i]]+w[i]);
   

与$01$背包只有遍历顺序上的不同！

$01$背包中由大到小的理由是每种物品只有一次被访问到的机会，要确保$dp[v-c_i]$在被调用时是上一轮遍历的结果，完全背包则没有这种限制。

事实上转移方程可以写成：

注意方程的第二项$dp[i][v-ci]$是以$i$作为参照对象的，因为第$i$个物品可以选择多次！

多重背包

每种物品限制数量，转移方程：

基本思路

把每种物品都看成$n[i]$个独立的物品，全部拆开，套用$01$背包。

总的时间复杂度为$O( \sum n_i *maxv)$，物品数量过大时必然超时。

二进制优化

首先明确二进制可以用来表示所有数字，可参见二进制分解。

我们只需要进行如下的拆分即可：

例如：$n[i]=19$，那么$19=1+2+4+8+5$

注意：

伪代码如下：

if(n[i]*c[i]<=maxv)// 想选几个就选几个
    完全背包(ci,wi);
else {
    int sum=1
    while(sum<=n[i]) {// 二进制分解
        01背包(sum*ci,sum*wi);
        n[i]-=sum;
        sum*=2;
    }
    01背包(n[i]*ci,n[i]*wi);// 计算剩余部分
}

单调队列

对某一类dp，当转移方程类似于如下形式时：

可以使用单调队列保存所有的$dp[j]$，每一次取出最大/最小值即可。

关于单调队列参见单调队列。

四种背包的混合情况

分类处理即可，伪代码如下：

for(int i=1;i<=n;++i)
    if(满足01背包) 套用01背包;
    else if(满足完全背包) 套用完全背包;
    else if(满足多重背包) 套用多重背包;

二维费用的背包问题

此时一个物品有两种花费，即$c1_i$和$c2_i$，需要同时考虑。

转移方程如下（以01背包为例）：

实际上也可以进一步优化成二维数组：

for(int i=1;i<=n;++i)
    for(int v=maxv;v>=c1[i];--v)
        for(int u=maxu;u>=c2[i];--u)// 注意遍历顺序
            dp[v][u]=max(dp[v][u],dp[v-c1[i]][u-c2[i]]+w[i]);

完全背包与多重背包的解法类似，多加一维限制即可。

背包问题的变法

要求总价值/总物品数量最大/小

只需要修改dp方程中的max/min即可。

输出最优值方案

此时需要用一个额外的数组记录每个值的最优状态是从哪儿转移过来的。

现在使用额外数组$g[i][v]$：

实现g数组的更新时可以采用$ifelse$判断而不使用$min/max$函数：

if(dp[i-1][v]>=dp[i-1][v-c[i]]+w[i])
    g[i][v]=0;
else 
    g[i][v]=1;

注意取等号的条件，如果希望携带的物品尽量少，那么应当采取上面的写法。

输出最优解的方法：

i=N,v=maxv;
while(i>0) {
    if(g[i][v]==1) {
        选中i;
        v-=ci;
    }
    --i;
}

事实上，也可以不使用g数组保存最优解，利用下面的结论即可：

但是把二维数组压缩到一维数组之后上面的方法就不太适用，因为$dp[v]$在被更新之后就不能再判断它从哪儿更新而来。

求字典序（物品编号越小字典序越大）最小的最优方案

考虑如下两种情况：

1. 假设有一个存在物品$1$的最优方案，那么答案中一定有$1$，问题转化为： 容量为$maxv-c_1$，物品为$2…n$的子问题
2. 如果不存在这样的方案，问题转化为： 容量为$maxv$，物品为$2…n$的子问题

不妨把物品逆序排列，即从$n$到$1$遍历。

如果下式成立则代表选中了当前物品：

求可行的种数方案（以完全背包为例）

转移方程：

初始化一定要设定$dp[0][0]=1$，否则所有的$dp$值都会为$0$。

实际上上述方程亦可以压缩到一维数组当中：

memset(dp,0,sizeof(dp));
dp[0]=1;
for(int i=1;i<=n;++i)
    for(int v=c[i];v<=maxv;++j)
        dp[v]+=dp[v-c[i]];

考虑下列问题：

对于面值为$c[i]$的硬币，个数有$d[i]$个，用无穷多个$c[i]$凑出$tot$的合法方案数是按照上述方法求解出的$dp[tot]$。

但是不合法方案数呢？

不合法方案数为：

这意味着多于$d[i]$个的方案全部不合法。

在一些硬币数量较少的题目中，可以预处理出完全背包下的合法方案数，再考虑硬币个数的限制，往往还需要容斥（奇加偶减）。

例如用面值为c1和c2的硬币，个数分别为d1、d2，凑出tot的合法方案数是：

上式中$dp[tot]$是按照完全背包求解出的方案数。

求最优解个数（以01背包为例）

代码如下：

for(int i=1;i<=n;++i) {
    dp[i][v]=max(dp[i-1][v],dp[i-1][v-c[i]]+w[i]);
    g[i][v]=0;
    if(dp[i][v]==dp[i-1][v])
        g[i][v]+=g[i-1][v];
    if(dp[i][v]==dp[i-1][v-c[i]]+w[i])
        g[i][v]+=g[i-1][v-c[i]];
}

上式中$g[i][v]$表示在$i$个物品容量为$v$时候的最优解个数。

同样初始化需要设定$g[0][0]=1$，否则求解出来$g$数组会全$0$。

求第k优解

给出$dp[i][v][k]$，三维分别代表：前$i$个物品、背包大小为$v$、第$k$优解的值。

显然$dp[i][v][1]…dp[i][v][k]$是有序排列的。

而$dp[i][v][k]$是由$dp[i-1][v][k]$和dp$[i-1][v-c[i]][k]+w[i]$两个有序序列合并而来。

此时可以用类似归并排序的方法，时间复杂度$O(k)$。

分组背包

$n$个物品，总容量为$maxv$，费用$c_i$，价值$w_i$。

物品被分成了多组，每组最多选择一件物品。

那么策略实际上只有两种：选本组的某一件或者本组中一件都不选。

$dp[k][v]$表示前$k$组花费$v$的最大收益，转移方程如下：

其中物品$i$属于第$k$组。

写成伪代码形式如下：

for 所有的组k
    for(int v=maxv;v>=c[i];--v)
        for 所有的i属于组k
            dp[v]=max(dp[v],dp[v-c[i]]+w[i]);

一个小小的优化：

对同一组的两个物品i和j，如果存在c[i]<=c[j]&&w[i]>=w[j]，那么物品j一定不可选。

有依赖的背包问题

类似于一定要先选中了物品$i$才能选物品$j$的关系。

假设物品$i$为“主件”，物品$j$为“附件”，那么策略集合如下：

1. 一个也不选
2. 只选择主件
3. 选择主件和附件$1$
4. 选择主件和附件$2$
5. 选择主件、附件$1$和附件$2$
6. ……

策略太多，用转移方程没办法表示。

但是不难发现所有的选择策略都是互斥的，也即上述的种种策略中只能挑选一种。

那么一个主件和它的所有附件构成的策略集合就可以看成一个分组。

对于某种策略，比如：选择主件和附件$1$而言，

这个策略就相当于这个分组中的一个物品：

他的价值$=$主件价值$+$附件$1$价值，他的花费$=$主件花费$+$附件$1$花费。

为了应用上述优化策略，可以先对附件进行$01$背包，得到$dp[0]…dp[maxv]$。

把主件的花费$C$和价值$W$考虑进去，相当于此时构造了一个：

$maxv-C+1$个物品的物品组，物品组中$C+k$费用的物品价值为$dp[k]+W$。

$dp$的每一项都是一个物品，每一个物品对应的是一种附件的选择策略，多的那一种策略是只选主件。