参考博客：http://blog.csdn.net/guard_mine/article/details/40184529
01背包是基础的背包问题，给定N个物品和容量V的背包，给出每个物品的费用ci和物品的价值wi,求不超过背包容量V的前提下获得的最大物品价值。
状态转移方程：f(i, v) = max(f(i-1, v), f(i-1, v-c[i])+w[i])
1 for (int i = 1; i <= N; ++ i)
2 {
3 for (int j = c[i]; j <= V; ++ j)
4 {
5 dp[i][j] = max(dp[i-1][j], dp[i-1][j-c[i]]+w[i]);
6 }
7 }
时间复杂度O(NV), 空间复杂度O(NV), 可以将空间复杂度降到O(V):
1 for (int i = 1; i <= N; ++ i)
2 {
3 for (int j = V; j >= c[i]; ++ j)
4 {
5 dp[j] = max(dp[j], dp[j-c[i]]+w[i]);
6 }
7 }
为什么改变体积的循环顺序就可将二维的dp数组变成一维呢？？？
dp(i, v) 是由dp(i-1, v) 和 dp(i-1, v-ci)两个状态转移过来的，所以计算状态f(i, v)的时候必须保证前两个状态已经计算出来。当dp数组转换为一维的时候，无法保存（i-1）的状态，如果体积按照从小到大的顺序计算， （i-1)的各种状态会被 i 的状态“覆盖”， 所以只要按照从大到小的体积顺序计算就可以保留（i-1)层的状态了。