Discrete Optimization (Coursera) wee2-2 动态规划求解背包问题

Dynamic Programming

动态规划（DP）初探

DP的思想是：将一个大问题的求解转化为一些更小问题的求解。我们假设对于一个更小的问题已经有了最优解答，在此基础上我们build up the bigger problems。这种分而治之的思想非常像递归，但是递归通常会招致不必要的算力消耗，因此 DP使用了 bottom up的方法，有效地节省了算力。

DP guarantees to find the best solution

(Basic principles: 1. Divide and Conquer; 2. Bottom Up computation)

当我们谈起DP，其实可以预设一个很大的 table，我们要做的事情其实就是填表。

Take knapsack as an example

这里还是以 knapsack problem为例，假设问题如下：

给定一个 Capacity为 k的 knapsack，给定一组物品并用 1,2,…,n标记，物品i的价值为$v_i$vi​，重量为 $w_i$wi​. $ I = {1,2,…,n }$.

希望找到一个最优选择，使得在 knapsack可以装下的情况下，拿走物品的总价值最大。

我们可以建模如下：
$\max \sum_{i\in I}v_i x_i\\ s.t. \sum_{i\in I}v_i x_i \le k \\ x_i \in \{0,1\}, i\in I$maxi∈I∑​vi​xi​s.t.i∈I∑​vi​xi​≤kxi​∈{0,1},i∈I
现在假设 $O(p,m)$O(p,m)是当在 knapsack的 capacity为p，物品下标为 1,2,…,m的时候的最优选择下的总价值。这些就是子问题。

我们所关心的是 $O(k,n)$O(k,n)的值，并找出这个最大值对应的最优选择。

如果我们假设 $O(p,j)$O(p,j) 已经已知，对于$p\le k, j \le m$p≤k,j≤m，那么，如果我们在选择 $O(p, m+1)$O(p,m+1)的时候，无非就是选择物品m+1或者不选择它。

如果选择了物品m+1，那么我们还剩下 $p-w_{m+1}$p−wm+1​ 的背包容量（如果$p-w_{m+1}$p−wm+1​ 是一个负数，显然就不装物品m+1了），以及物品 1,…,m待选择，这种情况下我们最好的选择方法就是按照 $O(p-w_{i+1}, m)$O(p−wi+1​,m)来选择。因此，在选择物品m+1的情况下，能获得的最大价值是 $v_{m+1} + O(p-w_{i+1}, m)$vm+1​+O(p−wi+1​,m)

如果不选择物品 m+1，那么我们就有一个容量p的背包和物品 1,…,m待选择。因此，在不选择物品 m+1的情况下，能获得的最大价值的 $O(p, m)$O(p,m)

因此，我们选择 $O(p,m+1) := \max (v_{m+1} + O(p-w_{i+1}, m),O(p, m) )$O(p,m+1):=max(vm+1​+O(p−wi+1​,m),O(p,m))，这就完成了从更简单的subproblem到bigger problems的构建。

至于base case，也就是 $O(p, 1), 1\le p \le k$O(p,1),1≤p≤k，这个的填充方法不过是：能装下就装并填上 $v_1$v1​，不能装就填0.

Simple as that。所做的不过是 fill in a k times n table.

Recover the best choice

当然，还有一个问题就是：如何从这个 中 recover最优的选择？这个同样是不难的。首先，我们注意到，如果在选择 $O(p, m+1)$O(p,m+1)的时候，我们不选择物品m+1，那么 $O(p,m+1) = O(p,m)$O(p,m+1)=O(p,m)。因此，只需要检查这个是否相等，我们就可以判断是否最优选择包含了这个物品。

嗯… Something like this:

如果 O(7,4) > O(7,3)，那么说明物品4是被选择的。然后发现 O(2,3) = O(2,2)，这说明没有选择物品3；然后是O(2,2) = O(2,1)，说明物品2也没有被选择。最后发现 O(2,1) > 0，因此物品1是被选择了的。综上所述，最优选择是 (1,0,0,1)

The Complexity is pseudo-polynomial

Fill in the table 的算法复杂度是 O(kn)。如果我们只关注n，那么这个算法是 linear in n。但是，因为我们仅仅需要 $\log k$logk bits 来 represent k，这个复杂度实际上是 $O(2^{\log k} n)$O(2logkn)，因此是 exponenetial in terms of the input size

（这个我也有点迷糊… 看了挺多回答也半蒙半懂的。我现在的状态就像是在问“为什么鸽子这么大”… ）

所以当 k is small, DP is quite efficient for knapsack problems

但是如果 k很大，我们可能就得另觅他法了。

对于DP的介绍就先到这里~