背包問題基本解法 —— 《背包九講》筆記
相對于轉載文章，我更喜歡寫上一篇筆記，開篇給出原文連結。這樣，能有些自己的東西，總結一番，對知識的了解能加深一層；别人看來，也更有價值。
今天做USACO題目時，一道題不會，網上查到解法是01背包，于是重新看了《背包九講》。相比第一次看，了解深的多，可見我還是在進步的，隻要我沒停下腳步。如果大家想看原文，那麼隻需要百度“背包九講”就好了，百度文庫中的“背包九講 2.0”是正版，作者是崔添翼前輩，網上好像稱他為dd大牛。這篇文章可以說是“背包問題”的權威了，如果我了解無誤的話，背包問題的整套解法就是這篇文章總結出來的。在此，感謝崔添翼前輩的無私奉獻！
本篇筆記，暫時隻對01背包、完全背包問題基本解法做出記錄，今後如果用到更多，或許會回來更新。
------------------------------------------------------------------------------------------------------------------------------------------------
背包問題模型：容量為V的背包，有N件物品，編号為i的物品，所占容量為Ci，所創造價值為Wi。
01背包問題：每件物品隻有一件，可以選擇放或不放（即取0件或1件，故名01）。
完全背包問題：每件物品有無窮件，隻要裝得下放多少都行（物品所取件數，所有值都可能取到，故名完全）。
背包問題設問：
1、最多能創造多少價值？
2、背包放滿時，最多（最少）能創造多少價值？
3、背包放慢時，總共有多少種方案？
……
這就是最基礎的背包問題了，下面一一講解。
------------------------------------------------------------------------------------------------------------------------------------------------
我們首先以01背包+問題1為例。
對于背包問題，我們的基本思路是這樣的：我們一件一件去放物品，從第1件開始直到第N件。設d[i][v]為放完第i件物品時，所占容量為v的情況下最大價值是多少。
由于我們的問題1并不要求放滿背包，那麼顯然有邊界條件d[0][0~N]=0，這表示我們一件物品不放的時候，可以認為已經占了任意容量，創造的最大價值為0。
而後，我們開始一件一件放物品，c++代碼如下：
for(int i=1;i<=N;++i)
for(int v=Ci;v<=V;++v) d[v][i]=max(d[v][i-1],d[v-Ci][i-1]+Wi); 應該很容易了解，d[v][i]隻可以由兩種情況更新，一種是d[v][i-1]，這表示第i件物品不放入背包（或者說放入0件）；一種是d[v-Ci][i-1]+Wi，這表示第i件物品放入背包。我們用這兩種情況的最大值去更新d[v][i]，那麼便考慮了所有情況，進而得到了d[v][i]得到了滿足定義的值。
這便是動态規劃的思路了，很容易了解，也很好寫。那麼我們來分析一下它的複雜度：時間複雜度O(NV)，空間複雜度O(NV)。
下面我們來考慮優化。這種算法是考慮了所有情況，進而保證了正确性，是以時間複雜度上基本是無法優化的；而空間上，可以看到我們是層層遞推上去的，求第i件物品的d[0~V][i]時，我們隻需要用到d[0~V][i-1]而已，是以我們至少可以把空間縮減到兩層，也就是O(2V)。而實際上，本題是可以讓空間為一層的，即O(V)。
這時，我們的初始化代碼是：
for(int v=0;v<=V;++v) d[v]=0; 而遞推代碼則如下：
for(int i=1;i<=N;++i)
for(int v=V;v>=Ci;--v) d[v]=max(d[v],d[v-Ci]+Wi); 其實并不難了解，我們把内層循環的順序颠倒了。這樣一來，很容易發現，我們内層循環至v時，d[v+1~V]實際上都是d[v+1~V][i]，而d[0~v]則是d[0~v][i-1]。是以，黨我們執行d[v]=max(d[v],d[v-Ci]+Wi)時，它實際上就相當于d[v][i]=max(d[v][i-1],d[v-Ci][i-1]+Wi)，因為執行完這句，d[v]就相當于是d[v][i]了。
如果上面的話你了解了，那麼你也就明白了01背包問題的解法，時間O(NV)空間O(V)的解法。
那麼我們讨論下01背包+問題2：
問題2很容易，我們要把背包放滿，那麼隻需要修改一下初始化代碼：
d[0]=0;
for(int v=1;v<=V;++v) d[v]=-∞; 很好了解，一件物品不放時，隻有d[0]有意義，其餘容量都不可達到。是以，我們設為-∞，保證後面不會被max選到。而後面，隻需要使用同樣的遞推代碼，意義完全不變。這算法正确性太顯然，我就不說明了。
接下來，我們來讨論完全背包問題：
完全背包中，每件物品可以放無窮件。如果我們考慮空間為O(NV)的算法，那麼會相對複雜一點，這裡不予讨論；而實際上，我們也隻需要O(V)的空間，代碼如下：
for(int i=1;i<=N;++i)
for(int v=Ci;v<=V;++v) d[v]=max(d[v],d[v-Ci]+Wi); 很簡單，隻需要把内層循環恢複正序即可。我這裡不加解釋，相信大家簡單想想便可以了解。
而對于問題1和問題2，和01背包一樣，相對應修改初始化部分即可，代碼完全一樣。
那麼，問題3呢？
這個問題很容易，我也不打算給出代碼。有興趣的讀者可以自己想想，我在USACO上所做那道題便是這種類型，想不出來的同學可以參考一下，這是博文連結。
------------------------------------------------------------------------------------------------------------------------------------------------
至此，本篇對背包問題的基礎内容講解完畢。如果大家仍有興趣了解，不妨去看看《背包九講》原文。