从背包问题看动态规划

我们不从枯燥难懂的理论知识讲起，首先先让我们看第一个问题：

有 N 件物品和一个体积为 V 的背包。放入第 i 件物品耗费的体积是 Ci ，得到的价值是 Wi。求将哪些物品装入背包可使价值总和最大？

这是一个最简单的**【01】背包问题**，一眨眼看到这个问题时，我们可能会想到这样的一种解法，题目中不是要求我们求价值总和最大吗？那我们先把所有物品按价值进行排序，然后从价值最大物品开始放入背包，再依次拿次价值物品放入背包，直到背包中不能放入物品为止时就结束放置，这时候放入背包中的所有物品的价值和应该就是我们所求的最大价值；正好杭电OJ上有这样的题目：HDU 2602，我们使用刚才所说的思路去解决这个问题：

最后OJ判断代码的提交结果为【Wrong Answer】说明有一些数据没有通过评测：所提交的代码为：贪心代码；杭OJ上并没有给出评测数据，但读者可以考虑以下数据：当背包容量V为2时,第一件物品：体积=1，价值=2、第二件物品：体积=1，价值=2、第三件物品：体积=2，价值=3；采用上述方案得到的最大价值为3，但实际上我们可以得到的最大价值为4(放入第一件和第二件物品)；这时候我们可能会想到既然从价值最大物品开始放入背包不行，那就从重量最轻或者单位价值最大的物品开始放起，但得到的结果都是错误的，读者可自行举反例验算数据；

我们所采用的上述解题方法称之为为贪心算法，在贪心算法中，我们总是做出当时看来最佳的选择，也就是说，它总是做出局部最优的选择，寄希望这样的选择能导致全局最优解；通常算法是自顶向下的，进行一次又一次的选择，将给定问题实例变得更小【摘自算法导论】使用贪心策略解决01背包无效是因为当我们考虑是否把一个物品装入背包时，必须比较包含此物品的子问题的解和不包含此物品的子问题的解两种情况，然后才能够做出选择，这就是问题所在；

既然贪心无法正确解题，那我们考虑使用枚举来解决这道问题；每个物品都有拿或者不拿两种状态，如果有n个物品，那么选物品的方案就为2n,然后挑选出最大价值的方案即可；所用的题解代码为：枚举代码 ，可以看到OJ给我们的反馈结果为【超时】；因为枚举子集时间复杂度过大，比如n为 1000时，这个子集数量2n就大得不可衡量了；

我们尝试了上述两种方法后都无法满足我们的解题要求，但不代表上述讨论是无意义的，从上述讨论中我们知道每个物品有放或者不放两种状态，我们可以用子问题来定义状态：用DP[i] [v]来表示前i件物品放入一个容量为v的背包的最大价值；当我们考虑选择放第i件物品时，这时候得到的最大价值为：DP[i-1] [v- Ci] +Wi 【表示前i-1件物品放入容量为v-Ci的背包得到的最大价值加上第i件物品的价值】；当我们考虑不放第i件物品时，这时候得到的最大价值为DP[i-1] [v]【表示前i-1件物品放入容量为v的背包得到的最大价值】；这时候我们就可以从这两种状态中选择一个最大的价值状态，至此我们就可以得到动态规划中最重要的状态转移方程：
DP[i] [v] = max{DP[i-1] [v]，DP[i-1] [v- Ci] +Wi}
伪代码为：

for i←1 to N for v←Ci to V DP[i][v] = max{DP[i-1][v]，DP[i-1][v-Ci]+Wi}

所用解题代码为：DP二维，可以看到OJ对这次提交为通过；

同时我们也可以得到对称状态的状态转移方程：
DP[i] [v] = max{DP[i+1] [v],DP[i+1] [v-Ci]+Wi}
这里对称状态证明过程与代码实现留给读者自行验证；
凡事都讲求尽善尽美，在实现了正确的解答方法后，我们是否可以考虑对我们代码进行优化呢？

对代码进行优化最基本的两个考虑角度就是：时间复杂度与空间复杂度，之前代码时间复杂度为和空间复杂度都为O(VN)；其中时间复杂度涉及对物品数量和背包空间的遍历，两个for循环无法进行简化了，但是空间复杂度却可以降到O(V)；

我们之前使用了二维数组保留中间生成数据(DP[1~i] [ 1~V])，我们现在可以考虑使用一维滚动数组不断的覆盖中间数据只保留最终数据即可；从之前状态转移方程我们可以知道前i件物品放入背包的最大价值只与前i-1件物品的最大价值以及Wi和Ci有关，与前i-2件物品无关(因为这时候i-2件物品的最大价值已经被计算过了)；这时候我们就可以考虑只使用一个一维数组DP[v]保留最终数据而省去中间数据了：

DP[v] = max{DP[v],DP[v-Ci]+Wi}

依照上述状态转移方程写出来的伪代码为：

for i←1 to Nfor v←V to CiDP[v] = max{DP[v]，DP[v-Ci]+Wi}

注意上面伪代码中第二层for循环为逆序，我们在二维数组版本中，在执行第i次循环之前，背包容量为0～V保存的是前i-1次循环的结果，即为DP[1~i-1] [0~V]；而第i次循环的结果只与第i-1次循环结果有关，所以我们推一维数组DP[v]状态时就要求我们DP[v-Ci]保存的是对应使用二维数组时DP[i-1] [v-Ci]的值，如果改成正序就变成DP[i] [v]是由DP[i] [v-Ci]推导而来，那么就与之前二维数组的状态转移方程不符了；

