动态规划之背包问题【1】

背包问题是一类有关物品和背包的问题，包括01背包问题，完全背包问题，多重背包问题和二维费用背包问题等等，都可以用动态规划来解。下面主要分析背包问题中的最基础问题，01背包问题！

01背包问题
问题：有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。
状态转移方程：f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}
其中f[i][v]表示前i个物品恰好放在容量为v的背包里所能获得的最大价值。这个方程的核心就是：第i个物品放与不放的问题，可以转化为一个只牵扯前i-1件物品的问题。

• 如果放第i个物品，则转化为“前i-1个物品放入容量为v-c[i]的背包中”问题，其价值等于w[i]+f[i-1][v-c[i]]；
• 如果第i个物品不放，则转化为“前i-1个物品放入v的背包中”的问题，其价值等于f[i-1][v]；

伪代码如下：

1:  Backpack( N, v, C, W )  
2:  {  
3:    initialize 2D-array f[N.size][v]  
4:    for i=1 to N.size  
5:    {  
6:      for vv=1 to v  
7:      {  
8:        f[i][vv] = max{ f[i-1][vv], f[i-1][vv-C[i]]+W[i] };  
9:      }  
10:    }  
11:  }  

以上的方法的时间和空间复杂度都是O(VN)，但空间复杂度可以优化到O(V)。因为f[i][v]是由f[i-1][v]和f[i-1][v-c[i]]两个字问题推倒而来。只要能保证 f[i-1][v-c[i]]永远读取f[i][v]前面的数据，就能保证用一位数组也能得到正确答案，即将次循环中的v反向遍历。伪代码如下：

1:  Backpack( N, v, C, W )  
2:  {  
3:       initialize 1D-array f[v]  
4:       for i=1 to N.size  
5:       {  
6:          //     as the item i, which has C[i], will not   
7:          //     affect f[0 to C[i]-1]. If it happend,  
8:          //     the index will exceed the lower boundary.  
9:          for vv=v to C[i]  
10:         {  
11:              f[vv]=max{f[vv],f[vv-C[i]]+W[i]};  
12:         }  
13:      }  
14:  }