(01)背包问题

(01)背包问题

之前讨论过该问题的一种分治算法，这里讨论一种更优的DP(动态规划)算法，其沿用之前的子问题划分思路，依赖数值的递推关系。先定义函数\(F(k,V)\)为“体积\(V\)的背包与物品前\(k+1\)项子序列\([t_0…t_k]\)能取到的最大总价值”。根据在分治法的讨论，可得\(F\)的递推式\(F(k,V) = max\{ F(k-1,V-A_k)+B_k, F(k-1,V) \} \)，该式也称为状态转移方程。需要注意其边界情况，\(V-A_k<0\)时说明物品本身的体积就超过背包容积，此时\(F(k,V)=F(k-1,V)\)。另一个边界情况是序号取-1时，显然有\(F(-1,V)=0\)。此时等于找到了最大总价值的递推关系，而不是解本身的递推关系。

然后是求\(F(k,V)\)，这里不用分治法“自顶向下递归”的方式，而是用“自底向上迭代”的方式。先初始化二维序列\(F[x][y]\)，然后从\(F[0][0]\)开始计算出每个下标对应的值，直到得出\(F[k][V]\)本身。这是DP中常用的计算方式，其相比函数递归，能避免对同一输入的多次计算，其缺点是需要建立维护数组，也会计算一部分之后用不上的值。

最后是用\(F\)求出1个解，比如解出\(F(k,V)=F(k-1,V)=F(k-2,V-A_{k-1})+B_{k-1}=…\)，就能得序列“\(t_k\)不放,\(t_{k-1}\)放,…”。同样在遇到\(V-A_k<0\)的边界情况时，直接认为\(t_k\)物品不放。类似于从\(F\)中找到1个“路径”。这种利用F得到具体解的方法的正确性比较容易证明，这里不讨论这一点。

容易观察出这个算法的“计算量”是\(O(kV)\)，但其时间复杂度并不是\(O(kV)\)，因为\(k\)确实反映了问题的规模，但\(V\)并不反映“规模”，其只是一个数值。但是\(V\)却与时间复杂度相关，这种“假”多项式时间的算法一般叫伪多项式时间算法。

下面是一种程序具体实现，为了强调动态规划策略本身，故意把程序分成两段，\(dp\)用于求\(F\)，\(zeroOne\)用于从\(F\)中还原出一个具体的解，虽然很容易在求\(F\)的过程中顺便构造出一个具体的解。