背包問題題目及含義

背包它是在1978年由Merkel和Hellman提出的。它的主要思路是假定某人擁有大量物品，重量各不同。此人通過秘密地選擇一部分物品并將它們放到背包中來加密消息。背包中的物品中重量是公開的，所有可能的物品也是公開的，但背包中的物品是保密的。附加一定的限制條件，給出重量，而要列出可能的物品，在計算上是不可實現(xiàn)的。背包問題是熟知的不可計算問題，背包體制以其加密，解密速度快而其人注目。但是，大多數(shù)一次背包體制均被破譯了，因此現(xiàn)在很少有人使用它。DD牛的背包九講P01:01背包問題題目有N件物品和一個容量為V的背包。第i件物品的費用是c，價值是w。求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大?；舅悸愤@是最基礎(chǔ)的背包問題，特點是：每種物品僅有一件，可以選擇放或不放。用子問題定義狀態(tài)：即f[v]表示前i件物品恰放入一個容量為v的背包可以獲得的最大價值。則其狀態(tài)轉(zhuǎn)移方程便是：f[v]=max{f[v],f[v-c]+w}。這個方程非常重要，基本上所有跟背包相關(guān)的問題的方程都是由它衍生出來的。所以有必要將它詳細解釋一下：“將前i件物品放入容量為v的背包中”這個子問題，若只考慮第i件物品的策略(放或不放)，那么就可以轉(zhuǎn)化為一個只牽扯前i-1件物品的問題。如果不放第i件物品，那么問題就轉(zhuǎn)化為“前i-1件物品放入容量為v的背包中”；如果放第i件物品，那么問題就轉(zhuǎn)化為“前i-1件物品放入剩下的容量為v-c的背包中”，此時能獲得的最大價值就是f[v-c]再加上通過放入第i件物品獲得的價值w。注意f[v]有意義當且僅當存在一個前i件物品的子集，其費用總和為v。所以按照這個方程遞推完畢后，最終的答案并不一定是f[N][V]，而是f[N][0..V]的最大值。如果將狀態(tài)的定義中的，，恰，，字去掉，在轉(zhuǎn)移方程中就要再加入一項f[v-1]，這樣就可以保證f[N][V]就是最后的答案。至于為什么這樣就可以，由你自己來體會了。優(yōu)化空間復(fù)雜度以上方法的時間和空間復(fù)雜度均為O(N*V)，其中時間復(fù)雜度基本已經(jīng)不能再優(yōu)化了，但空間復(fù)雜度卻可以優(yōu)化到O(V)。先考慮上面講的基本思路如何實現(xiàn)，肯定是有一個主循環(huán)i=1..N，每次算出來二維數(shù)組f[0..V]的所有值。那么，如果只用一個數(shù)組f[0..V]，能不能保證第i次循環(huán)結(jié)束后f[v]中表示的就是我們定義的狀態(tài)f[v]呢？f[v]是由f[v]和f[v-c]兩個子問題遞推而來，能否保證在推f[v]時(也即在第i次主循環(huán)中推f[v]時)能夠得到f[v]和f[v-c]的值呢？事實上，這要求在每次主循環(huán)中我們以v=V..0的順序推f[v]，這樣才能保證推f[v]時f[v-c]保存的是狀態(tài)f[v-c]的值。偽代碼如下：for『1..Nforv=V..0f[v]=max{f[v],f[v-c]+w};其中的f[v]=max{f[v],f[v-c]"句恰就相當于我們的轉(zhuǎn)移方程f[v]=max{f[v],f[v-c]}，因為現(xiàn)在的f[v-c]就相當于原來的f[v-c]。如果將v的循環(huán)順序從上面的逆序改成順序的話，那么則成了f[v]由f[v-c]推知，與本題意不符，但它卻是另一個重要的背包問題P02最簡捷的解決方案，故學(xué)習(xí)只用一維數(shù)組解01背包問題是十分必要的?？偨Y(jié)01背包問題是最基本的背包問題，它包含了背包問題中設(shè)計狀態(tài)、方程的最基本思想，另外，別的類型的背包問題往往也可以轉(zhuǎn)換成01背包問題求解。故一定要仔細體會上面基本思路的得出方法，狀態(tài)轉(zhuǎn)移方程的意義，以及最后怎樣優(yōu)化的空間復(fù)雜度。P02:完全背包問題題目有N種物品和一個容量為V的背包，每種物品都有無限件可用。第i種物品的費用是c，價值是w。求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大?；舅悸愤@個問題非常類似于01背包問題，所不同的是每種物品有無限件。也就是從每種物品的角度考慮，與它相關(guān)的策略已并非取或不取兩種，而是有取0件、取1件、取2件......等很多種。如果仍然按照解01背包時的思路，令f[v]表示前i種物品恰放入一個容量為v的背包的最大權(quán)值。仍然可以按照每種物品不同的策略寫出狀態(tài)轉(zhuǎn)移方程，像這樣：f[v]=max{f[v-k*c]+k*w|0<=k*c<=v}。這跟01背包問題一樣有O(N*V)個狀態(tài)需要求解，但求解每個狀態(tài)的時間則不是常數(shù)了，求解狀態(tài)f[v]的時間是O(v/c)，總的復(fù)雜度是超過O(VN)的。將01背包問題的基本思路加以改進，得到了這樣一個清晰的方法。這說明01背包問題的方程的確是很重要，可以推及其它類型的背包問題。但我們還是試圖改進這個復(fù)雜度。一個簡單有效的優(yōu)化完全背包問題有一個很簡單有效的優(yōu)化，是這樣的：若兩件物品i、j滿足c<=c[j]且w>=w[j]，則將物品j去掉，不用考慮。這個優(yōu)化的正確性顯然：任何情況下都可將價值小費用高得j換成物美價廉的i，得到至少不會更差的方案。對于隨機生成的數(shù)據(jù)，這個方法往往會大大減少物品的件數(shù)，從而加快速度。然而這個并不能改善最壞情況的復(fù)雜度，因為有可能特別設(shè)計的數(shù)據(jù)可以一件物品也去不掉。轉(zhuǎn)化為01背包問題求解既然01背包問題是最基本的背包問題，那么我們可以考慮把完全背包問題轉(zhuǎn)化為01背包問題來解。最簡單的想法是，考慮到第i種物品最多選V/c件，于是可以把第i種物品轉(zhuǎn)化為V/c件費用及價值均不變的物品，然后求解這個01背包問題。這樣完全沒有改進基本思路的時間復(fù)雜度，但這畢竟給了我們將完全背包問題轉(zhuǎn)化為01背包問題的思路：將一種物品拆成多件物品。更高效的轉(zhuǎn)化方法是：把第i種物品拆成費用為c*2%、價值為w*2W的若干件物品，其中k滿足c*2W<V。這是二進制的思想，因為不管最優(yōu)策略選幾件第i種物品，總可以表示成若干個2W件物品的和。這樣把每種物品拆成O(log(V/c))件物品，是一個很大的改進。但我們有更優(yōu)的O(VN)的算法。*O(VN)的算法這個算法使用一維數(shù)組，先看偽代碼：<preclass"example">for『1..Nforv=0..Vf[v]=max{f[v],f[v-c]+w};你會發(fā)現(xiàn)，這個偽代碼與P01的偽代碼只有v的循環(huán)次序不同而已。為什么這樣一改就可行呢？首先想想為什么P01中要按照v=V..0的逆序來循環(huán)。這是因為要保證第i次循環(huán)中的狀態(tài)f[v]是由狀態(tài)f[v-c]遞推而來。換句話說，這正是為了保證每件物品只選一次，保證在考慮“選入第i件物品”這件策略時，依據(jù)的是一個絕無已經(jīng)選入第i件物品的子結(jié)果f[v-c]。而現(xiàn)在完全背包的特點恰是每種物品可選無限件，所以在考慮'加選一件第i種物品”這種策略時，卻正需要一個可能已選入第i種物品的子結(jié)果f[v-c]，所以就可以并且必須采用v=0..V的順序循環(huán)。這就是這個簡單的程序為何成立的道理。這個算法也可以以另外的思路得出。例如，基本思路中的狀態(tài)轉(zhuǎn)移方程可以等價地變形成這種形式：f[v]=max{f[v],f[v-c]+w}，將這個方程用一維數(shù)組實現(xiàn)，便得到了上面的偽代碼?？偨Y(jié)完全背包問題也是一個相當基礎(chǔ)的背包問題，它有兩個狀態(tài)轉(zhuǎn)移方程，分別在“基本思路”以及“O(VN)的算法“的小節(jié)中給出。希望你能夠?qū)@兩個狀態(tài)轉(zhuǎn)移方程都仔細地體會，不僅記住，也要弄明白它們是怎么得出來的，最好能夠自己想一種得到這些方程的方法。事實上，對每一道動態(tài)規(guī)劃題目都思考其方程的意義以及如何得來，是加深對動態(tài)規(guī)劃的理解、提高動態(tài)規(guī)劃功力的好方法。P03:多重背包問題題目有N種物品和一個容量為V的背包。第i種物品最多有n件可用，每件費用是c，價值是w。求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大?；舅惴ㄟ@題目和完全背包問題很類似?；镜姆匠讨恍鑼⑼耆嘲鼏栴}的方程略微一改即可，因為對于第i種物品有n+1種策略：取0件，取1件......取n件。令f[v]表示前i種物品恰放入一個容量為v的背包的最大權(quán)值，則：f[v]=max{f[v-k*c]+k*w|0<=k<=n}。復(fù)雜度是O(V*￡n)。轉(zhuǎn)化為01背包問題另一種好想好寫的基本方法是轉(zhuǎn)化為01背包求解:把第i種物品換成n件01背包中的物品，則得到了物品數(shù)為￡n的01背包問題，直接求解，復(fù)雜度仍然是O(V*￡n)。但是我們期望將它轉(zhuǎn)化為01背包問題之后能夠像完全背包一樣降低復(fù)雜度。仍然考慮二進制的思想，我們考慮把第i種物品換成若干件物品，使得原問題中第i種物品可取的每種策略一取0..n件——均能等價于取若干件代換以后的物品。另外，取超過n件的策略必不能出現(xiàn)。方法是：將第i種物品分成若干件物品，其中每件物品有一個系數(shù)，這件物品的費用和價值均是原來的費用和價值乘以這個系數(shù)。使這些系數(shù)分別為1,2,4,...,2A(k-1),n-2W+1,且k是滿足n-2W+1>0的最大整數(shù)。例如，如果n為13,就將這種物品分成系數(shù)分別為1,2,4,6的四件物品。分成的這幾件物品的系數(shù)和為n，表明不可能取多于n件的第i種物品。另外這種方法也能保證對于0..n間的每一個整數(shù)，均可以用若干個系數(shù)的和表示，這個證明可以分0..2W-1和2W..n兩段來分別討論得出，并不難，希望你自己思考嘗試一下。這樣就將第i種物品分成了O(logn)種物品，將原問題轉(zhuǎn)化為了復(fù)雜度為O(V*￡logn)的01背包問題，是很大的改進。O(VN)的算法多重背包問題同樣有O(VN)的算法。這個算法基于基本算法的狀態(tài)轉(zhuǎn)移方程，但應(yīng)用單調(diào)隊列的方法使每個狀態(tài)的值可以以均攤0(1)的時間求解。由于用單調(diào)隊列優(yōu)化的DP已超出了N0IP的范圍，故本文不再展開講解。我最初了解到這個方法是在樓天成的'男人八題”幻燈片上。小結(jié)這里我們看到了將一個算法的復(fù)雜度由O(V*Zn)改進到O(V*￡logn)的過程，還知道了存在應(yīng)用超出N0IP范圍的知識的0(VN)算法。希望你特別注意“拆分物品”的思想和方法，自己證明一下它的正確性，并用盡量簡潔的程序來實現(xiàn)。P04:混合三種背包問題問題如果將P01、P02、P03混合起來。也就是說，有的物品只可以取一次(01背包)，有的物品可以取無限次(完全背包)，有的物品可以取的次數(shù)有一個上限(多重背包)。應(yīng)該怎么求解呢？

曰背包問題的一個例子：應(yīng)該選擇哪些盒子，才能使價格盡可能地大，而保持重量小于或等于15kg？背包問題(Knapsackproblem)是一種組合優(yōu)化的NP完全問題。問題可以描述為：給定一組物品，每種物品都有自己的重量和價格，在限定的總重量內(nèi)，我們?nèi)绾芜x擇，才能使得物品的總價格最高。問題的名稱來源于如何選擇最合適的物品放置于給定背包中。相似問題經(jīng)常出現(xiàn)在商業(yè)、組合數(shù)學(xué)，計算復(fù)雜性理論、密碼學(xué)和應(yīng)用數(shù)學(xué)等領(lǐng)域中。也可以將背包問題描述為決定性問題，即在總重量不超過W的前提下，總價值是否能達到V？目錄［隱藏］1定義.2計算復(fù)雜度3動態(tài)規(guī)劃解法o3.1無界背包問題o3.20-1背包問題4二次背包問題5外部鏈接Q［編輯］定義我們有n種物品，物品j的重量為w,價格為p.。我們假定所有物品的重量和價格都是非負的。背包所能承受的最大重量為w。J如果限定每種物品只能選擇0個或1個則問題稱為0-1背包問題可以用公式表示為:

