背包問(wèn)題和TSP問(wèn)題算法報(bào)告

1、算法報(bào)告班 級(jí)： 140710班 組 員： 14071006 魏澤琳 14071008 田 恬 14071019 黃婧婧 14071021 宋 蕊 14071026 于婷雯 指導(dǎo)老師： 徐旭東 廣義背包問(wèn)題 一、問(wèn)題描述廣義背包問(wèn)題的描述如下：給定載重量為M的背包和n種物品，每種物品有一定的重量和價(jià)值，現(xiàn)在需要設(shè)計(jì)算法，在不超過(guò)背包載重量的前提下，巧妙選擇物品，使得裝入背包的物品的總價(jià)值最大化。規(guī)則是，每種物品均可裝入背包多次或不裝入（但不能僅裝入物品的一部分）。請(qǐng)用數(shù)學(xué)語(yǔ)言對(duì)上述背包問(wèn)題加以抽象，在此基礎(chǔ)上給出動(dòng)態(tài)規(guī)劃求解該問(wèn)題的遞歸公式。要求對(duì)所給公式中的符號(hào)意義加以詳細(xì)說(shuō)明，并簡(jiǎn)述算法的

2、求解步驟。用一種你熟悉的程序設(shè)計(jì)語(yǔ)言加以實(shí)現(xiàn)。二、基本思路1、01背包問(wèn)題在討論廣義背包問(wèn)題前應(yīng)該先討論最基礎(chǔ)的01背包問(wèn)題。這是最基礎(chǔ)的背包問(wèn)題，特點(diǎn)是：每種物品僅有一件，可以選擇放或不放。用子問(wèn)題定義狀態(tài)：即Fim表示前i件物品恰放入一個(gè)重量為m的背包可以獲得的最大價(jià)值。其狀態(tài)轉(zhuǎn)移方程是：Fim=maxFi1m,Fi1mwi+Ci這個(gè)方程是解決背包問(wèn)題的關(guān)鍵點(diǎn)，基本上所有跟背包相關(guān)的問(wèn)題的方程都是由它衍生出來(lái)的。所以有必要解釋一下：“將前i件物品放入容量為m的背包中”這個(gè)子問(wèn)題，若只考慮第i件物品的策略（放或不放），那么就可以轉(zhuǎn)化為一個(gè)只和前i1件物品相關(guān)的問(wèn)題。如果不放第i件物品，那么問(wèn)

3、題就轉(zhuǎn)化為“前i1件物品放入容量為v的背包中”，價(jià)值為Fi1m；如果放第i件物品，那么問(wèn)題就轉(zhuǎn)化為“前i1件物品放入剩下的容量為mwi的背包中”，此時(shí)能獲得的最大價(jià)值就是Fi1mwi再加上通過(guò)放入第i件物品獲得的價(jià)值Ci。最優(yōu)解的函數(shù)從方程中能得出:Fim=Fi-1m(當(dāng)?shù)趇個(gè)物品不裝入)Fim>Fi-1m(當(dāng)?shù)趇個(gè)物品裝入)以上是有關(guān)01背包的討論，現(xiàn)在討論廣義背包的問(wèn)題。2、廣義背包問(wèn)題與01背包的區(qū)別：每種物品都有無(wú)限件，能放多少就放多少。 問(wèn)題:在不超過(guò)背包重量的情況下，能獲得的最大價(jià)值。舉例：物品個(gè)數(shù)N = 3，背包重量為M = 5，則背包可以裝下的最大價(jià)值為40.如下表：基本

4、思路（直接擴(kuò)展01背包的方程）直接擴(kuò)展01背包的方程：由于本問(wèn)題類(lèi)似于01背包問(wèn)題，在01背包問(wèn)題中，物品要么取，要么不取，而在廣義背包中，物品可以取0件、取1件、取2件.直到背包放不下位置。因此，可以直接在01背包的遞推式中擴(kuò)展得到：Fim:表示前i件物品放入重量為m的背包中時(shí)的最大價(jià)值遞推式：Fim = max(Fi 1m,Fi -1m- K * wi+ K * Ci);其中 1 <= K <= m/wi(m指此時(shí)背包重量)/初始條件f0m = 0;fi0 = 0;Valuei為第i件物品的價(jià)值；矩陣圖如下：fim第i件物品是否裝入，此時(shí)容量為M的背包的最大價(jià)值0 1 2 3

