背包九講doc版

1、背包問題九講背包問題九講v1.0v1.0目錄第一講01背包問題第二講完全背包問題第三講多重背包問題第四講混合三種背包問題第五講二維費用的背包問題第六講分組的背包問題第七講有依賴的背包問題第八講泛化物品第九講背包問題問法的變化附：USACO中的背包問題前言前言本篇文章是我(dd_engi)正在進行中的一個雄心勃勃的寫作計劃的一部分，這個計劃的內容是寫作一份較為完善的NOIP難度的動態(tài)規(guī)劃總結，名為《解動態(tài)規(guī)劃題的基本思考方式》。現(xiàn)在你看到

2、的是這個寫作計劃最先發(fā)布的一部分。背包問題是一個經(jīng)典的動態(tài)規(guī)劃模型。它既簡單形象容易理解，又在某種程度上能夠揭示動態(tài)規(guī)劃的本質，故不少教材都把它作為動態(tài)規(guī)劃部分的第一道例題，我也將它放在我的寫作計劃的第一部分。讀本文最重要的是思考。因為我的語言和寫作方式向來不以易于理解為長，思路也偶有跳躍的地方，后面更有需要大量思考才能理解的比較抽象的內容。更重要的是：不大量思考，絕對不可能學好動態(tài)規(guī)劃這一信息學奧賽中最精致的部分。你現(xiàn)在看到的是本文的

3、1.0正式版。我會長期維護這份文本，把大家的意見和建議融入其中，也會不斷加入我在OI學習以及將來可能的ACMICPC的征程中得到的新的心得。但目前本文還沒有一個固定的發(fā)布頁面，想了解本文是否有更新版本發(fā)布，可以在OIBH論壇中以“背包問題九講”為關鍵字搜索貼子，每次比較重大的版本更新都會在這里發(fā)貼公布。目錄目錄第一講第一講0101背包問題這是最基本的背包問題，每個物品最多只能放一次。第二講第二講完全背包問題完全背包問題第二個基本的背包問

4、題模型，每種物品可以放無限多次。第三講第三講多重背包問題多重背包問題每種物品有一個固定的次數(shù)上限。第四講第四講混合三種背包問題混合三種背包問題將前面三種簡單的問題疊加成較復雜的問題。第五講第五講二維費用的背包問題二維費用的背包問題一個簡單的常見擴展。第六講第六講分組的背包分組的背包問題一種題目類型，也是一個有用的模型。后兩節(jié)的基礎。第七講第七講有依賴的背包問題有依賴的背包問題另一種給物品的選取加上限制的方法。第八講第八講泛化物品泛化物品

5、以上方法的時間和空間復雜度均為O(NV)，其中時間復雜度基本已經(jīng)不能再優(yōu)化了，但空間復雜度卻可以優(yōu)化到O(V)。先考慮上面講的基本思路如何實現(xiàn)，肯定是有一個主循環(huán)i=1..N，每次算出來二維數(shù)組f[i][0..V]的所有值。那么，如果只用一個數(shù)組f[0..V]，能不能保證第i次循環(huán)結束后f[v]中表示的就是我們定義的狀態(tài)f[i][v]呢？f[i][v]是由f[i1][v]和f[i1][vc[i]]兩個子問題遞推而來，能否保證在推f[i]

6、[v]時（也即在第i次主循環(huán)中推f[v]時）能夠得到f[i1][v]和f[i1][vc[i]]的值呢？事實上，這要求在每次主循環(huán)中我們以v=V..0的順序推f[v]，這樣才能保證推f[v]時f[vc[i]]保存的是狀態(tài)f[i1][vc[i]]的值。偽代碼如下：fi=1..Nfv=V..0f[v]=maxf[v]f[vc[i]]w[i]其中的f[v]=maxf[v]f[vc[i]]一句恰就相當于我們的轉移方程f[i][v]=maxf[i1

7、][v]f[i1][vc[i]]，因為現(xiàn)在的f[vc[i]]就相當于原來的f[i1][vc[i]]。如果將v的循環(huán)順序從上面的逆序改成順序的話，那么則成了f[i][v]由f[i][vc[i]]推知，與本題意不符，但它卻是另一個重要的背包問題P02最簡捷的解決方案，故學習只用一維數(shù)組解01背包問題是十分必要的。事實上，使用一維數(shù)組解01背包的程序在后面會被多次用到，所以這里抽象出一個處理一件01背包中的物品過程，以后的代碼中直接調用不加說

8、明。過程ZeroOnePack，表示處理一件01背包中的物品，兩個參數(shù)cost、weight分別表明這件物品的費用和價值。procedureZeroOnePack(costweight)fv=V..costf[v]=maxf[v]f[vcost]weight注意這個過程里的處理與前面給出的偽代碼有所不同。前面的示例程序寫成v=V..0是為了在程序中體現(xiàn)每個狀態(tài)都按照方程求解了，避免不必要的思維復雜度。而這里既然已經(jīng)抽象成看作黑箱的過程了

9、，就可以加入優(yōu)化。費用為cost的物品不會影響狀態(tài)f[0..cost1]，這是顯然的。有了這個過程以后，01背包問題的偽代碼就可以這樣寫：fi=1..NZeroOnePack(c[i]w[i])初始化的細節(jié)問題初始化的細節(jié)問題我們看到的求最優(yōu)解的背包問題題目中，事實上有兩種不太相同的問法。有的題目要求“恰好裝滿背包”時的最優(yōu)解，有的題目則并沒有要求必須把背包裝滿。一種區(qū)別這兩種問法的實現(xiàn)方法是在初始化的時候有所不同。如果是第一種問法，要

10、求恰好裝滿背包，那么在初始化時除了f[0]為0其它f[1..V]均設為∞，這樣就可以保證最終得到的f[N]是一種恰好裝滿背包的最優(yōu)解。如果并沒有要求必須把背包裝滿，而是只希望價格盡量大，初始化時應該將f[0..V]全部設為0。為什么呢？可以這樣理解：初始化的f數(shù)組事實上就是在沒有任何物品可以放入背包時的合法狀態(tài)。如果要求背包恰好裝滿，那么此時只有容量為0的背包可能被價值為0的nothing“恰好裝滿”，其它容量的背包均沒有合法的解，屬于

11、未定義的狀態(tài)，它們的值就都應該是∞了。如果背包并非必須被裝滿，那么任何容量的背包都有一個合法解“什么都不裝”，這個解的價值為0，所以初始時狀態(tài)的值也就全部為0了。這個小技巧完全可以推廣到其它類型的背包問題，后面也就不再對進行狀態(tài)轉移之前的初始化進行講解。小結小結01背包問題是最基本的背包問題，它包含了背包問題中設計狀態(tài)、方程的最基本思想，另外，別的類型的背包問題往往也可以轉換成01背包問題求解。故一定要仔細體會上面基本思路的得出方法，狀