用動態(tài)規(guī)劃方法求解廣義背包問題 final

1、火Ex亭2014在職工程碩士算法分析與設(shè)計(jì)廣義背包問題實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱：用動魏a劃方法求解廣義背包問題蒲小眥員:實(shí)驗(yàn)時(shí)間：2014年10月報(bào)告完成時(shí)間：2014年11月北京工業(yè)大學(xué)2014在職工程碩士算法分析與設(shè)計(jì)上機(jī)題 廣義背包(General Knapsack Problem )問題 用動態(tài)規(guī)劃方法解決廣義背包GKP問題基于對動態(tài)規(guī)劃方法的了解，我們將采用動態(tài)規(guī)劃的方法解決廣義背包問題GKP(General Knapsack Problem)。問題描述給定載重量為M的背包和n種物品，每種物品有一定的重量和價(jià)值，現(xiàn)在 需要設(shè)計(jì)算法，在不超過背包載重量的前提下，巧妙選擇物品，使得裝入背包的 物

2、品的總價(jià)值最大化。規(guī)則是，每種物品均可裝入背包多次或不裝入(但不能僅 裝入物品的一部分)二數(shù)學(xué)描述堿給定背包重量為M0;給定n中物品其重量分別為W1，W2，W3,Wn;n種物品對應(yīng)的價(jià)值為vi，v2f v3fvn ;設(shè)為為篥i種物品裝入背包的數(shù)量；若篥i種物品不裝入則由取值為0；有題目給定可知，物品可反復(fù)裝入，即均可取 1,2,3.,但由于背包的總?cè)萘繛镸,所以第i種物品裝入背包的次數(shù)X應(yīng)當(dāng)滿足如 下條件嗎況 M,即篥i種物品的總重量(篥i種物品單個(gè)的重量Wj乘以放入的 次i數(shù)g)應(yīng)當(dāng)小于總?cè)萘?否則無法放入，另外由于題目給定不能僅裝入某物品的 一部分可知放入次數(shù)為必須為整數(shù)。因此可得為的取值