5、4 5 6000000001051015252530200101520303530001520253040000202530此程序運(yùn)行結(jié)果為35。復(fù)雜度分析：程序需要求解N*M個(gè)狀態(tài)，每一個(gè)狀態(tài)需要的時(shí)間為O（m/Weighti），所以總的復(fù)雜度為O(NM*(M/Weighti)。思考：完全背包問(wèn)題有一個(gè)很簡(jiǎn)單有效的優(yōu)化，是這樣的：若兩件物品i、j滿(mǎn)足ci<=cj且wi>=wj，則將物品j去掉，不用考慮。(c=Cost價(jià)格，w=Weight重量）即，如果一個(gè)物品A是占的地少且價(jià)值高，而物品B是占地多，但是價(jià)值不怎么高，那么肯定是優(yōu)先考慮A物品的。TSP問(wèn)題一、問(wèn)題描述所謂TSP問(wèn)題

6、是指旅行商要去n個(gè)城市推銷(xiāo)商品，其中每個(gè)城市到達(dá)且僅到達(dá)一次，并且要求所走的路程最短（該問(wèn)題又稱(chēng)貨郎擔(dān)問(wèn)題、郵遞員問(wèn)題、售貨員問(wèn)題等）。TSP問(wèn)題最容易想到、也肯定能得到最優(yōu)解的算法是窮舉法，即考察所有可能的行走線(xiàn)路，從中選出最佳的一條。但是用窮舉法求解TSP問(wèn)題的時(shí)間復(fù)雜性為O(n!)，屬于NP問(wèn)題。請(qǐng)用數(shù)學(xué)語(yǔ)言對(duì)該TSP問(wèn)題加以抽象，在此基礎(chǔ)上給出動(dòng)態(tài)規(guī)劃求解該問(wèn)題的遞推公式。要求對(duì)所給公式中的符號(hào)意義加以詳細(xì)說(shuō)明，并簡(jiǎn)述算法求解步驟。用一種你熟悉的程序設(shè)計(jì)語(yǔ)言加以實(shí)現(xiàn)。二、基本思路Length（總回路）= Length（S0S1）+Length（S1S2S3S0）把問(wèn)題簡(jiǎn)化：把求通過(guò)各點(diǎn)

7、的一條最短的回路 求解從某個(gè)（任意）確定點(diǎn)到回路最后一個(gè)點(diǎn)的最短路徑。規(guī)范化公式：d（i，V）表示從i點(diǎn)經(jīng)過(guò)點(diǎn)集V各點(diǎn)一次之后回到出發(fā)點(diǎn)的最短距離d（i，V）= minCik + d(k,V k)d（k，）= Cik （其中，Cik表示ik的距離）舉例：node 0 1 2 3 0 5 3 2 1 5 7 9 2 3 7 12 3 2 9 12 i/Vj 1 2 3 1,2 1,3 2,3 1,2,3 0 211 5 10 11 212 3 12 14 183 2 14 15 19三、算法偽代碼for (i =1;i<n;i+) /初始化第0列 di0=ci0;for( j=1;j<

8、;2(n-1)-1;j+) for(i=1 ; i<n ;i+) if(子集Vj中不包含i) 對(duì)Vj中的每個(gè)元素k，計(jì)算diVj = mincik + dkVj-k | 每一個(gè)kVj; 對(duì)V2(n-1)-1中的每個(gè)元素k,計(jì)算: d02(n-1)-1 = minc0k + dk2(n-1)-2; 輸出最短路徑:d02(n-1)-1; 廣義背包問(wèn)題源代碼：#include <iostream>#include <vector>#include <assert.h>#include <windows.h>#include <stdio.h

9、>#include <windef.h>#include <iostream>#include <assert.h>using namespace std;/*fim:前i件物品放入背包容量為m的背包獲得的最大收益fim = max(fi - 1m,fi - 1m - k * Wi + k * Vi,其中 1<=k<= m/Wi)邊界條件f0m = 0;fm0 = 0;*/const int N = 4;/四種物品const int M = 6;/背包的容積為6int weightN + 1 = 0, 1, 2, 3 ,4;/四種物品的重量

10、分別為1,2,3,4int ValueN + 1 = 0, 5, 10, 15,25 ;/四種物品的價(jià)值分別為5,10,20,25int fN + 1M + 1 = 0 ;/fim初始化為零int Completeknapsack()/邊界條件for (int i = 0; i <= N; i+)fi0 = 0;for (int m = 0; m <= M; m+)f0m = 0;/遞推for ( i = 1; i <= N; i+)for ( m = 1; m <= M; m+)fim = 0;int nCount = m / weighti;/背包最多能裝入的同種物品數(shù)量for (int k = 0