背包问题

· · 个人记录

目录

  1. 01背包

  2. 完全背包

  3. 多重背包

  4. 混合背包

  5. 二维费用背包

一、01背包

01背包，意思就是要么是0要么是1，即每种物品仅有一件。

有 N 个物品，每件物品仅有 1 件，背包承重限度为 V。第 i 件物品重量为 c_i、价值为 w_i。求可行方案的最大价值。

Part 1 O(VN)算法1

通过简单分析，可以得出

  1. 无法一次求解，需要递推（动态规划）

  2. 显然，按物品的数量顺序递推（指“1件物品最大价值”\Rightarrow“2件物品最大价值”\Rightarrow……\Rightarrow“n件物品最大价值”的递推顺序）明显比按重量大小顺序递推（指“重量为1时的最大价值”\Rightarrow“重量为2时的最大价值”\Rightarrow……\Rightarrow“重量为n时的最大价值”）更快、更简单，则考虑按物品的数量顺序由小到大作为主循环

  3. 对于第 i 件物品，有两种选择：选；不选

则能得出解法：

状态

f_{i,j}\text{表示前i件物品中，放入重量为j的物品所能获得的最大价值}

转移方程及过程

f_{i,j}=\max(f_{i-1,j},f_{i-1,j-c_i}+w_i)

即 f[i][j]=max(f[i-1][j],f[i-1][j-c[i]]+w[i])

解析：对于“从第 i-1 件物品的选择转化到第 i 件物品的选择”有两种情况：

  1. 在选了 i-1 件物品的基础上，选择第 i 件物品，当前背包承重减去 c_i，当前价值加上 w_i

  2. 在选了 i-1 件物品的基础上，无所事事（跳过第 i 件物品的选择，即不选择第 i 件物品）

取最大值即可

得到转移方程，考虑过程为

for i=1..N
    for j=c[i]..V
        f[i][j]=max(f[i-1][j],f[i-1][j-c[i]]+w[i]);

for(int i=1;i<=n;i++){
    for(int j=c[i];j<=V;j++){
        f[i][j]=max(f[i-1][j],f[i-1][j-c[i]]+w[i]);
    }
}

解析：

  1. 第一层循环表示当前物品数量，循环顺序显然，不做解释

  2. 第二层循环表示重量，循环顺序无所谓，正反皆可（注意范围为 c_i\sim V）

Part 2 O(VN)算法2

考虑：对于每次转移，我们仅仅只需要 f_{i,...} 和 f_{i-1,...} 的值即可。用滚动数组滚掉第一维即可：

状态、转移方程及过程

f_{j}=\max(f_{j},f_{j-c_i}+w_i)

即 f[j]=max(f[j],f[j-c[i]]+w[i])

可得过程

for i=1..N
    for j=V..c[i]
        f[j]=max(f[j],f[j-c[i]]+w[i]);

for(int i=1;i<=n;i++){
    for(int j=V;j>=c[i];j--){
        f[j]=max(f[j],f[j-c[i]]+w[i]);
    }
}

解析：由于第二层循环（重量）是倒着来的，所以在第 i 层时 j 还没跑到 j-c_i 的时候，f_{j-c_i} 其实是在第 i-1 层重量为 j-c_i 的最大价值（因为第 i 层重量为 j-c_i 还没跑过）。这就满足了我们之前二维数组时的需求：判断 f_{i,j} 要看 f_{i-1,j} 和 f_{i-1,j-c_i}（因为重量是倒着跑的，所以在第 i 层重量为 j 的 f 数组还未被赋值时，当前的 f_j 和 f_j-c_i 其实都是在第 i-1 层时的值）。所以，第二层循环仅能倒着跑

Part 3 一些有用的优化&技巧

循环次数1

前面已经给出了，我们将第二层循环的 V..0 转化为 V..c[i]，即可将 \Theta(VN) 的复杂度转化为 O(VN)

循环次数2

注意，在背包九讲中，原作者将这里的代码和内容写错了。。。

该优化可以使 \Theta(VN) 转化为 O(VN) （虽然大部分时候并没什么用，不考虑预处理的时间的话并不会导致负优化）

考虑：由于最终我们仅需要知道 f_V 的值，所以在进行 i=n 时的转移时，我们仅需要知道 f_{V-c_n} 即可。所以，在 i=n-1 的转移中，我们仅需要算到 f_{V-c_n} 即可。同样，我们在 i=n-2 的转移中，只需要算到 f_{V-c_n-c_{n-1}}（注意，由于 Latex 的格式问题，此处应显示f[V-c[n]-c[n-1]]） 即可……以此类推，在 i=k 的转移时，我们仅需要知道 f_{V-\sum^n_{i=k+1}c_{i}} 即可。但是，如果当前物品的重量（即c_i）大于背包剩余空间（即V-\sum^n_{i=k+1}c_{i}），我们仍然需要考虑抛弃掉一些物品，在 f_{V-c_i} 的基础上选择该物品。所以，在第 i 件物品的选择上，我们可以只循环到：

