0-1背包

存在容量为 $V$ 的背包， $N$ 件体积分别为 $c_1, c_2, .. ,c_N$ ，重量为 $w_1, w_2, ... ,w_N$ 的物品。求解将哪些物品放入背包使得体积不超出 $V$ 的情况下重量最重，物品不得重复使用。

解法

对于 0-1背包问题，每一件物品只存在放或者不放这两种情况。例如，讨论是否放入最后一个物品存在两种情况:

不放入该物品，那么结果转化为 容量为 $V$ ，物品为前 $N-1$ 子问题的结果
放入该物品，那么结果转化为容量为 $V-c_N$ ，物品为前 $N-1$ 子问题的结果 + $w_N$

利用函数 $f(i, v)$ 表示前 $i$ 件物品放入容量为 $v$ 的背包中所能获得的最大重量，那么我们的问题结果为:

$f(N,V )=max(f(N-1, V ),\ \ \ f(N-1, V-c_N) + w_N)$

等式右边两个函数分别表示情况1, 2所对应的结果，取其中较大的则为问题最终的结果。同样，这个函数可以扩展到一般情况，即把 $N$ 换成 $i$ :

$f(i, v) = max(f(i-1, v ),\ \ \ f(i -1, V-c_i) + w_i)$

这里举一个实际的例子来说明这个算法，对于 $C=[2,2,6,5,4]$ , $W=[6,3,5,4,6]$ , $V=10$ 来说，我们实际上要求 $f(4, 10)$ .根据上式:

$f(4, 10) = max(f(3, 10), f(3, 10-4) + 6)=max(f(3,10),f(3,6)+6)$

而:

$f(3, 10)=max(f(2, 10), f(2, 5) + 4)$
$f(3, 6)=max(f(2, 6), f(2, 1) + 4)$

可以看出，这是一个递归的问题，最终当 $f(0, i)$ 即可退出递归，而:

$f(0, i) = w_0 \ \ if \ \ (i) >= c_0 \ \ else \ \ 0$

同过一系列的递归，则可以求得最终的值。用python来描述即为:

def one_zero_r(C, W, V):
    def helper(i, v, dir):
        if not i:
            return W[0] if v >= C[0] else 0
        if v >= C[i]:
            return max(helper(i - 1, v - C[i]) + W[i], helper(i - 1, v))
        else:
            return helper(i - 1, v)
    return helper(len(C) - 1, V)

同时，还可以画出求解的状态图:

状态图