動态規劃——背包問題1：01背包

背包問題是動态規劃中的一個經典題型，其實，也比較容易了解。

當你了解了背包問題的思想，凡是考到這種動态規劃，就一定會得很高的分。

背包問題主要分為三種：

01背包    完全背包    多重背包

其中，01背包是最基礎的，最簡單的，也是最重要的。

因為其他兩個背包都是由01背包演變而來的。是以，學好01背包，對接下來的學習很有幫助。

廢話不多說，我們來看01背包。

01 背包問題：給定 n 種物品和一個容量為 C 的背包，物品 i 的重量是 wi，其價值為 vi 。

問：應該如何選擇裝入背包的物品，使得裝入背包中的物品的總價值最大？

第一眼看上去，我們會想到貪心（背包問題還不會QAQ）。

用貪心算法來看，流程是這樣的：

1.排序，按價值從大到小排序

2.選價值盡可能大的物品放入。

但是，貪心做這題是錯的。

讓我們舉個反例：

n=5,C=10
             重量          價值
第一個物品：    10            5
第二個物品：    1             4
第三個物品：    2             3
第四個物品：    3             2
第五個物品：    4             1      

用貪心一算。答案是5，但正解是用最後4個，價值總和是10.

那将重量排序呢？

其實也不行。

稍微一想就想到了反例。

我們需要借助别的算法。

貪心法用的是一層循環，而資料不保證在一層循環中得解，于是，我們要采用二層循環。

這也是背包的思想之一。

來看背包算法：

1.用二維數組dp [ i ] [ j ]，表示在面對第 i 件物品，且背包容量為  j 時所能獲得的最大價值 

比如說上面的那個反例：

dp [ 1 ] [ 3 ] = 4 + 3 = 7.

2.01背包之是以叫“01”，就是一個物品隻能拿一次，或者不拿。

那我們就分别來讨論拿還是不拿。

（1）j < w[i] 的情況，這時候背包容量不足以放下第 i 件物品，隻能選擇不拿

dp [ i ] [ j ] = dp [ i - 1 ] [ j ]；

（2）j>=w[i] 的情況，這時背包容量可以放下第 i 件物品，我們就要考慮拿這件物品是否能擷取更大的價值。

~如果拿取，dp [ i ] [ j ] = dp [ i - 1 ] [ j - w [ i ] ] + v [ i ]。 這裡的dp [ i - 1 ] [ j - w [ i ] ]指的就是考慮了i-1件物品，背包容量為 j-w[i] 時的最大價值，也是相當于為第i件物品騰出了w[i]的空間。

~如果不拿，dp [ i ] [ j ] = dp [ i-1 ] [ j ]

到底拿不拿呢？要看拿與不拿那個結果更大了。

看，這用到了動态規劃的思想：在求值時會用到之前狀态的結果。

我們就可以得出狀态轉移方程了。

1 if(j>=w[i])
2     dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
3 else 
4     dp[i][j] = dp[i-1][j];      

 于是，完整代碼就出來了：

code：

1 int n,c,w[1001],v[1001];
 2 int dp[1001][1001];
 3 cin>>n>>c;
 4 for(int i=1;i<=n;i++)
 5     cin>>w[i]>>v[i];
 6 for(int i=1;i<=n;i++) //物品 
 7 {        
 8     for(int j=1;j<=c;j++)  //從一枚舉到C      
 9     {            
10         if(j>=w[i])                
11             dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);  //最大值            
12         else                
13             dp[i][j]=dp[i-1][j];       
14     }    
15 }
16 cout<<dp[n][c]<<endl;//n個物品，背包空間為c的dp值       

那麼，這是二維的01背包，可以看出，數組受空間限制，不能開太大，是以，我們還有一種優化01背包，隻有一維的數組

先考慮上面講的基本思路如何實作，肯定是有一個主循環i=1..N，每次算出來二維數組dp[ i ] [ 0..V ]的所有值。那麼，如果隻用一個數組dp [ 0..V ]，能不能保證第i次循環結束後dp[ v ]中表示的就是我們定義的狀态dp [ i ] [ v ]呢？dp[ i ][ v ]是由dp[ i-1 ][ v ]和dp[ i-1 ][ v-c[i] ]兩個子問題遞推而來，能否保證在推dp[ i ][ v ]時（也即在第i次主循環中推dp[ v ]時）能夠得到dp[ i-1 ][ v ]和dp[ i-1 ][ v-c[i] ]的值呢？事實上，這要求在每次主循環中我們以v=V..0的順序推dp[ v ]，這樣才能保證推dp[ v ]時dp[ v-c[i] ]儲存的是狀态dp[ i-1 ][ v-c[i] ]的值。如果将v的循環順序從上面的逆序改成順序的話，那麼則成了dp[ i ][ v ]由dp[ i ][ v-c[ i ] ]推知，與本題意不符，但它卻是完全背包最簡捷的解決方案，故學習隻用一維數組解01背包問題是十分必要的。

1 for(int i=1;i<=n;i++)
2 {
3     for(int v=c;v>=0;v--)
4     {
5         dp[v]=max(dp[v],dp[v-c[i]]+w[i]);
6     }
7 }      

這就是代碼，相比上面的簡潔了許多，既優化了空間，又減少了代碼長度。

這就是01背包問題，其實真沒啥難度，記下模闆都能過。

上面的講解應該很詳細了，大家多看幾遍，應該是可以了解的。

我們下次将講解完全背包和多重背包問題，我們下次見。