背包九講doc版

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

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

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

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

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

6、[v]時(shí)（也即在第i次主循環(huán)中推f[v]時(shí)）能夠得到f[i1][v]和f[i1][vc[i]]的值呢？事實(shí)上，這要求在每次主循環(huán)中我們以v=V..0的順序推f[v]，這樣才能保證推f[v]時(shí)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]]一句恰就相當(dāng)于我們的轉(zhuǎn)移方程f[i][v]=maxf[i1

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

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

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

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

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