0-1背包问题

0-1背包问题描述：
有n个物品，标示为1、2、3....n，重量分别为w1、w2、....wn，价值分别为v1、v2、....vn，
有一背包，能承受的最大重量为C，问用该背包装哪些物品可以获得最大价值？

动态规划分析：
只需找出optimal substructure 就可以了。
设m(i,j)表示可选物品为1、2、3、....i，背包剩余容量为j时的最优解。
我们最终求的结果是m(n,C)，n为物品件数，C为背包总容量。

递推是为：
m(i,j)=
        max( m(i-1,j), m(i-1,j-wi)+vi )   j>=wi;
        m(i-1,j)                          j
初始化条件为：
m(1,j)=
        v1         j>=w1;
        0          0<=j

伪代码大概描述为：
for j in 0 to C
    if j>=w1
        m(1,j)=v1;
    else
        m(1,j)=0;
for i in 2 to n
for j in 0 to C
if j    m(i,j)=m(i-1,j);
else
    m(i,j)=max(m(i-1,j),m(i-1,j-wi)+vi);

print m(n,C)

以上代码只是求出了背包可以装的最大价值，但没有具体给出装哪些物品来获取最大价值，
在每一步选择的时候增加标志即可记录所选择的物品。