[理學(xué)]背包問(wèn)題詳解(已修改)
2024-10-31 01:09 本頁(yè)面
【正文】 1 動(dòng)態(tài)規(guī)劃系列之二 背包問(wèn)題 彭智朝 2 解空間 ? 設(shè) Xi表示第 i件物品的取舍， 1代表取， 0代表舍，搜索的空間為 n元一維數(shù)組（ X1,X2,X3,…… ，Xn） ,取值范圍為（ 0， 0， 0…… ， 0， 0），（ 0， 0， 0…… ， 0， 1），（ 0， 0， 0…… ， 1，0），（ 0， 0， 0…… ， 1， 1）， …… ，（ 1，1， 1…… ， 1， 1）。 3 解空間圖示 ? 以 3個(gè)物品為例 ,解 (0,1,0)表示 (不取物品 0,取物品 1,不取物品 2) root 0 1 0 1 0 1 0 1 0 4 01背包問(wèn)題 ? 問(wèn)題陳述： ? 給定 n種物品和一背包。物品 i的重量是 wi，其價(jià)值為 vi，背包的容量為 c。問(wèn)應(yīng)如何選擇裝入背包中的物品，使得裝入背包中物品的總價(jià)值最大？ ? 在選擇裝入背包的物品時(shí)，對(duì)每種物品 i只有兩種選擇，即裝入背包或不裝入背包。不能將物品 i裝入背包多次，也不能只裝入部分的物品 i。因此，該問(wèn)題稱為 01背包問(wèn)題。 ? ? 解題思路： ? 此問(wèn)題可轉(zhuǎn)化為：給定 c0， wi0， vi0， 1≤i≤n ，要求找出一個(gè) n元 01向量 (x1， x2， … ， xn)， xi∈{0 ， 1}， 1≤i≤n ，使得∑ wixi≤c ，而且 ∑ vixi達(dá)到最大。因此， 01背包是一個(gè)特殊的整數(shù)規(guī)劃問(wèn)題： ? max ∑vixi ? . ∑wixi≤c ， ? xi∈{0 ， 1}， 1≤i≤n ? 可用動(dòng)態(tài)規(guī)劃算法求解。 5 其他類型背包問(wèn)題 ? 完全背包問(wèn)題 (0/1)： ? 有 N種物品和一個(gè)容量為 V的背包，每種物品都有 無(wú)限 件可用。第 i種物品的費(fèi)用是 c[i]，價(jià)值是 w[i]。求解將哪些物品裝入背包可使這些物品的費(fèi)用總和不超過(guò)背包容量，且價(jià)值總和最大。 ? 多重背包問(wèn)題 ? 有 N種物品和一個(gè)容量為 V的背包。第 i種物品 最多有 n[i]件可用，每件費(fèi)用是 c[i]，價(jià)值是 w[i]。求解將哪些物品裝入背包可使這些物品的費(fèi)用總和不超過(guò)背包容量，且價(jià)值總和最大。 6 01背包問(wèn)題 設(shè)所給 01背包問(wèn)題的子問(wèn)題 ??nikkk xvm a x???????????nkixjxwknikkk},1,0{的最優(yōu)值為 m(i， j)，即 m(i， j)是背包容量為 j，可選擇物品為 i，i+1， … ， n時(shí) 01背包問(wèn)題的最優(yōu)值。由 01背包問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)，可以建立計(jì)算 m(i， j)的遞歸式如下。 iiiiwjwjjimvwjimjimjim????????????0),1(}),1(),1(m a x {),(nnnwjwjvjnm???????00),(算法復(fù)雜度分析： 從 m(i， j)的遞歸式容易看出，算法需要 O(nc)計(jì)算時(shí)間。當(dāng)背包容量 c很大時(shí)，算法需要的計(jì)算時(shí)間較多。例如，當(dāng) c2n時(shí)，算法需要 Ω(n2n)計(jì)算時(shí)間。 7 0/1背包問(wèn)題可以看作是決策一個(gè)序列 (x1, x2, …, xn)，對(duì)任一變量 xi的決策是決定 xi=1還是 xi=0。在對(duì) xi1決策后，已確定了(x1, …, xi1)，在決策 xi時(shí)，問(wèn)題處于下列兩種狀態(tài)之一： （ 1） 背包容量不足以裝入物品 i， 則 xi=0， 背包不增加價(jià)值； （ 2） 背包容量可以裝入物品 i， 則 xi=1， 背包的價(jià)值增加了 vi。 這兩種情況下背包價(jià)值的最大者應(yīng)該是 對(duì) xi決策后 的背包價(jià)值 。 令 V(i, j)表示在 前 i(1≤i≤n)個(gè)物品中能夠裝入容量為 j（ 1≤j≤C） 的背包中的物品的最大值 ， 則可以得到如下動(dòng)態(tài)規(guī)劃函數(shù)： 01背包問(wèn)題 8 01背包問(wèn)題 — 動(dòng)態(tài)規(guī)劃算法 ? void Knapsack(int *v, int *w, int c, int n, int ** m) ? { int j。 int jMax。 ? if(w[n]1c) jMax=c。 else jMax=w[n]1。 ? for (j = 0。 j = jMax 。j++) m[n][j] = 0。 ? for (j = w[n]。 j = c。 j++) m[n][j] = v[n] 。 ? for ( int i=n1。 i1。 i) ? { int jMax。 ? if(w[n]1c) jMax=c。 else jMax=w[n]1。 ? for (j = 0。 j = jMax。 j++) ? m[i][j] = m[i+1][j]。 ? for (j = w[i] 。 j = c。 j++) ? if(m[i+1][j] m[i+1][jw[i]] + v[i] ) m[i][j]=m[i+1][j]。 ? else m[i][j]=m[i+1][jw[i]] + v[i] 。 ? } ? m[1][c] =m[2][c]。 ? if (c = w[1]) m[1][c]=((m[1][c]m[2][cw[1]]+v[1])?m[1][c]:m[2][cw[1]]+v[1])。 ? } 9 根據(jù)動(dòng)態(tài)規(guī)劃函數(shù)，用一個(gè) (n+1) (C+1)的二維表 V， V[i][j]表示把前 i個(gè)物品裝入容量為 j的背包中獲得的最大價(jià)值。 例如，有 5個(gè)物品，其重量分別是 {2, 2, 6, 5, 4}，價(jià)值分別為 {6, 3, 5, 4, 6}，背包的容量為 10。 0 1 2 3 4 5 6 7 8 9 10 0 w1=2 v1=6 1 w2=2 v2=3 2 w3=6 v3=5 3 w4=5 v4=4 4 w5=4 v5=6 5 01背包問(wèn)題 — 動(dòng)態(tài)規(guī)劃算法舉例 10 0 1 2 3 4 5 6 7 8 9 10 0 0 0 0 0 0 0 0
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1