(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\)的过程中顺便构造出一个具体的解。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 | def dp(A, B, V): f = [[0 for j in range(V + 1)] for i in A] for i in range(len(A)): for j in range(V + 1): if i == 0: if j - A[i] < 0: f[i][j] = 0 else: f[i][j] = B[i] else: if j - A[i] < 0: f[i][j] = f[i - 1][j] else: f[i][j] = max(f[i - 1][j], f[i - 1][j - A[i]] + B[i]) return f def zeroOne(A, B, V): result = [0 for i in A] f = dp(A, B, V) i, j = len(A) - 1, V while True: if i == 0: result[i] = 0 if j - A[i] < 0 else 1 break else: if j - A[i] < 0: result[i] = 0 i -= 1 else: if f[i][j] == f[i - 1][j]: result[i] = 0 i -= 1 else: result[i] = 1 j -= A[i] i -= 1 return result |