背包問題匯總.doc

部分背包 書P74（貪心，按斤計算，求平均價值）最基本的背包問題：（回溯，給重量，看能否裝滿）；P01: 01背包問題題目有N件物品和一個容量為V的背包。第i件物品的費用是ci，價值是wi。求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大?；舅悸愤@是最基礎的背包問題，特點是：每種物品僅有一件，可以選擇放或不放。用子問題定義狀態(tài)：即fiv表示前i件物品恰放入一個容量為v的背包可以獲得的最大價值。則其狀態(tài)轉移方程便是：fiv=maxfi-1v,fi-1v-ci+wi。這個方程非常重要，基本上所有跟背包相關的問題的方程都是由它衍生出來的。所以有必要將它詳細解釋一下：“將前i件物品放入容量為v的背包中”這個子問題，若只考慮第i件物品的策略（放或不放），那么就可以轉化為一個只牽扯前i-1件物品的問題。如果不放第i件物品，那么問題就轉化為“前i-1件物品放入容量為v的背包中”；如果放第i件物品，那么問題就轉化為“前i-1件物品放入剩下的容量為v-ci的背包中”，此時能獲得的最大價值就是fi-1v-ci再加上通過放入第i件物品獲得的價值wi。注意fiv有意義當且僅當存在一個前i件物品的子集，其費用總和為v。所以按照這個方程遞推完畢后，最終的答案并不一定是fNV，而是fN0.V的最大值。如果將狀態(tài)的定義中的“恰”字去掉，在轉移方程中就要再加入一項fiv-1，這樣就可以保證fNV就是最后的答案。至于為什么這樣就可以，由你自己來體會了。優(yōu)化空間復雜度以上方法的時間和空間復雜度均為O(N*V)，其中時間復雜度基本已經不能再優(yōu)化了，但空間復雜度卻可以優(yōu)化到O(V)。先考慮上面講的基本思路如何實現(xiàn)，肯定是有一個主循環(huán)i=1.N，每次算出來二維數(shù)組fi0.V的所有值。那么，如果只用一個數(shù)組f0.V，能不能保證第i次循環(huán)結束后fv中表示的就是我們定義的狀態(tài)fiv呢？fiv是由fi-1v和fi-1v-ci兩個子問題遞推而來，能否保證在推fiv時（也即在第i次主循環(huán)中推fv時）能夠得到fi-1v和fi-1v-ci的值呢？事實上，這要求在每次主循環(huán)中我們以v=V.0的順序推fv，這樣才能保證推fv時fv-ci保存的是狀態(tài)fi-1v-ci的值。偽代碼如下：for i=1.N for v=V.0 fv=maxfv,fv-ci+wi;其中的fv=maxfv,fv-ci一句恰就相當于我們的轉移方程fiv=maxfi-1v,fi-1v-ci，因為現(xiàn)在的fv-ci就相當于原來的fi-1v-ci。如果將v的循環(huán)順序從上面的逆序改成順序的話，那么則成了fiv由fiv-ci推知，與本題意不符，但它卻是另一個重要的背包問題P02最簡捷的解決方案，故學習只用一維數(shù)組解01背包問題是十分必要的?？偨Y01背包問題是最基本的背包問題，它包含了背包問題中設計狀態(tài)、方程的最基本思想，另外，別的類型的背包問題往往也可以轉換成01背包問題求解。故一定要仔細體會上面基本思路的得出方法，狀態(tài)轉移方程的意義，以及最后怎樣優(yōu)化的空間復雜度。P02: 完全背包問題題目有N種物品和一個容量為V的背包，每種物品都有無限件可用。第i種物品的費用是ci，價值是wi。求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大?；舅悸愤@個問題非常類似于01背包問題，所不同的是每種物品有無限件。也就是從每種物品的角度考慮，與它相關的策略已并非取或不取兩種，而是有取0件、取1件、取2件等很多種。如果仍然按照解01背包時的思路，令fiv表示前i種物品恰放入一個容量為v的背包的最大權值。仍然可以按照每種物品不同的策略寫出狀態(tài)轉移方程，像這樣：fiv=maxfi-1v-k*ci+k*wi|0=k*ci=v。這跟01背包問題一樣有O(N*V)個狀態(tài)需要求解，但求解每個狀態(tài)的時間則不是常數(shù)了，求解狀態(tài)fiv的時間是O(v/ci)，總的復雜度是超過O(VN)的。將01背包問題的基本思路加以改進，得到了這樣一個清晰的方法。這說明01背包問題的方程的確是很重要，可以推及其它類型的背包問題。但我們還是試圖改進這個復雜度。一個簡單有效的優(yōu)化完全背包問題有一個很簡單有效的優(yōu)化，是這樣的：若兩件物品i、j滿足ci=wj，則將物品j去掉，不用考慮。這個優(yōu)化的正確性顯然：任何情況下都可將價值小費用高得j換成物美價廉的i，得到至少不會更差的方案。對于隨機生成的數(shù)據(jù)，這個方法往往會大大減少物品的件數(shù)，從而加快速度。然而這個并不能改善最壞情況的復雜度，因為有可能特別設計的數(shù)據(jù)可以一件物品也去不掉。轉化為01背包問題求解既然01背包問題是最基本的背包問題，那么我們可以考慮把完全背包問題轉化為01背包問題來解。最簡單的想法是，考慮到第i種物品最多選V/ci件，于是可以把第i種物品轉化為V/ci件費用及價值均不變的物品，然后求解這個01背包問題。這樣完全沒有改進基本思路的時間復雜度，但這畢竟給了我們將完全背包問題轉化為01背包問題的思路：將一種物品拆成多件物品。更高效的轉化方法是：把第i種物品拆成費用為ci*2k、價值為wi*2k的若干件物品，其中k滿足ci*2kV。這是二進制的思想，因為不管最優(yōu)策略選幾件第i種物品，總可以表示成若干個2k件物品的和。這樣把每種物品拆成O(log(V/ci)件物品，是一個很大的改進。 但我們有更優(yōu)的O(VN)的算法。 * O(VN)的算法 這個算法使用一維數(shù)組，先看偽代碼： for i=1.N for v=0.V fv=maxfv,fv-ci+wi; 你會發(fā)現(xiàn)，這個偽代碼與P01的偽代碼只有v的循環(huán)次序不同而已。為什么這樣一改就可行呢？首先想想為什么P01中要按照v=V.0的逆序來循環(huán)。這是因為要保證第i次循環(huán)中的狀態(tài)fiv是由狀態(tài)fi-1v-ci遞推而來。換句話說，這正是為了保證每件物品只選一次，保證在考慮“選入第i件物品”這件策略時，依據(jù)的是一個絕無已經選入第i件物品的子結果fi-1v-ci。而現(xiàn)在完全背包的特點恰是每種物品可選無限件，所以在考慮“加選一件第i種物品”這種策略時，卻正需要一個可能已選入第i種物品的子結果fiv-ci，所以就可以并且必須采用v=0.V的順序循環(huán)。這就是這個簡單的程序為何成立的道理。這個算法也可以以另外的思路得出。例如，基本思路中的狀態(tài)轉移方程可以等價地變形成這種形式：fiv=maxfi-1v,fiv-ci+wi，將這個方程用一維數(shù)組實現(xiàn)，便得到了上面的偽代碼?？偨Y完全背包問題也是一個相當基礎的背包問題，它有兩個狀態(tài)轉移方程，分別在“基本思路”以及“O(VN)的算法“的小節(jié)中給出。希望你能夠對這兩個狀態(tài)轉移方程都仔細地體會，不僅記住，也要弄明白它們是怎么得出來的，最好能夠自己想一種得到這些方程的方法。事實上，對每一道動態(tài)規(guī)劃題目都思考其方程的意義以及如何得來，是加深對動態(tài)規(guī)劃的理解、提高動態(tài)規(guī)劃功力的好方法。P03: 多重背包問題題目有N種物品和一個容量為V的背包。第i種物品最多有ni件可用，每件費用是ci，價值是wi。求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大?；舅惴ㄟ@題目和完全背包問題很類似?；镜姆匠讨恍鑼⑼耆嘲鼏栴}的方程略微一改即可，因為對于第i種物品有ni+1種策略：取0件，取1件取ni件。令fiv表示前i種物品恰放入一個容量為v的背包的最大權值，則：fiv=maxfi-1v-k*ci+k*wi|0=k0的最大整數(shù)。例如，如果ni為13，就將這種物品分成系數(shù)分別為1,2,4,6的四件物品。分成的這幾件物品的系數(shù)和為ni，表明不可能取多于ni件的第i種物品。另外這種方法也能保證對于0.ni間的每一個整數(shù)，均可以用若干個系數(shù)的和表示，這個證明可以分0.2k-1和2k.ni兩段來分別討論得出，并不難，希望你自己思考嘗試一下。這樣就將第i種物品分成了O(log ni)種物品，將原問題轉化為了復雜度為O(V*log ni)的01背包問題，是很大的改進。O(VN)的算法多重背包問題同樣有O(VN)的算法。這個算法基于基本算法的狀態(tài)轉移方程，但應用單調隊列的方法使每個狀態(tài)的值可以以均攤O(1)的時間求解。由于用單調隊列優(yōu)化的DP已超出了NOIP的范圍，故本文不再展開講解。我最初了解到這個方法是在樓天成的“男人八題”幻燈片上。小結這里我們看到了將一個算法的復雜度由O(V*ni)改進到O(V*log ni)的過程，還知道了存在應用超出NOIP范圍的知識的O(VN)算法。希望你特別注意“拆分物品”的思想和方法，自己證明一下它的正確性，并用盡量簡潔的程序來實現(xiàn)。P04: 混合三種背包問題問題如果將P01、P02、P03混合起來。也就是說，有的物品只可以取一次（01背包），有的物品可以取無限次（完全背包），有的物品可以取的次數(shù)有一個上限（多重背包）。應該怎么求解呢？01背包與完全背包的混合考慮到在P01和P02中最后給出的偽代碼只有一處不同，故如果只有兩類物品：一類物品只能取一次，另一類物品可以取無限次，那么只需在對每個物品應用轉移方程時，根據(jù)物品的類別選用順序或逆序的循環(huán)即可，復雜度是O(VN)。偽代碼如下：for i=1.N if 第i件物品是01背包 for v=V.0 fv=maxfv,fv-ci+wi; else if 第i件物品是完全背包 for v=0.V fv=maxfv,fv-ci+wi;再加上多重背包如果再加上有的物品最多可以取有限次，那么原則上也可以給出O(VN)的解法：遇到多重背包類型的物品用單調隊列解即可。但如果不考慮超過NOIP范圍的算法的話，用P03中將每個這類物品分成O(log ni)個01背包的物品的方法也已經很優(yōu)了。小結有人說，困難的題目都是由簡單的題目疊加而來的。這句話是否公理暫且存之不論，但它在本講中已經得到了充分的體現(xiàn)。本來01背包、完全背包、多重背包都不是什么難題，但將它們簡單地組合起來以后就得到了這樣一道一定能嚇倒不少人的題目。但只要基礎扎實，領會三種基本背包問題的思想，就可以做到把困難的題目拆分成簡單的題目來解決。P05: 二維費用的背包問題問題二維費用的背包問題是指：對于每件物品，具有兩種不同的費用；選擇這件物品必須同時付出這兩種代價；對于每種代價都有一個可付出的最大值（背包容量）。問怎樣選擇物品可以得到最大的價值。設這兩種代價分別為代價1和代價2，第i件物品所需的兩種代價分別為ai和bi。兩種代價可付出的最大值（兩種背包容量）分別為V和U。物品的價值為wi。算法費用加了一維，只需狀態(tài)也加一維即可。設fivu表示前i件物品付出兩種代價分別為v和u時可獲得的最大價值。狀態(tài)轉移方程就是：fivu=maxfi-1vu,fi-1v-aiu-bi+wi。如前述方法，可以只使用二維的數(shù)組：當每件物品只可以取一次時變量v和u采用順序的循環(huán)，當物品有如完全背包問題時采用逆序的循環(huán)。當物品有如多重背包問題時拆分物品。物品總個數(shù)的限制有時，“二維費用”的條件是以這樣一種隱含的方式給出的：最多只能取M件物品。這事實上相當于每件物品多了一種“件數(shù)”的費用，每個物品的件數(shù)費用均為1，可以付出的最大件數(shù)費用為M。換句話說，設fvm表示付出費用v、最多選m件時可得到的最大價值，則根據(jù)物品的類型（01、完全、多重）用不同的方法循環(huán)更新，最后在f0.V0.M范圍內尋找答案。另外，如果要求“恰取M件物品”，則在f0.VM范圍內尋找答案。小結事實上，當發(fā)現(xiàn)由熟悉的動態(tài)規(guī)劃題目變形得來的題目時，在原來的狀態(tài)中加一緯以滿足新的限制是一種比較通用的方法。希望你能從本講中初步體會到這種方法。P06: 分組的背包問題問題有N件物品和一個容量為V的背包。第i件物品的費用是ci，價值是wi。這些物品被劃分為若干組，每組中的物品互相沖突，最多選一件。求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。算法這個問題變成了每組物品有若干種策略：是選擇本組的某一件，還是一件都不選。也就是說設fkv表示前k組物品花費費用v能取得的最大權值，則有fkv=maxfk-1v,fk-1v-ci+wi|物品i屬于第k組。使用一維數(shù)組的偽代碼如下：for 所有的組k for 所有的i屬于組k for v=V.0 fv=maxfv,fv-ci+wi另外，顯然可以對每組中的物品應用P02中“一個簡單有效的優(yōu)化”。小結分組的背包問題將彼此互斥的若干物品稱為一個組，這建立了一個很好的模型。不少背包問題的變形都可以轉化為分組的背包問題（例如P07），由分組的背包問題進一步可定義“泛化物品”的概念，十分有利于解題。P07: 有依賴的背包問題簡化的問題這種背包問題的物品間存在某種“依賴”的關系。也就是說，i依賴于j，表示若選物品i，則必須選物品j。為了簡化起見，我們先設沒有某個物品既依賴于別的物品，又被別的物品所依賴；另外，沒有某件物品同時依賴多件物品。算法這個問題由NOIP2006金明的預算方案一題擴展而來。遵從該題的提法，將不依賴于別的物品的物品稱為“主件”，依賴于某主件的物品稱為“附件”。由這個問題的簡化條件可知所有的物品由若干主件和依賴于每個主件的一個附件集合組成。按照背包問題的一般思路，僅考慮一個主件和它的附件集合?？墒牵捎玫牟呗苑浅６?，包括：一個也不選，僅選擇主件，選擇主件后再選擇一個附件，選擇主件后再選擇兩個附件無法用狀態(tài)轉移方程來表示如此多的策略。（事實上，設有n個附件，則策略有2n+1個，為指數(shù)級。）考慮到所有這些策略都是互斥的（也就是說，你只能選擇一種策略），所以一個主件和它的附件集合實際上對應于P06中的一個物品組，每個選擇了主件又選擇了若干個附件的策略對應于這個物品組中的一個物品，其費用和價值都是這個策略中的物品的值的和。但僅僅是這一步轉化并不能給出一個好的算法，因為物品組中的物品還是像原問題的策略一樣多。再考慮P06中的一句話： 可以對每組中的物品應用P02中“一個簡單有效的優(yōu)化”。 這提示我們，對于一個物品組中的物品，所有費用相同的物品只留一個價值最大的，不影響結果。所以，我們可以對主件i的“附件集合”先進行一次01背包，得到費用依次為0.V-ci所有這些值時相應的最大價值f0.V-ci。那么這個主件及它的附件集合相當于V-ci+1個物品的物品組，其中費用為ci+k的物品的價值為fk+wi。也就是說原來指數(shù)級的策略中有很多策略都是冗余的，通過一次01背包后，將主件i轉化為V-ci+1個物品的物品組，就可以直接應用P06的算法解決問題了。更一般的問題更一般的問題是：依賴關系以圖論中“森林”的形式給出（森林即多叉樹的集合），也就是說，主件的附件仍然可以具有自己的附件集合，限制只是每個物品最多只依賴于一個物品（只有一個主件）且不出現(xiàn)循環(huán)依賴。解決這個問題仍然可以用將每個主件及其附件集合轉化為物品組的方式。唯一不同的是，由于附件可能還有附件，就不能將每個附件都看作一個一般的01背包中的物品了。若這個附件也有附件集合，則它必定要被先轉化為物品組，然后用分組的背包問題解出主件及其附件集合所對應的附件組中各個費用的附件所對應的價值。事實上，這是一種樹形DP，其特點是每個父節(jié)點都需要對它的各個兒子的屬性進行一次DP以求得自己的相關屬性。這已經觸及到了“泛化物品”的思想?？赐關08后，你會發(fā)現(xiàn)這個“依賴關系樹”每一個子樹都等價于一件泛化物品，求某節(jié)點為根的子樹對應的泛化物品相當于求其所有兒子的對應的泛化物品之和。小結NOIP2006的那道背包問題我做得很失敗，寫了上百行的代碼，卻一分未得。后來我通過思考發(fā)現(xiàn)通過引入“物品組”和“依賴”的概念可以加深對這題的理解，還可以解決它的推廣問題。用物品組的思想考慮那題中極其特殊的依賴關系：物品不能既作主件又作附件，每個主件最多有兩個附件，可以發(fā)現(xiàn)一個主件和它的兩個附件等價于一個由四個物品組成的物品組，這便揭示了問題的某種本質。我想說：失敗不是什么丟人的事情，從失敗中全無收獲才是。P08: 泛化物品定義考慮這樣一種物品，它并沒有固定的費用和價值，而是它的價值隨著你分配給它的費用而變化。這就是泛化物品的概念。更嚴格的定義之。在背包容量為V的背包問題中，泛化物品是一個定義域為0.V中的整數(shù)的函數(shù)h，當分配給它的費用為v時，能得到的價值就是h(v)。這個定義有一點點抽象，另一種理解是一個泛化物品就是一個數(shù)組h0.V，給它費用v，可得到價值hV。一個費用為c價值為w的物品，如果它是01背包中的物品，那么把它看成泛化物品，它就是除了h(c)=w其它函數(shù)值都為0的一個函數(shù)。如果它是完全背包中的物品，那么它可以看成這樣一個函數(shù)，僅當v被c整除時有h(v)=v/c*w，其它函數(shù)值均為0。如果它是多重背包中重復次數(shù)最多為n的物品，那么它對應的泛化物品的函數(shù)有h(v)=v/c*w僅當v被c整除且v/c=n，其它情況函數(shù)值均為0。一個物品組可以看作一個泛化物品h。對于一個0.V中的v，若物品組中不存在費用為v的的物品，則h(v)=0，否則h(v)為所有費用為v的物品的最大價值。P07中每個主件及其附件集合等價于一個物品組，自然也可看作一個泛化物品。泛化物品的和如果面對兩個泛化物品h和l，要用給定的費用從這兩個泛化物品中得到最大的價值，怎么求呢？事實上，對于一個給定的費用v，只需枚舉將這個費用如何分配給兩個泛化物品就可以了。同樣的，對于0.V的每一個整數(shù)v，可以求得費用v分配到h和l中的最大價值f(v)。也即f(v)=maxh(k)+l(v-k)|0=k=v?？梢钥吹剑琭也是一個由泛化物品h和l決定的定義域為0.V的函數(shù)，也就是說，f是一個由泛化物品h和l決定的泛化物品。由此可以定義泛化物品的和：h、l都是泛化物品，若泛化物品f滿足f(v)=maxh(k)+l(v-k)|0=k0) if(giv=0) print 未選第i項物品 else if(giv=1) print 選了第i項物品 v=v-ci另外，采用方程的前一項或后一項也可以在輸出方案的過程中根據(jù)fiv的值實時地求出來，也即不須紀錄g數(shù)組，將上述代碼中的giv=0改成fiv=fi-1v，giv=1改成fiv=fi-1v-ci+wi也可。輸出字典序最小的最優(yōu)方案這里“字典序最小”的意思是1.N號物品的選擇方案排列出來以后字典序最小。以輸出01背包最小字典序的方案為例。一般而言，求一個字典序最小的最優(yōu)方案，只需要在轉移時注意策略。首先，子問題的定義要略改一些。我們注意到，如果存在一個選了物品1的最優(yōu)方案，那么答案一定包含物品1，原問題轉化為一個背包容量為v-c1，物品為2.N的子問題。反之，如果答案不包含物品1，則轉化成背包容量仍為V，物品為2.N的子問題。不管答案怎樣，