【正文】 c。 i1。 else jMax=w[n]1。當(dāng)背包容量 c很大時(shí)，算法需要的計(jì)算時(shí)間較多。第 i種物品的費(fèi)用是 c[i]，價(jià)值是 w[i]。 3 解空間圖示 ? 以 3個(gè)物品為例 ,解 (0,1,0)表示 (不取物品 0,取物品 1,不取物品 2) root 0 1 0 1 0 1 0 1 0 4 01背包問題 ? 問題陳述： ? 給定 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á)到最大。 6 01背包問題 設(shè)所給 01背包問題的子問題 ??nikkk xvm a x???????????nkixjxwknikkk},1,0{的最優(yōu)值為 m(i， j)，即 m(i， j)是背包容量為 j，可選擇物品為 i，i+1， … ， n時(shí) 01背包問題的最優(yōu)值。 令 V(i, j)表示在 前 i(1≤i≤n)個(gè)物品中能夠裝入容量為 j（ 1≤j≤C） 的背包中的物品的最大值 ， 則可以得到如下動(dòng)態(tài)規(guī)劃函數(shù)： 01背包問題 8 01背包問題 — 動(dòng)態(tài)規(guī)劃算法 ? void Knapsack(int *v, int *w, int c, int n, int ** m) ? { int j。 j = c。 j = jMax。 ? } 9 根據(jù)動(dòng)態(tài)規(guī)劃函數(shù)，用一個(gè) (n+1) (C+1)的二維表 V， V[i][j]表示把前 i個(gè)物品裝入容量為 j的背包中獲得的最大價(jià)值。 ? c=w[i]。 14 一個(gè)例子 n=3， c=6， w={4， 3， 2}， v={5， 2， 1}。 初始時(shí) p[6]={(0,0)}， (w5,v5)=(4,6)。合并 p[i+1]和q[i+1]并清除受控跳躍點(diǎn)也需要 O(|p[i+1]|)計(jì)算時(shí)間。 但是，從許多可以用貪心算法求解的問題中看到這類問題一般具有 2個(gè)重要的性質(zhì)：貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。但是，對(duì)于具有最優(yōu)子結(jié)構(gòu)的問題應(yīng)該選用貪心算法還是動(dòng)態(tài)規(guī)劃算法求解 ?是否能用動(dòng)態(tài)規(guī)劃算法求解的問題也能用貪心算法求解 ?下面研究 2個(gè)經(jīng)典的組合優(yōu)化問題，并以此說明貪心算法與動(dòng)態(tài)規(guī)劃算法的主要差別。若將這種物品全部裝入背包后，背包內(nèi)的物品總重量未超過 C，則選擇單位重量?jī)r(jià)值次高的物品并盡可能多地裝入背包。 ? for (i=1。 為了證明算法的正確性，還必須證明背包問題具有貪心選擇性質(zhì) 。由此就導(dǎo)出許多互相重疊的子問題。如果肯定不包含，則跳過對(duì)該結(jié)點(diǎn)為根的子樹的搜索，逐層向其祖先結(jié)點(diǎn)回溯；否則，進(jìn)入該子樹，繼續(xù)按深度優(yōu)先策略搜索。否則將右子樹剪去。 32 01背包問題 — 回溯法 ? 在實(shí)現(xiàn)時(shí)，由函數(shù) Bound來計(jì)算在當(dāng)前結(jié)點(diǎn)處的上界。在通常情況下，排序算法將待排序元素從小到大排列。//物品價(jià)值數(shù)組 Typew cw。j++) bestx[j]=x[j]。 cp=p[i]。 b += p[i]。 }。 Q[i1].d=*p[i]/w[i]。jn。 = new int[n+1]。 =0。 delete [] ?；罱Y(jié)點(diǎn)一旦成為擴(kuò)展結(jié)點(diǎn)，就一次性產(chǎn)生其所有兒子結(jié)點(diǎn)。 算法首先檢查當(dāng)前擴(kuò)展結(jié)點(diǎn)的左兒子結(jié)點(diǎn)的可行性。 //p[i]表示 i的價(jià)值 i++。 // 取下一個(gè)擴(kuò)展節(jié)點(diǎn) （ 略 ） } 分支限界搜索過程 。 // 裝填剩余容量裝滿背包 return b。當(dāng)前擴(kuò)展結(jié)點(diǎn)的右兒子結(jié)點(diǎn)一定是可行結(jié)點(diǎn)，僅當(dāng)右兒子結(jié)點(diǎn)滿足上界約束時(shí)才將它加入子集樹和活結(jié)點(diǎn)優(yōu)先隊(duì)列。 40 01背包問題 — 分支限界法 常見的兩種分支限界法 （ 1）隊(duì)列式 (FIFO)分支限界法 按照隊(duì)列先進(jìn)先出（ FIFO） 原則選取下一個(gè)節(jié)點(diǎn)為擴(kuò)展節(jié)點(diǎn)。 } 38 01背包問題 — 分支限界法 分支限界法與回溯法 （ 1）求解目標(biāo)：回溯法的求解目標(biāo)是找出解空間樹中滿足約束條件的所有解，而分支限界法的求解目標(biāo)則是找出滿足約束條件的一個(gè)解，或是在滿足約束條件的解中找出在某種意義下的最優(yōu)解。 =n。 [0]=0。Q[i].d=Q[j].d。 W+=w[i]。 Typep P=0。 } // 裝滿背包 if (i = n) b += p[i]/w[i] * cleft。 Backtrack(i+1)。} return。//當(dāng)前價(jià)值 Typep bestp。 private: Typep Bound(int i)。 Knap的其他成員記錄解空間樹中的結(jié)點(diǎn)信息，以減少函數(shù)參數(shù)的傳遞以及遞歸調(diào)用時(shí)所需的?？臻g。這 4個(gè)物品的單位重量?jī)r(jià)值分別為「 3,2,4]。 ?顯約束：對(duì)分量 xi的取值限定。 實(shí)際上也是如此，動(dòng)態(tài)規(guī)劃算法的確可以有效地解 01背包問題。事實(shí)上，在考慮 01背包問題時(shí)，應(yīng)比較選擇該物品和不選擇該物品所導(dǎo)致的最終方案，然后再作出最好選擇。i++) { ? if (w[i]c) break。 具體算法可描述如下頁： 用貪心算法解背包問題的基本步驟： 25 背包問題 — 貪心算法 ? void Knapsack(int n,float M,float v[],float w[],float x[]) ? { Sort(n,v,w)。物品 i的重量是 Wi，其價(jià)值為 Vi，背包的容量為 C。這是貪心算法可行的第一個(gè)基本要素，也是貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別。因此， p[i]中跳躍點(diǎn)個(gè)數(shù)不超過 2ni+1。 p[5]={(0,0),(4,6)}。因此，函數(shù) m(i,j)的全部跳躍點(diǎn)包含于函數(shù) m(i+1，j)的跳躍點(diǎn)集 p[i+1]與函數(shù) m(i+1， jwi)+vi的跳躍點(diǎn)集 q[i+1]的并集中。 ? } 01背包問題 — 動(dòng)態(tài)規(guī)劃算法 13 算法改進(jìn) 由 m(i,j)的遞歸式容易證明，在一般情況下，對(duì)每一個(gè)確定的i(1≤i≤n)，函數(shù) m(i,j)是關(guān)于變量 j的階梯狀單調(diào)不減函數(shù)。 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