0-1背包问题

问题：N个物品，分别有(s体积，v价值)两个属性。一个背包，总的容量为C。 要怎么装，使得不超过C的情况下，总价值最大？

特点：每种物品仅有一件，可以选择放或不放。

状态转移：V(i,j)，表示从i个中取出来体积为j的价值。 目标：V(n,C)。

方程：

V(i,j) = 0 ,if(i ==0 || j==0)，即不装，就没有价值。
V(i,j) = V(i-1,j)，if (j<si)，体积j小于Si，装不下，那么也就是和前一个一致。
V(i,j) = max{ V(i-1,j),V(i-1,j-Si) + Vi }，如果可以装得下，那么取装与不装的最大值。

计算：使用(n+1) * (C + 1) 打表即可算出。