【正文】 點(diǎn)，返回到 A ? A沒有可擴(kuò)展結(jié)點(diǎn)，成為死結(jié)點(diǎn)，算法結(jié)束，最優(yōu)解 X=(0,1,1)，最優(yōu)值 V=50 A Cr=C=30， V=0 B w1=16， v1=45 Cr=14， V=45 C Cr=30， V=0 D Crw2 不可行解 J Crw3 不可行解 K Cr=14 V=45 x=(1,0,0) H I E Cr=14 V=45 L w3=15， v3=25 Cr=0， V=50 5045 x=(0,1,1) F w2=15， v2=25 Cr=15， V=25 M 2550 不是 最優(yōu) 解 31 01背包問題 — 回溯法 ?解空間：子集樹 ?可行性約束函數(shù)： ?上界函數(shù)： 11 cxwniii ??? 0— 1背包問題是一個(gè)子集選取問題，適合于用子集樹表示 0— 1背包問題的解空間。 ?解空間：對(duì)于問題的一個(gè)實(shí)例，解向量滿足顯式約束條件的所有多元組，構(gòu)成了該實(shí)例的一個(gè)解空間。 ?顯約束：對(duì)分量 xi的取值限定。如果肯定不包含，則跳過對(duì)該結(jié)點(diǎn)為根的子樹的搜索，逐層向其祖先結(jié)點(diǎn)回溯；否則，進(jìn)入該子樹，繼續(xù)按深度優(yōu)先策略搜索。 ? 回溯法在問題的解空間樹中，按深度優(yōu)先策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹。 ? 回溯法的基本做法是搜索，或是一種組織得井井有條的，能避免不必要搜索的窮舉式搜索法。 實(shí)際上也是如此，動(dòng)態(tài)規(guī)劃算法的確可以有效地解 01背包問題。由此就導(dǎo)出許多互相重疊的子問題。 10 20 30 50 1.￥ 60 2.￥ 100 3.￥ 120 =￥ 220 =￥ 160 =￥ 180 =￥ 240 100 20 120 30 60 10 100 20 60 10 120 30 60 10 100 20 80 20 120 —— 20 30 01背包問題的例子 背包問題 — 貪心算法 27 背包問題 — 貪心算法 對(duì)于 01背包問題，貪心選擇之所以不能得到最優(yōu)解是因?yàn)樵谶@種情況下，它無法保證最終能將背包裝滿，部分閑置的背包空間使每公斤背包空間的價(jià)值降低了。這正是該問題可用動(dòng)態(tài)規(guī)劃算法求解的另一重要特征。事實(shí)上，在考慮 01背包問題時(shí)，應(yīng)比較選擇該物品和不選擇該物品所導(dǎo)致的最終方案，然后再作出最好選擇。 為了證明算法的正確性，還必須證明背包問題具有貪心選擇性質(zhì) 。 ? } 算法 knapsack的主要計(jì)算時(shí)間在于將各種物品依其單位重量的價(jià)值從大到小排序。 ? c=w[i]。i++) { ? if (w[i]c) break。 ? for (i=1。i++) x[i]=0。 ? for (i=1。 具體算法可描述如下頁： 用貪心算法解背包問題的基本步驟： 25 背包問題 — 貪心算法 ? void Knapsack(int n,float M,float v[],float w[],float x[]) ? { Sort(n,v,w)。若將這種物品全部裝入背包后，背包內(nèi)的物品總重量未超過 C，則選擇單位重量價(jià)值次高的物品并盡可能多地裝入背包。 這 2類問題都具有 最優(yōu)子結(jié)構(gòu) 性質(zhì)，極為相似，但背包問題可以用貪心算法求解，而 01背包問題卻不能用貪心算法求解。不能將物品 i裝入背包多次，也不能只裝入部分的物品 i。物品 i的重量是 Wi，其價(jià)值為 Vi，背包的容量為 C。但是，對(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ī)劃算法的主要差別。問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可用動(dòng)態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征。 對(duì)于一個(gè)具體問題，要確定它是否具有貪心選擇性質(zhì)，必須證明每一步所作的貪心選擇最終導(dǎo)致問題的整體最優(yōu)解。這是貪心算法可行的第一個(gè)基本要素，也是貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別。 但是，從許多可以用貪心算法求解的問題中看到這類問題一般具有 2個(gè)重要的性質(zhì)：貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。 算法復(fù)雜度分析 ? ?nniinniOOipO 22|]1[|22?????????????? ? ?????18 背包問題 — 貪心算法 本節(jié)著重討論可以用貪心算法求解的問題的一般特征。當(dāng)所給物品的重量 wi(1≤i≤n)是整數(shù)時(shí)， |p[i]|≤c+1，(1≤i≤n)。因此， p[i]中跳躍點(diǎn)個(gè)數(shù)不超過 2ni+1。合并 p[i+1]和q[i+1]并清除受控跳躍點(diǎn)也需要 O(|p[i+1]|)計(jì)算時(shí)間。 17 上述算法的主要計(jì)算量在于計(jì)算跳躍點(diǎn)集p[i](1≤i≤n)。從跳躍點(diǎn)集 p[5]與 q[5]的并集p[5]?q[5]={(0,0),(4,6),(5,4),(9,10)}中看到跳躍點(diǎn) (5,4)受控于跳躍點(diǎn) (4,6)。 p[5]={(0,0),(4,6)}。 初始時(shí) p[6]={(0,0)}， (w5,v5)=(4,6)。 ? 由此可見，在遞歸地由表 p[i+1]計(jì)算表 p[i]時(shí)，可先由 p[i+1]計(jì)算出 q[i+1]，然后合并表 p[i+1]和表 q[i+1]，并清除其中的受控跳躍點(diǎn)得到表 p[i]。因此，容易由 p[i+1]確定跳躍點(diǎn)集 q[i+1]如下q[i+1]=p[i+1]?(wi,vi)={(j+wi,m(i,j)+vi)|(j,m(i,j))?p[i+1]} ? 另一方面，設(shè) (a， b)和 (c， d)是 p[i+1]?q[i+1]中的 2個(gè)跳躍點(diǎn)，則當(dāng) c?a且 db時(shí)， (c， d)受控于 (a， b)，從而 (c， d)不是p[i]中的跳躍點(diǎn)。因此，函數(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]的并集中。 14 一個(gè)例子 n=3， c=6， w={4， 3， 2}， v={5， 2， 1}。 對(duì)每一個(gè)確定的 i(1≤i≤n)，用一個(gè)表 p[i]存儲(chǔ)函數(shù) m(i， j)的全部跳躍點(diǎn)。在一般情況下，函數(shù) m(i,j)由其全部跳躍點(diǎn)唯一確定。 ? } 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ù)。 ? c=w[i]。 i++) ? if (m[i][c]==m[i+1][c]) ? x[i]=0。 11 x5=1 x4=0 x3=0 x2=1 x1=1 0 1 2 3 4 5 6 7 8 9 10 0 0 0 0 0