算法与数据结构学习——01背包问题常数优化算法对问题解集的影响

再述 01 背包问题

本篇博文使用题目及符号的习惯表达方式均来自于《背包问题九讲》。

背包问题相信大家都不陌生，动态规划算法学习过程中不得不提得经典系列问题，而 01 背包问题又是系列问题得基础，在编程实现过程中，我们常会使用空间优化与常数优化来加速程序的执行，在程序设计竞赛中我们关注点在程序的运行结果是否与标程的运行结果是否一致，但对于优化的影响却不甚关心，我记得在自己学习编译原理优化一章时，徐老师常常谈起优化的代价，今天这篇博文主题便是这个经典问题空间优化与常数优化的影响与代价。

对原题目非常熟悉的请直接跳过前面题目和思路以及优化方法介绍，阅览最后两节内容。

题目

有\(N\)件物品和一个容量为\(V\)的背包。放入第\(i\)件物品耗费的费用是\(C_i^1\)，得到的价值是\(Value_i\)。求解将哪些物品装入背包可使价值总和最大。

基本解题思路

因为每种物品只有一件，选择只有放（1）、不放（0）两种状态，所以称这类问题为 01 背包问题。

该问题对应的子问题为：前\(i\)件物品放入背包得到的最大价值。，根据该子问题，我们定义状态\(F[i,v]\)为前\(i\)件物品放入限制重量为\(v\)所能得到的最大价值，然后我们可以想出状态转移方程。

\[F[i,v] = max \{ F[i-1,v] , F[i-1,v-C_i] + Value_i \}\]

其含义为：逐个拾取编号问题过程中，拾取\(i\)号且背包限制为\(v\)重量时（\(F[i,v]\)），其只由两种状态转移而来，不选择该物体（则状态同相同限重量拾取上个物体时的状态 \(F[i-1,v]\)），选择该物体（则状态由上次选择时，限重为当下限重减去此次拾取物体重量的状态转移而来\(F[i-1,v-C_i]+Value_i\)）。

最优子结构性质与无后向性是可证的，见下一节附加内容。

原文特别强调了上述转移方程的重要性，也做了相应的解释：

这个方程非常重要，基本上所有跟背包象关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下：“将前\(i\)件物品放入容量为\(v\)的背包中”这个子问题，若只考虑第\(i\)件物品的策略（放或不放），那么就可以转化为一个只和前\(i-1\)件物品相关的问题。如果不放第\(i\)件物品，那么问题就转化为“前\(i-1\)件物品放入容量为\(v\)的背包中”，价值为\(F[i-1,v]\)；如果放第\(i\)件物品，那么问题就转化为“前\(i-1\)件物品放入剩下的容量为\(v-C_i\)的背包中”，此时能获得的最大价值就是\(F[i-1,v-C_i]\)再加上通过放入第\(i\)件物品获得的价值\(Value_i\)。

伪代码描述：

1
2
3
4
F[0,0..V] ← 0
for i ← 1 to n
    for v ← w[i] to V
        F[i,v] ← max{F[i-1,v] , F[i-1,v-w[i]]+v[i]}

附加：最优子结构证明

学习自博客01 背包存在最优子结构的证明

表述：

\(n\)为背包重量限制，\(w[i]\)为\(i\)物体重量，\(v[i]\)为\(i\)物体价值，如果\((z_1,z_2 \cdots z_k)\)是问题\(f_k(n)\)的最优解，那么

  1. 对于任意\(1 \le j \le k\)，有\(z_j = 1\)（确定\(j\)物体状态为取），则有\((z_1,z_2 \cdots z_{j_1} , z_{j+1} , z_{j+2} \cdots z_k)\)是问题\(f_{k-1}(n-w[j])+ v[j]\)的最优解
  2. 对于任意\(1 \le j \le k\)，有\(z_j = 0\)（确定\(j\)物体状态为不取），则有\((z_1,z_2 \cdots z_{j_1} , z_{j+1} , z_{j+2} \cdots z_k)\)是问题\(f_{k-1}(n)\)的最优解。

这里 \(i\) 表示子问题的规模，表述为将 \(i\) 个物品放入容量为\(v\)的背包中，

证明（反证法）：

假设子问题不是最优解，对于情况 1，假设存在\((z_1',z_2' \cdots z_{j-1}' , z_{j+1}' ,\cdots z_k')\) 是子问题的最优解，那么 \(f_k(n)\)的最优解将会是\((z_1',z_2' \cdots z_{j-1}' , z_j , z_{j+1}' \cdots z_k')\)，与假设矛盾。

空间复杂度优化

由于要使用\(dp[n][v]\)状态空间，如果储存全部状态，根据伪代码思路，该动态优化算法的时间和空间复杂度均为\(O(VN)\)，汽中时间复杂度应该已经不能再优化了，但空间复杂度却可以优化到\(O(V)\)。

我们观察状态转移方程

\[F[i,v] = max \{ F[i-1,v] , F[i-1,v-C_i] + Value_i \}\]

我们每轮计算前\(i\)个在不同限重背包的最优值时，利用的状态只有\(i-1\)时的状态，也即上一轮外层循环得到的值，据此我们可以使用一些优化方法。

滚动数组

每次都使用固定的几个存储空间，来达到压缩。主要应用在递推或动态规划中。

代码描述

1
2
3
4
5
6
7
8
9
10
11
for (i=1 ;i <= n; i++)
{
    for (v = w[i] ; v <= V ; v++)
    {
        dp[1][v] = max(dp[0][v],dp[0][v-w[i]]+v[i]);
    }
    // 一轮更新结束后统一翻转
    for (v = 0; v<=V ; v++){
        dp[0][v] = dp[1][v];
    }
}

