背包問題九講和源程序(答案)

1、背包問題九講和源程序(答案).txt臺灣一日不收復(fù)，我一日不過4級！如果太陽不出來了，我就不去上班了；如果出來了，我就繼續(xù)睡覺！目錄第一講01背包問題這是最基本的背包問題，每個物品最多只能放一次。第二講完全背包問題第二個基本的背包問題模型，每種物品可以放無限多次。第三講多重背包問題每種物品有一個固定的次數(shù)上限。第四講混合三種背包問題將前面三種簡單的問題疊加成較復(fù)雜的問題。第五講二維費(fèi)用的背包問題一個簡單的常見擴(kuò)展。第六講分組的背包問題一

2、種題目類型，也是一個有用的模型。后兩節(jié)的基礎(chǔ)。第七講有依賴的背包問題另一種給物品的選取加上限制的方法。第八講泛化物品我自己關(guān)于背包問題的思考成果，有一點(diǎn)抽象。第九講背包問題問法的變化試圖觸類旁通、舉一反三。附：USACO中的背包問題給出USACOTraining上可供練習(xí)的背包問題列表，及簡單的解答。P01:01背包問題題目有N件物品和一個容量為V的背包。第i件物品的費(fèi)用是c[i]，價值是w[i]。求解將哪些物品裝入背包可使價值總和最大

3、?；舅悸愤@是最基礎(chǔ)的背包問題，特點(diǎn)是：每種物品僅有一件，可以選擇放或不放。用子問題定義狀態(tài)：即f[i][v]表示前i件物品恰放入一個容量為v的背包可以獲得的最大價值。則其狀態(tài)轉(zhuǎn)移方程便是：f[i][v]=maxf[i1][v]f[i1][vc[i]]w[i]這個方程非常重要，基本上所有跟背包相關(guān)的問題的方程都是由它衍生出來的。所以有必要將它詳細(xì)解釋一下：“將前i件物品放入容量為v的背包中”這個子問題，若只考慮第i件物品的策略（放或不放

4、），那么就可以轉(zhuǎn)化為一個只牽扯前i1件物品的問題。如果不放第i件物品，那么問題就轉(zhuǎn)化為“前i1件物品放入容量為v的背包中”，價值為f[i1][v]；如果放第i件物品，那么問題就轉(zhuǎn)化為“前i1件物品放入剩下的容量為vc[i]的背包中”，此時能獲得的最大價值就是f[i1][vc[i]]再加上通過放入第i件物品獲得的價值w[i]。優(yōu)化空間復(fù)雜度以上方法的時間和空間復(fù)雜度均為O(NV)，其中時間復(fù)雜度基本已經(jīng)不能再優(yōu)化了，但空間復(fù)雜度卻可以優(yōu)化

5、到O(V)。先考慮上面講的基本思路如何實(shí)現(xiàn)，肯定是有一個主循環(huán)i=1..N，每次算出來二維數(shù)組f[i][0..V]的所有值。那么，如果只用一個數(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]]兩個子問題遞推而來，能否保證在推f[i][v]時（也即在第i次主循環(huán)中推f[v]時）能夠得到首頁P(yáng)02:完全背包問題題目有N種物品和一個容量

6、為V的背包，每種物品都有無限件可用。第i種物品的費(fèi)用是c[i]，價值是w[i]。求解將哪些物品裝入背包可使這些物品的費(fèi)用總和不超過背包容量，且價值總和最大?；舅悸愤@個問題非常類似于01背包問題，所不同的是每種物品有無限件。也就是從每種物品的角度考慮，與它相關(guān)的策略已并非取或不取兩種，而是有取0件、取1件、取2件……等很多種。如果仍然按照解01背包時的思路，令f[i][v]表示前i種物品恰放入一個容量為v的背包的最大權(quán)值。仍然可以按照每

7、種物品不同的策略寫出狀態(tài)轉(zhuǎn)移方程，像這樣：f[i][v]=maxf[i1][vkc[i]]kw[i]|0=w[j]，則將物品j去掉，不用考慮。這個優(yōu)化的正確性顯然：任何情況下都可將價值小費(fèi)用高得j換成物美價廉的i，得到至少不會更差的方案。對于隨機(jī)生成的數(shù)據(jù)，這個方法往往會大大減少物品的件數(shù)，從而加快速度。然而這個并不能改善最壞情況的復(fù)雜度，因?yàn)橛锌赡芴貏e設(shè)計(jì)的數(shù)據(jù)可以一件物品也去不掉。這個優(yōu)化可以簡單的O(N^2)地實(shí)現(xiàn)，一般都可以承受

8、。另外，針對背包問題而言，比較不錯的一種方法是：首先將費(fèi)用大于V的物品去掉，然后使用類似計(jì)數(shù)排序的做法，計(jì)算出費(fèi)用相同的物品中價值最高的是哪個，可以O(shè)(VN)地完成這個優(yōu)化。這個不太重要的過程就不給出偽代碼了，希望你能獨(dú)立思考寫出偽代碼或程序。轉(zhuǎn)化為01背包問題求解既然01背包問題是最基本的背包問題，那么我們可以考慮把完全背包問題轉(zhuǎn)化為01背包問題來解。最簡單的想法是，考慮到第i種物品最多選Vc[i]件，于是可以把第i種物品轉(zhuǎn)化為Vc[

9、i]件費(fèi)用及價值均不變的物品，然后求解這個01背包問題。這樣完全沒有改進(jìn)基本思路的時間復(fù)雜度，但這畢竟給了我們將完全背包問題轉(zhuǎn)化為01背包問題的思路：將一種物品拆成多件物品。更高效的轉(zhuǎn)化方法是：把第i種物品拆成費(fèi)用為c[i]2^k、價值為w[i]2^k的若干件物品，其中k滿足c[i]2^k=V。這是二進(jìn)制的思想，因?yàn)椴还茏顑?yōu)策略選幾件第i種物品，總可以表示成若干個2^k件物品的和。這樣把每種物品拆成O(log(Vc[i]))件物品，是一