\max(V-\sum^n_{k=i+1}c_{k},c_i)

得出代码（由于这里要用到后缀和，所以只写伪代码）

for i=1..N
    for j=V..max(V-sum(c[i+1..n]),c[i])
        f[j]=max(f[j],f[j-c[i]]+w[i]);

初始化

一般的题目可以分为两种：必须装满；可以不装满

考虑将无解的情况输出 -\infty

那么，对于必须装满的情况，我们只需要将所有除去 f_0 的位置全部初始化为 -\infty ，将 f_0 初始化为 0，最后判断 f_V 是否有解就行了。原因：我们可以看 f_0 为“装有价值和重量均为 0 的‘空’的位置”

对于不必须填满的情况，我们看作是不论重量大小都可以做为解，所以要将所有位置都初始化为 0。即每种情况先都视为“装着空气”。

Part 4 小结

01背包是最最最最基础的一种背包问题了，后面的大多数背包问题都是建立在01背包的基础上的

二、完全背包

有 N 个物品，每件物品有无数件，背包承重限度为 V。第 i 件物品重量为 c_i、价值为 w_i。求可行方案的最大价值。

分析：

  1. 每件物品有无数件

  2. 物品的选择没有顺序

Part 1 O(VN\sum \frac{V}{c_i}) 算法

由于害怕误导，不做代码展示和过多解释，仅做简单解释。

在01背包的基础上，枚举 k 表示该件物品使用的件数

状态+转移方程

\text{用}f_{i,j}\text{表示前}i\text{件物品，重量为}j\text{的最大价值} f_{i,j}=\max^V_{kc_i}f_{i-1,j-kc_i}+kw_i (0\le kc_i\le j)

即f[i][j]=max{f[i-1][j-k*c[i]]+k*w[i]},(0<=k*c[i]<=j)

显然，时间复杂度在大部分题目中并不允许，考虑优化

Part 2 转化为01背包的算法（一）

该方法在时间上较Part 1的算法有负优化，在空间上较Part 1的算法可能有负优化，所以同样不做展示和过多解释

考虑第 i 件物品仅能选择 \lfloor\frac{V}{c_i}\rfloor 件，我们可以将第 i 件物品转化成 \lfloor\frac{V}{c_i}\rfloor 件数量为 1 的物品。这样就可以按照01背包的方式来做了。

Part 3 转化为01背包的算法（二）

二进制拆分

该算法较Part 1&Part 2的算法有些许优化，使用了更高效的转化方法，但仍然不满足正常题目的需求，所以也不做展示和过多的解释

考虑对于第 i 件物品，枚举 k（满足 2^kc_i\le V,k>0），将其转化成 \{2^0c_i,2^0w_i\},\{2^1c_i,2^1w_i\},……,\{2^kc_i,2^kw_i\} 共计 k+1(\log V) 种物品。在实际操作时只需要将 k 从 1 枚举。

关于具体的证明可以到 附录 二进制拆分的简单证明 查看

Part 4 O(VN) 算法

该算法是在01背包算法的基础上建立的

状态

\text{用}f_i\text{表示重量为}i\text{的最大价值}

转移方程及过程

与01背包并无太大区别，仅仅只相差一个循环顺序

f_j=\max(f_j,f_{j-c_i}+w_i)

即 f[j]=max(f[j],f[j-c[i]]+w[i])

for i=1..N
    for j=c[i]..V
        f[j]=max(f[j],f[j-c[i]]+w[i]);

解析：

  1. 在第 i 次循环，重量为 j 时，f_j 的值取决于 f_j 和 f_{j-c_i}+w_i。思考一下，取值中的 f_j 应该是第 i 次循环中的值还是第 i-1 次循环中的值？如果是在01背包中，显然答案是后者。但在完全背包中，一个物品可以选无数次。而这里正着跑时，j-c_i 显然已经被算过了。这样就完成了完全背包的特性。所以，重量的循环只能正着跑

在背包九讲中，还提到了“上面的伪代码中两层for循环的次序可以颠倒”“这个结论有可能会带来算法时间常数上的优化”。本文不做解释和介绍。

Part 4 优化技巧

去重

存在 i,j，满足 c_i=c_j,w_i>w_j，则我们可以只考虑选择 i 这件物品，丢弃 j 这件物品。当然，如果数据不是随机的，那么该优化可能造成负优化

