背包

背包问题需要把状态想清楚，其实，各种问题的状态都需要想清楚。
最基本地状态是 f [ i ][ v ]表示 前 i 件物品装在 v 体积的包里所需要最多的价值。
（第 i 件物品有没有存我们并不知道）
f [ i ][ j ] = max { f [ i - 1 ][ j ], f [ i-1 ][ j - c[ i ] ] + w[ i ] } 。
然后参考 二维 的 状态转移图 就会发现，在空间复杂度上可以进行更新。
f [ i ] = max { f[ i ], f [ i - c[ i ] ] + w[ i ] } 。
如果不同价值的物品恰好只有一件， 具体参照 背包九讲 。