【文章內(nèi)容簡介】 (9， 10)， (10， 11)} q[2]=p[2]?(2， 6)={(2， 6)， (4， 9)， (6， 12)， (8， 15)} p[1]={(0， 0)， (2， 6)， (4， 9)， (6， 12)， (8， 15)} p[1]的最后的那個(gè)跳躍點(diǎn) (8,15)給出所求的最優(yōu)值為 m(1,c)=15。 17 上述算法的主要計(jì)算量在于計(jì)算跳躍點(diǎn)集p[i](1≤i≤n)。由于 q[i+1]=p[i+1]?(wi， vi)，故計(jì)算q[i+1]需要 O(|p[i+1]|)計(jì)算時(shí)間。合并 p[i+1]和q[i+1]并清除受控跳躍點(diǎn)也需要 O(|p[i+1]|)計(jì)算時(shí)間。從跳躍點(diǎn)集 p[i]的定義可以看出， p[i]中的跳躍點(diǎn)相應(yīng)于 xi,…,x n的 0/1賦值。因此， p[i]中跳躍點(diǎn)個(gè)數(shù)不超過 2ni+1。由此可見，算法計(jì)算跳躍點(diǎn)集 p[i]所花費(fèi)的計(jì)算時(shí)間為 從而，改進(jìn)后算法的計(jì)算時(shí)間復(fù)雜性為 O(2n)。當(dāng)所給物品的重量 wi(1≤i≤n)是整數(shù)時(shí)， |p[i]|≤c+1，(1≤i≤n)。在這種情況下，改進(jìn)后算法的計(jì)算時(shí)間復(fù)雜性為 O(min{nc,2n})。 算法復(fù)雜度分析 ? ?nniinniOOipO 22|]1[|22?????????????? ? ?????18 背包問題 — 貪心算法 本節(jié)著重討論可以用貪心算法求解的問題的一般特征。 對(duì)于一個(gè)具體的問題，怎么知道是否可用貪心算法解此問題，以及能否得到問題的最優(yōu)解呢 ?這個(gè)問題很難給予肯定的回答。 但是，從許多可以用貪心算法求解的問題中看到這類問題一般具有 2個(gè)重要的性質(zhì)：貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。 19 貪心算法的基本要素 貪心選擇性質(zhì) 所謂 貪心選擇性質(zhì) 是指所求問題的 整體最優(yōu)解 可以通過一系列 局部最優(yōu) 的選擇，即貪心選擇來達(dá)到。這是貪心算法可行的第一個(gè)基本要素，也是貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別。 動(dòng)態(tài)規(guī)劃算法通常以 自底向上 的方式解各子問題，而貪心算法則通常以 自頂向下 的方式進(jìn)行，以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問題簡化為規(guī)模更小的子問題。 對(duì)于一個(gè)具體問題，要確定它是否具有貪心選擇性質(zhì)，必須證明每一步所作的貪心選擇最終導(dǎo)致問題的整體最優(yōu)解。 20 貪心算法的基本要素 當(dāng)一個(gè)問題的最優(yōu)解包含其子問題的最優(yōu)解時(shí)，稱此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可用動(dòng)態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征。 最優(yōu)子結(jié)構(gòu)性質(zhì) 21 背包問題 — 貪心算法 貪心算法和動(dòng)態(tài)規(guī)劃算法都要求問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，這是 2類算法的一個(gè)共同點(diǎn)。但是，對(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ī)劃算法的主要差別。 貪心算法與動(dòng)態(tài)規(guī)劃算法的差異 22 背包問題 — 貪心算法 ? 01背包問題： 給定 n種物品和一個(gè)背包。物品 i的重量是 Wi，其價(jià)值為 Vi，背包的容量為 C。應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大 ? 在選擇裝入背包的物品時(shí)，對(duì)每種物品 i只有 2種選擇，即裝入背包或不裝入背包。不能將物品 i裝入背包多次，也不能只裝入部分的物品 i。 23 背包問題 — 貪心算法 ? 背包問題： 與 01背包問題類似，所不同的是在選擇物品 i裝入背包時(shí)，可以選擇物品 i的一部分，而不一定要全部裝入背包， 1≤i≤n 。 這 2類問題都具有 最優(yōu)子結(jié)構(gòu) 性質(zhì)，極為相似，但背包問題可以用貪心算法求解，而 01背包問題卻不能用貪心算法求解。 24 背包問題 — 貪心算法 首先計(jì)算每種物品單位重量的價(jià)值 Vi/Wi，然后，依貪心選擇策略，將盡可能多的單位重量價(jià)值最高的物品裝入背包。若將這種物品全部裝入背包后，背包內(nèi)的物品總重量未超過 C，則選擇單位重量價(jià)值次高的物品并盡可能多地裝入背包。依此策略一直地進(jìn)行下去，直到背包裝滿為止。 具體算法可描述如下頁： 用貪心算法解背包問題的基本步驟： 25 背包問題 — 貪心算法 ? void Knapsack(int n,float M,float v[],float w[],float x[]) ? { Sort(n,v,w)。 ? int i。 ? for (i=1。i=n。i++) x[i]=0。 ? float c=M。 ? for (i=1。i=n。i++) { ? if (w[i]c) break。 ? x[i]=1。 ? c=w[i]。 ? } ? if (i=n) x[i]=c/w[i]。 ? } 算法 knapsack的主要計(jì)算時(shí)間在于將各種物品依其單位重量的價(jià)值從大到小排序。因此，算法的計(jì)算時(shí)間上界為 O（ nlogn）。 為了證明算法的正確性，還必須證明背包問題具有貪心選擇性質(zhì) 。 26 ? 對(duì)于 01背包問題，貪心選擇之所以不能得到最優(yōu)解是因?yàn)樵谶@種情況下，它無法保證最終能將背包裝滿，部分閑置的背包空間使每公斤背包空間的價(jià)值降低了。事實(shí)上，在考慮 01背包問題時(shí)，應(yīng)比較選擇該物品和不選擇該物品所導(dǎo)致的最終方案，然后再作出最好選擇。由此就導(dǎo)出許多互相重疊的子問題。這正是該問題可用動(dòng)態(tài)規(guī)劃算法求解的另一重要特征。 ? 實(shí)際上也是如此，動(dòng)態(tài)規(guī)劃算法的確可以有效地解 01背包問題。 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à)值降低了。事實(shí)上，在考慮 01背包問題時(shí)，應(yīng)比較選擇該物品和不選擇該物品所導(dǎo)致的最終方案，然后再作出最好選擇。由此就導(dǎo)出許多互相重疊的子問題。這正是該問題可用動(dòng)態(tài)規(guī)劃算法求解的另一重要特征。 實(shí)際上也是如此，動(dòng)態(tài)規(guī)劃算法的確可以有效地解 01背包問題。 28 ? 有許多問題，當(dāng)需要找出它的解集或者要求回答什么解是滿足某些約束條件的最佳解時(shí)，往往要使用回溯法。 ? 回溯法的基本做法是搜索，或是一種組織得井井有條的，能避免不必要搜索的窮舉式搜索法。這種方法適用于解一些組合數(shù)相當(dāng)大的問題。 ? 回溯法在問題的解空間樹中，按深度優(yōu)先策略，從根結(jié)點(diǎn)