方法

可以选择用 n^2 的方式去重，也可以选择桶排（桶排时间快，但要看值域）来做，但由于鸢一折纸太可爱了，所以作者不能给出示例（这就是我不写代码的借口~~）。

三、多重背包

与完全背包很像，很多思考过程也与完全背包相似

有 N 个物品，每件物品有 n_i 件，背包承重限度为 V。第 i 件物品重量为 c_i、价值为 w_i。求可行方案的最大价值。

Part 1 O(VN\sum n_i) 算法

与完全背包类似，错误做法同样不做过多解释和展示。

状态+转移方程

\text{用}f_{i,j}\text{表示前}i\text{件物品，重量为}j\text{的最大价值} f_{i,j}=\max^V_{kc_i}f_{i-1,j-kc_i}+kw_i (0\le kc_i\le \min(n_i,\lfloor \frac{V}{c_i} \rfloor))

即f[i][j]=max{f[i-1][j-k*c[i]]+k*w[i]},(0<=k*c[i]<=min(n[i],V/c[i]))

Part 2 转化为01背包的算法（一）

与完全背包类似，同样不做过多解释和展示

考虑对于第 i 件物品，将其变为 n_i 件重量为 c_i，价值为 w_i，数量为 1 的物品

Part 3 转化为01背包的算法（二）

二进制拆分

考虑对于第 i 件物品，枚举 k（满足 2^kc_i\le V,k>0），将其转化成 \{2^0c_i,2^0w_i\},\{2^1c_i,2^1w_i\},……,\{2^{k-1}c_i,2^{k-1}w_i\},\{(n_i-2^k+1)c_i,(n_i-2^k+1)w_i\} 共计 k+1(\log V) 种物品。在实际操作时只需要将 k 从 1 枚举。

关于具体的证明可以到 附录 二进制拆分的简单证明 查看

Part 4 O(VN) 算法

注意，在某些题目中，该方法常数较大，有可能不如二进制拆分快。但在大部分情况下还是该算法更快一些的。

单调队列

思路+状态转方程

若当前重量为 j，对于第 i 个物品我们最多只能买 \lfloor \frac{j}{c_i}\rfloor 个。出于方便，我们将 \lfloor \frac{j}{c_i}\rfloor 记为 t。当然，可能还有一些剩余的空间，其大小为 j\bmod c_i，我们将其记为 m。可得 j=c_it+m

回看Part 1中的方程（这里我省略着写的）

f_{i,j}=\max(f_{i-1,j-kc_i}+kw_i)

其中，k\in [0,\min(\lfloor \frac{V}{c_i}\rfloor,n_i)]

在后面，我会用 l 来表示 \min(\lfloor \frac{V}{c_i}\rfloor,n_i)，即 k\in [0,l]

我们将刚刚得出的量代进去：

j-kc_i=(c_it+m)-c_ik=(t-k)c_i+m

得

f_{i,j}=\max(f_{i-1,(t-k)c_i+m}+kw_i)

令 t-k=k'

因为 t 是最多可选的，k 是当前要选的，那么 k' 就是当前不选的

可得出 k=t-k'

方程就变成了