当然我们还发现状态转移方程中，只会利用背包限重状态小于等于要更新状态的已知状态，所以我们按逆序（从大到小）遍历内层循环，就可以避免在同一轮外层循环中先更新的影响后更新的值，由此修改滚动数组代码。

1
2
3
4
5
6
7
8
9
for (i=1 ;i <= n; i++)
{
    for (v = V ; v >= w[i] ; v--)
    {
        dp[1][v] = max(dp[0][v],dp[0][v-w[i]]+v[i]);
        dp[0][v] = dp[1][v];
    }

}

一维数组

那既然逆序已经避免同一轮更新中先更新的影响后更新的值，实际上滚动数组也非必要了。我们使用一维数组便可实现状态转移，并且保证计算\(dp[v]\)时，\(dp[v-w[i]]\)保存的是对应二维\(dp[i-1][v-w[i]]\)的值。

1
2
3
4
5
6
7
8
for (i=1 ;i <= n; i++)
{
    for (v = V ; v >= w[i] ; v--)
    {
        dp[v] = max(dp[v],dp[v-w[i]]+v[i]);
    }

}

时间复杂度常数优化

伪代码中

1
2
for i ← 1 to n
    for v ← V to w[i]

原作者给出可以优化为\(V \quad to \quad max(V − \sum_i^N C_i, C_i)\)。我个人认为可以严格到\(V \quad to \quad max(V - \sum_{i+1}^N C_i,C_i)\)。

1
2
for i ← 1 to n
    for v ← V to max(w[i],V-(w[i+1]+...+w[n]))

背包九讲中没有对这一优化做阐述，我自己的理解是这样的：

再回过头来看状态转移方程。

\[F[i,v] = max \{ F[i-1,v] , F[i-1,v-C_i] + Value_i \}\]

我们固定某一限重状态随\(i\)递增的变化，不妨研究与最终答案相关的，\(final(i)= F[i][V]\)。我们发现在\(i\)递增一轮过程中。\(final\)只会变动一次，且只有两个可能的方向，不变（延续\(i\)上一轮递增后得到的结果），改变（受\(F[i-1][V-w[i]]\)影响）。

如果我们将，可以影响\(final\)的所有限重状态，随\(i\)减小（逆序），画出来，我们可以发现能够影响到答案（最终状态）的边界是逐渐减小的。

我们可以发现，能够影响\(final\)的重量状态是有限的，并且随\(i\)减小，可影响的状态逐渐扩张，最后一次只有\(final=dp[n][V]\)单一状态影响最终答案（因为它本身就是最终答案），每一轮可能影响到\(final\)的边界应是，\(max(V - \sum_{i+1}^N Value_i,C_i)\)，这里可以补充一下，原作者认为是求和下限应为\(i\)，带入最后\(i=N\)我们发现在最后一轮除了更新\(dp[N]\)还更新了其他与最终答案无关的状态，所以我觉得这个更严格的界限是正确的。

反过来想也可以，在计算\(dp[v]\)时，若某一限重状态最终能够影响\(final\)，必然要经过几轮\(i\)递增（理想状态是，\(dp[v+w[i+1]\)每次都能受到影响），这也提醒我们，某一状态影响最终结果是需要一定时间限制的，在\(i\)逐渐靠近\(n\)时，即便我们遇到重量很小但是价值很大的一颗“金子”，我们也不一定需要从它的重量开始更新状态。

举例来讲比如最后三个物体是

1
2
3
4
5
// n = 10   V = 50
// 当前dp[50]=150
w[n-2]=2  v[n-2]=100 //金子
w[n-1]=5  v[n-1]=40
w[n]=3    v[n]=50

此时\(w[i] = 2\),\(V-sum=42\)（按照底为\(i+1\)的求和）。如果只是为了获得正确的\(dp[50]\)，我们需要从\(v=50\)更新到\(v=42\)就够了呢？还是说要更新到\(v=2\)，显然，我们更新到\(v=42\)就够了，即便后面两个物体在最优解中都要取，\(dp[42]\)会影响下一轮的\(dp[47]\)，进而影响最终的\(dp[50]\)。

Special 优化的代价

优化不是无代价的

承上面例子，显然根据常数优化算法，我们最终可以得到正确的\(dp[50]\)，但我们在想，有没有少些什么？

很明显啊，在倒数第三轮外层循环我们没有计算新的\(dp[2]\)（而大概率碰到金子，2 格背包我们应该捡起来啊！），那么不更新的代价是什么呢？

针对题目，影响最终答案么？

不影响。

不针对题目，影响答案么？

影响，因为改变了状态空间解集。

朴素二维动态规划得到的解集

\(dp[n][V]\)储存了（在该遍历序下）任意小于序长度前缀，任意小于最大限制容量的解集。也即在不增删修改物品条件下，后续满足上述条件的任意询问\(Q_1\)，都可以在\(O(1)\)的时间给出答案。

一维压缩空间优化得到的解集

\(dp[V]\)储存了长度等于序长，任意小于最大限制容量的解集。同样，不改变物体，对该序询问容量小于限制的背包问题\(Q_2\)，都可以在\(O(1)\)的时间给出答案，但是如果想询问前缀问题（而非序长），则不能获得，因为在外层循环迭代中，没有保留这部分结果。

空间优化+常数优化的解集

只能保证\(dp[i],i=V\)单个值是正确的，而其他值均无意义。

这些发现很明显在提醒，如果关注单捷，那么空间+常数优化自然是很好的选择，但是如果数据固定而频繁询问，那么朴素方法或许才是最好的，优化不应该是盲目的，有些优化需要我们理解背后更深的意义及影响，才能更好的应用于我们程序中

本来这篇文章只想讨论这个内容，不过写着写着就补充了许多其他内容（飘了），希望和大家今后继续关注这些不该被忽略的小细节 hh。