nmaximizenEwixi幺W'勺E{°，1}subjectto1如果限定物品j最多只能選擇b個，則問題稱為有界背包問題?？梢杂霉奖硎緸?jn件jmaximize■:1nEW3X3幺W'X3G{0?L.…bj}subjectto-如果不限定每種物品的數(shù)量，則問題稱為無界背包問題。［編輯］［編輯］計算復(fù)雜度1=?利用動態(tài)規(guī)劃，背包問題存在一個偽多項式時間算法?把上而算法作為子程序，背包問題存在完全逼近多項式時間方案?作為NP完全問題，背包問題沒有一種既準確又快速(多項式時間)的算法［編輯］動態(tài)規(guī)劃解法［編輯］無界背包問題如果重量w1,...,w和W都是非負的，那么用動態(tài)規(guī)劃，可以用偽多項式時間解決背包問題。下面描述了無界背包問題的解法。簡便起見，我們假定重量都是正的(Wj.>0)。在總重量不超過W的前提下，我們希望總價格最高。對于Y<W,我們將在總重量不超過Y的前提下，總價格所能達到的最高值定義為A(Y)。A(W)即為問題的答案。顯然，A(Y)滿足：A(0)=0A(Y)=max{A(Y-1),max{當+A(Y-w.)|w.WY}}其中，當為第j種物品的價格。

關(guān)于第二個公式的一個解釋：總重量為Y時背包的最高價值可能有兩種情況，第一種是該重量無法被完全填滿，這對應(yīng)于表達式A(Y-1)。第二種是剛好填滿，這對應(yīng)于一個包含一系列剛好填滿的可能性的集合，其中的可能性是指當最后放進包中的物品恰好是重量為w.的物品時背包填滿并達到最高價值而這時的背包價值等于重量為w.物品的價值和當沒有放入該物品時背包的最高價值之和。故歸納為表達式P.+A(Y-W.)。最后把所有上述情況中背包價值的最大值求出就得到了a(y)的值。JJ如果總重量為0,總價值也為0。然后依次計算A(0),A(1),...,A(W)，并把每一步驟的結(jié)果存入表中供后續(xù)步驟使用，完成這些步驟后A(W)即為最終結(jié)果