所用的解题代码为：DP一维，这次的提交不仅正确，对于内存消耗从之前二维的5348K降到了1368K；

现在让我们看下一个问题：

有 N 种物品和一个容量为 V 的背包，每种物品都有无限件可用。放入第 i 种物品 的体积是 Ci，价值是
Wi。求解：将哪些物品装入背包，可使这些物品的耗费的费用总

和不超过背包容量，且价值总和最大。
这个与上一个问题不同之处在于物品变成了无限件可以使用，只改变了这一个条件，其他条件都相同，这称之为完全背包；我们顺着之前的思路解题，现在物品无限那么背包最多放第i件物品的数量为k件其中{0<=k<=V/Ci};所以我们根据之前的状态转移方程可以得到：

我们就可以得到一个状态转移方程：

DP[i] [v] = max{DP[i-1] [j],DP[i-1] [v-k × Ci ] + k × Wi}

这跟之前的二维版本的01背包空间复杂度一样均为O(VN),但是时间复杂度却变了，因为计算状态DP[i] [v]所需要的时间为O(V/Ci),所以我们可以近似认为时间复杂度为:
O(VN$\sum$(V/C_i))

上交OJ上也对应有一道练习题目：1013，我们使用上述状态转移方程编写 代码 提交后的结果为【超过时间限制】，这是因为多了一层for循环去遍历物品数复杂度变高，如果N和V数字过大也会造成【超过内存限制】的错误；

所以我们要想办法去掉转移方程中的数字k，方法是对于第i中物品最多选【V/Ci】件，我们就可以把第i件物品看成【V/Ci】件体积为Ci,价值为Wi的物品，然后就可以把01背包解题代码套用在这里了，具体代码请读者自己思考编写；

其实我们我们还有一些优化的小细节可以进行，考虑这样一种情况：如果有两件物品i和j，且Ci ≤Cj&&Wi≥Wj，那我们就可以将物品j直接丢掉，因为将体积大价值小的物品A换成体积小价值大B放进显然是正确的；

把时间复杂度从三重循环降低到二重循环之后，我们思考像之前解01一样用一维数组去优化空间复杂度，状态转移方程如下：

DP[v] = max{DP[v],DP[v-Ci]+Wi}

对应解题核心代码为：

for(int i=1;i<=n;i++){	    	 for(int j=C[i];j<=V;j++){   DP[j]=max(DP[j],DP[j-C[i]]+W[i]); }	        				 }

注意在内层物品容量for循环变成了正序，这是因为在【01】背包中，为了防止把扫到上一个物品的状态用扫到当前物品的状态更新掉，我们内层循环倒过来更新；但是反过来会发生什么呢？反过来的话，当我们更新DP[j]的时候，会从DP[j−Ci]更新过来，但此时DP[j−Ci]或许已经包括了当前这个物品，那么DP[j]再被此状态更新的话，实际上就相当于包括了两个物品i，这也是我们希望的，因为完全背包不限制每种物品数量；

现在我们来看最后一个问题,所对应的题目连接：HDU2191

有 N 种物品和一个容量为 V 的背包。第 i 种物品最多有 Mi 件可用，每件耗费的 空间是 Ci，价值是
Wi。求解将哪些物品装入背包可使这些物品的耗费的空间总和不超 过背包容量，且价值总和最大。

这与上面完全背包区别是物品的数量是有限的，这称为多重背包问题，我们既可以转化为Mi件i种物品的01背包问题，也可以套用上面完全背包的状态转移方程：

DP[i] [v] = max{DP[i-1] [v-k×Ci]+Wi} 其中0≤k≤Mi

对应的使用一维数组的状态转移方程以及解题代码请读者自己编写；
我们继续往优化的思考，方法是把第i种物品换乘若干件01背包中的物品，其中每件物品有一个系数，这件物品的体积和价值均是原来的体积和价值乘以这个系数，而这个系数分别为，，,…-1,Mi-+1且k是满足：Mi-+1>0的最大整数；我们举一个例子来说明：有一件物品M，体积为3，价值为3，数量为7；把这个件物品M（数量7）看作为物品①：体积=×3，重量=×3，物品②：体积=重量=×3,重量=×3，物品③：体积= × 3，重量=×3；分成的这几件物品的系数和为Mi，表明不可能取多于Mi件的第i种物品，而且这些系数可以组合成任意小于等于Mi的数"num"，这个数"num"就是取第i种物品的策略；这是一种二进制优化思想，如111这个二进制数表示为7，第一个1表示4，第二个1表示2，第三个1表示1，那么由这三个1就可以组合成0~7的所有数字；这样就原来数字7分成了三组来表示，减小了复杂度；解题代码为：二进制优化

至此三种基本的背包问题都讲完了，最后我想引用算法导论来总结一下以上讨论：

什么时候应该使用动态规划求解问题呢？这样的问题应该具备两个要素：最优子结构和子问题重叠；

最优子结构：如果一个问题的最优解包含其子问题的最优解，我们就称此问题具有最优子结构性质；比如我们【01】背包，我们不仅可以求得N件物品放入背包容量为V的最大价值，同时也可以求得N件物品放入背包容量为【0~V-1】的最大价值；通常问【最大】【最小】的问题，一般都是满足最优子结构的;

重叠子问题：适用于动态规划求解最优化问题的第二个性质是子问题空间必须足够“小”，即问题的递归算法会反复地求解相同的子问题，而不是一直生成新的子问题；如背包问题求第i次循环结果时会从第i-1循环结果推导而来，也就是我们的状态转移方程；