3、范圍是0 Xili1(由雄式九1，=，MI 0 i n三、遞歸公式廣義背包問題非常類似于0-1背包問題，所不同的是每種物品有無限件。也 就是從每種物品的角度考慮，與它相關(guān)的策略已并非取或不取兩種，而是有取0 件、取1件、取2件.等很多種如果仍然按照解01背包時(shí)的思路，令m(ij)表示從前i種物品選取若 干放入一個(gè)容量為j的背包的最大權(quán)值。仍然可以按照每種物品不同的策略寫 出狀態(tài)轉(zhuǎn)移方程(遞歸公式)，廣.)=j m(i- l,j),0 j Wim L J (max(m(i - 1, j), m(i - 1J - XjWj) + x, 0 XjWj j其邊界條件為:(0f 0 j WnXn篥一個(gè)式

4、子表明：如果第i種物品的重量大于背包的容量，則裝入前i種物品得到的最大價(jià)值和裝入前i-l種物品得到的最大值是相同的,即物品i不能裝入背篥二個(gè)式子表明:如果篥i種物品的重量小于背包容量,則會有以下兩種情況:L如果把第i種物品裝入背包，則背包中物品的價(jià)值等于把前i-l種物品裝入 容量為j -XiWi的背包的價(jià)值加上第i種物品的價(jià)值XjWi。2.如果篥i種物品沒有裝入背包，則背包中物品的價(jià)值就等于把前面i-l種 物品裝入容量為J的背包中所取得的價(jià)值。顯然取二者中價(jià)值大者作為把前i種物品裝入容量為j的背包中的最優(yōu)解。,時(shí)間復(fù)雜度這跟0-1背包問題一樣有O(MN)個(gè)狀態(tài)需要求解但因?yàn)槎嗔艘粋€(gè)參數(shù)x, 求

5、解每個(gè)狀態(tài)的時(shí)間則不是常數(shù)了需在原有0-1背包問題的基礎(chǔ)上加一層數(shù)量 的循環(huán)，偽代碼如下：for i = Nfor j=0.M for(x=0;x*wi v=j；x+)mij=maxmi-lj,mi-lj-x*wi+x*vi求解狀態(tài)mij的時(shí)間是那么總的時(shí)間復(fù)雜度就是ZM五，算法實(shí)現(xiàn)1.算法優(yōu)化因?yàn)橥籱勿品可以選取多次，那么可以通過計(jì)算每件物品的單位價(jià)值，來 優(yōu)先放進(jìn)單價(jià)最高的物品。這個(gè)優(yōu)化的正確性顯然：田可情況下都可閣介值小重 量用高得a換成物美價(jià)廉的b，得到至少不會更差的方案。這里可以用快速排序的方法對物品進(jìn)行單價(jià)排序，時(shí)間復(fù)雜度為0(N2)另外，針對背包問題而言，比較不錯的一種方法是：

6、首先將重量大于M的 物品去掉，然后使用類似計(jì)數(shù)排序的做法案，計(jì)算出重量相同的物品中價(jià)值最高 的是哪個(gè)，可以O(shè)(V+N)地完成這個(gè)優(yōu)化。2.運(yùn)行結(jié)果默認(rèn)數(shù)據(jù)來自于算法教材(篥三版)133頁的示例，我們運(yùn)行結(jié)果是物品 4裝入7次總價(jià)值等于28我們實(shí)現(xiàn)充分考慮到測試算法各細(xì)節(jié)的需要,可以修改已有物品的重量和價(jià) 值，然后重新計(jì)算出新的結(jié)果，如下圖所示根據(jù)算法教材(篥三版)133頁的示 例數(shù)據(jù)，將物品3的價(jià)值從7修改為13 ,可得出新的裝入方案即物品3裝入3 次，物品4裝入1次，總價(jià)值3*13+1*4=43除此之外我們的實(shí)現(xiàn)還可以隨機(jī)生成物品種類修改各參數(shù)，如下圖所示, 隨機(jī)生成5種物品，修改部分價(jià)值，

7、按照背包容量為11 ,計(jì)算出新的裝入方案: 物品1裝入1次，物品3裝入2次，物品5裝入1次，總價(jià)值1012o北京工業(yè)大學(xué)2014在職工程碩士算法分析與設(shè)計(jì)上機(jī)題3.相關(guān)代碼動態(tài)規(guī)劃部分代碼/ Kparan nae=-tLis-t排好序的物品清單，單價(jià)從低到高/ Kparajii 11孫自=，。槌/背包總答照。pa匚邱/ 不放入的單勺更高的物品數(shù)里/ J 史最高總價(jià)。paramprivate void Algo r it hm (Ar r ayL 1st tList, int total, int *t op, int o Idiot al) if (hasMax)/記錄是否已經(jīng)找到最優(yōu)選擇初始

8、化為0return;int tv = 0;int left = tot al;for (int i = 1: i old!otal)當(dāng)前總作值超過之前的方案oldTotal = tv;resutIList = new ArrayList(tList):tList = new ArrayList (tOldList):Algorithm(tList, -total, +top3 tv);elseif (top = tList.Count)return;之前方案更好tList = new ArrayList (tOldList);Algorithm(tList, *total, +top, old

9、Total):firegion裝入第i個(gè)物品tmp. n = left / tmp.w; left = left % tmp.w;tv += tmp. n * tmp.v;tList tList. Count - i - top = tmp;if (left = 0)break;Sendregion快速排序算法源碼region快速排序定位private int Part it ion (ref ArrayLisl List5 int loWj int high)|int i = low;int j = high;object keyObj = list low:double key = (El

10、ement)list lo-ur). pv;while (i key 炭& j i)一一 j：list i = list j;while (Elemerrt)list i) .pv i)+i；= list i;list i = keyObj;return j：快速排序private void QSort(ref ArrayList list, int low, int high)if (Low high)int q = Part it ion (ref listj Low, high):QSort (ref list, low。 q - 1);QSort (ref list, q + high):private void QSort (ref ArrayList list)this. QSort (ref list5 0, list. Count - 1):#endreg:ion13 14 15 16 17 36 37 44 45 51 52 66 67 lly 120 181 182 252 253 260 261 299 300 350 351 369 370 557 558 606 607 608 609-namespace hnap sackPr ob LemS田.publ