【正文】 t {return uprofit。 //左兒子結(jié)點(diǎn)標(biāo)志 }。 private: bbnode *parent。 class bbnode{ friend Knapint,int。//單位重量?jī)r(jià)值 }。} private: int ID。 則 主要 算法描述為： class Object{ friend int Knapsack(int *,int *,int,int,int *)。由于需要不斷地利用收益密度來排序，物品的索引值會(huì)隨之變化，因此必須將函數(shù)所生成的結(jié)果映射回初始時(shí)的物品索引。 01 背包問題的最大收益分枝定界算法可以使用定界 函數(shù)來計(jì)算活結(jié)點(diǎn)的收益上限 upprofit，使得以活結(jié)點(diǎn)為根的子樹中的任一結(jié)點(diǎn)的收益值都不可能超過 upprofit，活結(jié)點(diǎn)的最大堆使用 upprofit作為關(guān)鍵值域。 13 01 背包問題的實(shí)現(xiàn) 工作在解空間樹上的 FIFO 分枝定界方法非常類似于從根結(jié)點(diǎn)出發(fā)的寬度優(yōu)先搜索。 ② 最小耗費(fèi)或最大收益法在這種模式中，每個(gè)結(jié)點(diǎn)都有一個(gè)對(duì)應(yīng)的耗費(fèi)或收益。從活結(jié)點(diǎn)表中取出所選擇的結(jié)點(diǎn)并進(jìn)行擴(kuò)充，直到找到解或活動(dòng)表為空，擴(kuò)充才結(jié)束。當(dāng)一個(gè)結(jié)點(diǎn)變?yōu)?E結(jié)點(diǎn)時(shí)，則生成從該結(jié)點(diǎn)移動(dòng)一步即可到達(dá)的所有新結(jié)點(diǎn)。 01 背包問題在 分枝 限界法 中的實(shí)現(xiàn) 分枝 限界法 的基本原理與分析 分枝限界 發(fā) 是另一種系統(tǒng)地搜索解空間的方法，它與回溯法的主要區(qū)別在于對(duì) E結(jié)點(diǎn) (expansion node)的擴(kuò)充方式。 回溯算法的運(yùn)行時(shí)間取決于它在搜索過程中所生成的結(jié)點(diǎn)數(shù) ,而限界函數(shù)可以大量減少所生成的結(jié)點(diǎn)個(gè)數(shù) ,省去許多無謂的搜索 , 使得搜索速度更快 ,其調(diào)用限界函數(shù)計(jì)算上界需花費(fèi) O(n)時(shí)間 ,最壞情況下有 O( n2 )個(gè)結(jié)點(diǎn)需調(diào)用限界函數(shù) ,需花費(fèi) O(n)時(shí)間 ,所以該算法的時(shí)間復(fù)雜度為 O(n n2 )[12]。 }[1] ③ 算法效 率 由于計(jì)算上界函數(shù)需要 O(n)時(shí)間 ，在最壞情況下有 O( n2 )個(gè)右孩子結(jié)點(diǎn)需要上界函數(shù)，故計(jì)算 01背包問題的回溯算法所需的計(jì)算時(shí)間復(fù)雜度為 O(nn2 )。 delete[]。 delete[]Q。 =0。 =c。 } =0。i++){ [i]=p[Q[i1].ID]。 for (int i=1。 =new Typep[n+1]。//裝入所有物品 //依物品單位重量?jī)r(jià)值排序 sort(Q,n)。 w+=w[i]。 Q[i1].d=*p[i]/w[i]。i=n。 Object*Q=new Object[n]。 templateclass Typew,class Typep Typep Knapsack(Typep p[], Typep w[],Typew c,int n) { //為 Knap::Backtrack 初始化 Typew W=0。 float d。 int operator=(Object a) const {return(d=)。 } class Object { friend int Knapsack(int*,int *,int,int)。 } //裝滿背包 if(i=n)b+=p[i]* cleft/w[i]。 b+=p[i]。amp。 //剩余容量 Typep b=cp。 if(Bound(i+1)bestp) //進(jìn)入右子數(shù) Backtrack(i+1)。 cw=w[i]。 cp+=p[i]。 return。 //當(dāng)前最優(yōu)價(jià)值 }。 //當(dāng)前重量 Typep cp。 //物品重量數(shù)組 Typep*p。 //背包容量 int n。 void Backtrack(int i)。 ② 解 01背包問題的回溯算法描述如下 ： templateclass Typew,class Typep class Knap{ friend Typep Knapsack(Typep*,Typew*,Typew,int)。一種決定是否要移動(dòng)到右子樹的簡(jiǎn)單方法是r為還未遍歷的對(duì)象的收益之和，將 r加到 cp (當(dāng)前節(jié)點(diǎn)所獲收益 )之上，若 ( r+cp) 9 ? bestp(目前最優(yōu)解的收益 )，則不 需 搜索右子樹。改進(jìn)后的代碼可找到獲得最大收益時(shí)包 含在背包中的對(duì)象的集合 。首先形成一個(gè)遞歸算法，去找到可獲得的最大收益。為了實(shí)現(xiàn)回溯，首先需要為問題定義一個(gè)解空間，這個(gè)解空間必須至少包含問題的一個(gè)解 (可能是最優(yōu)的 )。一旦定義了解空間的組織方法， 這個(gè)空間即可按照深度優(yōu)先的方法從開始結(jié)點(diǎn)進(jìn)行搜索，利用限界函數(shù)避免移動(dòng)到不可能產(chǎn)生解的子空間。 下一步是組織解空間以便它能被容易地搜索。 回溯法需要為問題定義一個(gè)解空間，這個(gè)解空間必須至少包含問題的一個(gè)解 (可能是最優(yōu)的 )。 01 背包問題在 回溯法 中的實(shí)現(xiàn) 回溯法 的基本原理與分析 回溯是一種系統(tǒng)地搜索問題解答的方法 。 }[1] 8 ④ 計(jì)算復(fù)雜性分析 利用動(dòng)態(tài)規(guī)劃求解 01 背包問題的復(fù)雜度為 0(min{nc,2n}。c= w[i]。i++) if(m[i][c]==m[i+1][c]) x[i]=0。 } templateclass Type void Traceback(Type* * m,int w,int c,int n,int x) { for (int i=1。 } m[1][c]=m[2][c]。j=c。j++)m[i][j]=m[i+1][j]。 for (int j=0。i1。j++)m[n][j]=v[n]。 for (int j=w[n]。j=jMax。由 01 背包問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，可以建立計(jì)算m(i,j)的遞歸式如下： ??? ??? ?????? wjjjim wijviwijimjim 0),1( },),1(),),1(m a x{j)m (i , ??? ?? ?? wnj wnvnj0j)m (n, ③ 算法描述 基于以上討論，當(dāng) wi(1? i? n)為正整數(shù)時(shí)，用二維數(shù)組 m[][]來存儲(chǔ) m(i,j)的相應(yīng)值，可設(shè)計(jì)解 01背包問題的動(dòng)態(tài)規(guī)劃算法 Knapsack 入下： 7 templateclass Type void Knapsack(Type v,int w,int c,int n,Type* * m) { int jMax=min(w[n]1,c)。此為矛盾 [1]。設(shè) (y1， y2? yn)是所給 01背包問題的一個(gè)最優(yōu)解，則 (y2， y3? yn)是下面相應(yīng)子問題的一個(gè)最優(yōu)解： ??nik kkxvmax 6 ??????????? nkixjxwknik kk},1,0{ 因若不然 ，設(shè) (z2， z3? zn)是上述問題的一個(gè)最優(yōu)解，而 (y2， y3? yn)不是它的最優(yōu)解，由此可見 ???ni 2 ??ni iiyv2,且 ???ni iizw2w1y1? c。因此，在設(shè)計(jì) 01背包問題解決方案時(shí)，可以將整個(gè)物品放到背包的過程，看成一個(gè)取物品的過程。 動(dòng)態(tài)規(guī)劃算法的每一步?jīng)Q策都是根據(jù)前一步的 狀態(tài)參量來決定這一步狀態(tài)參量的設(shè)置，也就是說，從初始狀態(tài)到最終狀態(tài)要經(jīng)過多個(gè)過程 ，經(jīng)歷不同的狀態(tài)，不斷地根據(jù)上一步狀態(tài)決定下一狀態(tài)，從而形成了一個(gè)決策序列，最終將整個(gè)問題解決，這就是典型的多段決策的特性。前一子問題為后面子問題提供信息，而減少計(jì)算量，最后一個(gè)子問題的解即為問題解。如果能夠保存已解決的子問題的答案，而在需要時(shí)再找出已求得的答案，就可以 避免大量重復(fù)計(jì)算，從而得到多項(xiàng)式時(shí)間算法。 但是經(jīng)分解得到的子問題往往不是互相獨(dú)立的。 ② 問題符號(hào) 化 01 背包問題的符號(hào)化表示是，給定 M0， w i 0， pi 0， 1? i? n ，要求找到一個(gè) n 元 01向量向量 (x1， x2? xn)， X i =0 或 1 , 1? i? n, 使得 Mwx ii ?? ，而且 px ii? 達(dá)到最大[2]。不能將 物品 i 裝人背包多次， 也不能只 裝入部分的物品 i。物品 i 的重量是 wi，其價(jià)值為 pi，背包的容量為 M。滿足約束條件的任何向量都是一個(gè)可行解，而使得目標(biāo)函數(shù)達(dá)到最大的那個(gè)可行解則為最優(yōu)解 [1]。 問題的一般描述是：旅行者背包登山，背包的最大承重為 M，現(xiàn)有 n 個(gè)物品可供選擇裝入背包，第 i 個(gè)物品鶯量為 wi，價(jià)值為 pi，假定物品 i 的一部分xi(0? xi ? 1)放人背包，獲得價(jià)值為 xipi，由于背包最大承重為 M，要求裝入物品總質(zhì)量不過超過 M，問旅行者應(yīng)該如何選擇物品裝入背包，使得裝入物品的價(jià)值總和達(dá)到最大值。 背包問題 的描 述 背包問題是整數(shù)規(guī)劃中的一類特殊問題，在現(xiàn)實(shí)生活中具有廣泛應(yīng)用 。 在計(jì)算理論中屬于 NPC 完全問題，其計(jì)算復(fù)雜度 ， 傳統(tǒng)上采用動(dòng)態(tài)規(guī)劃來求解。 他是 最基本的背包問題，即對(duì)一個(gè)物體要么選用，要么就拋棄，不能將一個(gè)物體再繼續(xù)細(xì)分的情況。 01 背包問題的算法研究的分析 01 背包問題的算法研究 主要是通過 算法設(shè)計(jì)與分析知識(shí)，設(shè)計(jì)解決相關(guān)問題的盡可能高效的算法并程序?qū)崿F(xiàn)，而且能夠分析算法的復(fù)雜性，通過實(shí)驗(yàn)進(jìn)一步領(lǐng)會(huì)各種算法