f_{i,j}=\max(f_{i-1,c_ik'+m}+tw_i-k'w_i)

当然，对于第 i 件物品来说，无论如何 t 都是固定的，所以我们可以将 t 提出来

f_{i,j}=\max(f_{i-1,c_ik'+m}-k'w_i)+tw_i

现在，问题转化成了：

\text{对于}f_{i,j}\text{，求}\max(f_{i-1,c_ik'+m}-k'w_i)

而我们可以得出共有 l+1 个值（前面说过 k\in [0,l]）

考虑使用单调队列，用 O(V) 的时间得出

当然，考虑对于第 i 物品，f_{i,j} 可以影响 f_{i,j-(k+1)c_i} （前者为第 i 件物品不选，后者为选 k 件物品），所以我们分组来做

显然重量为 v 时，有 v\bmod c_i=(v+kc_i)\bmod c_i，则考虑对每个对 c_i 取模等于 b(0\le b<c_i) 的 v(v\le V) 的数分为一组。各组之间不会相互影响（证明：令该组中的第一个 v 满足 v=c_i+q，显然这一组中的每个 v 都可以写成这个形式且它们的 q 都相同，相互间的区别仅在于 c_i 的系数的值。那么就可以得出，当两个 v 的 q 相同时，这两个 v 一定在一个组中；相反，如果两个 v 的 q 不相同，那么它们一定不属于同一个组。而对于每个 v 而言，他所能影响到的仅仅只有值为 kc_i+q 的，所以每一个和它 q 不同的值，即不属于同一组的值，一定不能被影响）

考虑分组后，我们按组来做即可。

则总时间复杂度为 O(VN)

代码实现

见P1776
int c,w,num;
if(c==0){
    ans+=w*num;
    continue;
}int l=min(num,V/c);
for(int modse=0;modse<c;modse++){
    int t=(V-modse)/c;
    head=1,tail=0;
    for(int k=0;k<=t;k++){
        int New=f[k*c+modse]-k*w;
        while(head<=tail&&New>=q[tail].w)tail--;
        tail++;
        q[tail].id=k,q[tail].w=New;
        while(head<=tail&&q[head].id+l<k)head++;
        f[k*c+modse]=q[head].w+k*w;
        tmp=max(tmp,f[k*c+modse]);
    }
}

由于代码太麻烦，就不给出伪代码了

文中 modse 表示模数，head & tail 表示队列的头和尾的位置，ans 表示不占体积的物品的价值总值，tmp 表示所有物品中解的最大值（不计算不占体积的物品的价值）。注意，代码中给出的是处理一件物品的过程

四、混合背包

这里的混合背包指的是混合01背包、完全背包、多重背包

有 N 个物品，每件物品有 n_i 件，背包承重限度为 V。第 i 件物品重量为 c_i、价值为 w_i。求可行方案的最大价值。

Part 1 引导

考虑在前三种背包中，我们通常将每件物品分着来做（将每件物品分别考虑方程）。而且，不同物品的方程不同，不会影响到结果

后面的两个部分是证明“不同物品的方程不同，不会影响到结果”这句话的，如果您已经理解，可以直接转到Part 2。

我们可以将完全背包和多重背包转化为01背包（虽然实际上我们的解法不同，但在理论上它们是可以转化的）

证明：由于对于第 i 件物品，若有 x 个，我们最多可以选择 \min(\lfloor \frac{V}{c_i} \rfloor ,x) 个。无论 x 取任何符合有意义的值，这句话都一定是对的（x=\infty 同样成立）

我们将其转化为 x 件物品，每件物品的数量都为 1，价值和重量不变，即转化为01背包。

所以，调换方程不影响结果

Part 2 算法

算法时间复杂度视个人想法来定

有了Part 1的证明，我们只需要对每件物品分别做方程即可。当然，每件物品你可以选择时间复杂度不同的方程。

伪代码：

for i=1..N
    if 物品i为01背包
        01背包的方程...
    if 物品i为完全背包
        完全背包的方程...
    if 物品i为多重背包
        多重背包的方程...

条件符合的情况下，时间复杂度可以达到 O(VN)

五、二维费用背包

二维费用背包即每个物品有两种费用，当你选择这件物品时，两种费用要同时花费。

有 N 件物品，代价 1 的最大值为 A，代价 2 的最大值为 B。每件物品有 a_i,b_i 两个代价值，价值为 w_i。当你选择第 i 件物品，你将花费 a_i 的代价 1 和 b_i 的代价 2。

注意，后面的一些背包问题不再考虑每件物品的数量，因为他们都可以与前文中的背包问题相对应。出于方便，我们这里考虑的是01背包的做法。

这种问题分布其实比较普遍。某些背包问题表面上只有一种费用，但题目中要求最多只能选 m 件物品，也相当于给每件物品附上了第二种价值。

Part 1 复数域上的背包问题（不做详解）

在背包九讲中有提到

我们可以将一件物品转化为复数的形式，那么问题就转化成了复数域上的背包问题了。

Part 2 O(ABN) 算法

状态

f_{i,u,v}\text{表示前}i\text{件物品代价}1\text{为}u\text{，代价}2\text{为}v\text{的最大价值}

转移方程及过程

根据前面的经验，我们可以轻松得出转移：

f_{i,u,v}=\max(f_{i,u,v},f_{i,u-a_i,v-b_i}+w_i)

过程也同样简单，只给出伪代码

for i=1..N
    for u=1..A
        for v=1..B
            f[i][u][v]=max(f[i][u][v],f[i][u-a[i]][v-b[i]])

这里第二维循环和第三维循环顺序可以随便交换，不影响

简单优化

因为是01背包，状态第一维可以滚掉（将第二维和第三维的循环顺序反过来，即从小到大变为从大到小）。即便是完全背包和多重背包，仍然可以利用前面讲的方式优化。

附录 二进制拆分的简单证明

以后有空再写

附录 习题

echo的背包题单

01背包

P1048 [NOIP2005 普及组] 采药

P1060 [NOIP2006 普及组] 开心的金明