(01)背包问题
背包问题(Knapsack Problem)是一类著名的运筹学、应用数学的问题，其相关研究可追溯至1897年。其中最简单的背包问题是(01)背包问题。其可描述为“给定一个物品序列\([t_0,t_1…t_n]\)，序列中任意下标\(i\)的物品都有体积\(A_i\)和价值\(B_i\)两个指标，现有容积\(V\)的背包，问放入背包哪些物品能取到最大价值”。这个问题的解不一定唯一，这里规定解的格式为和物品序列等长的序列，序列下标\(i\)的元素能取的值是0/1，表示物品序列下标\(i\)的物品不放/放入背包。
然后找问题的分治算法，这里先用一个符号\(G(k,V)\)表示“对物品序列前\(k+1\)项构成的子序列\([t_0,t_1…t_k]\)，求一个能放入体积\(V\)背包的最大价值物品组合”。然后考虑如何用规模更小的若干个\(G\)构造出\(G(k,V)\)的一个解。这里先直接给出结论，按如下2种方式得到的物品组合，总价最大的其中一个可作为\(G(k,V)\)的解：
1) \(G(k-1,V-A_k)\)的任意1个解再加上物品\(t_k\)；
2) \(G(k-1,V)\)的任意1个解；
上述结论可用反证法证明，假设按上述方式找到物品集合\(S\)但不能作为\(G(k,V)\)的解，那只能因为总价值没最大化，不可能因为其他原因。设\(S’\)是\(G(k,V)\)的一个解，若\(S’\)包含\(t_k\)，去掉\(S’\)中的\(t_k\)得到的必须是\(G(k-1,V-A_k)\)的1个解，否则\(S’\)就不是解了。同理若\(S’\)不包含\(t_k\)，\(S’\)必须是\(G(k-1,V)\)的1个解。综上说明\(S\)的总价值不小于\(S’\)，导致矛盾。
简单考虑上述解法的边界的情况。当遇到\(V<0\)时，说明物品\(t_k\)的体积直接比背包体积大了，也就是直接排除掉上述(1)作为最优解的可能。当遇到\(k=-1\)说明已经到达问题的边界，返回空序列作为解。下面是程序实现。
1 2 3 4 5 6 7 8 9 10 11 | def f(A, B, k, v): if k == 0: return [] if v - A[0] <= 0 else [0] if v - A[k] < 0: return f(A, B, k - 1, v) s1 = f(A, B, k - 1, v) s2 = f(A, B, k - 1, v - A[k]) s2.append(k) v1 = sum([B[i] for i in s1]) v2 = sum([B[i] for i in s2]) return s1 if v1 >= v2 else s2 |