算法分析與設(shè)計(jì)論文-背包問題的算法設(shè)計(jì)策略對(duì)比與分析-資料下載頁
2025-06-04 10:51本頁面
【正文】 c[i][j]數(shù)組保存了 1,2,3 號(hào)物品依次選擇后的最大價(jià)值 。 這個(gè)最大價(jià)值是怎么得來的呢 ?從背包容量為 0開始 ,1號(hào)物品先試 ,0,1,2,的容量都不能放 .所以置 0,背包容量為 3 則里面放 ,這一排背包容量為 4,5,6,....10 的時(shí)候，最佳方案都是放 1 號(hào)物品放入背包 .則再看 2 號(hào)物品 .當(dāng)背包容量為 3 的時(shí)候，最佳方案還是上一排的最價(jià)方案 c 為 5 的時(shí)候，則最佳方案為自己的重量 7 的時(shí)候，很顯然是 5 加上一個(gè)值了。加誰 ??很顯然是 74=3 的時(shí)候 .上一排 c3 的最佳方案是 。總的最佳 方案是 5+4 為 .一排一排推下去。最右下放的數(shù)據(jù)就是最大的價(jià)值了。 (注意第 3 排的背包容量為 7 的時(shí)候 ,最佳方案不是本身的 3 號(hào)物品沒有被選 .選的是 1,2 號(hào)物品 .所以得 9。 從以上最大價(jià)值的構(gòu)造過程中可以看出。 f(n,m)=max{f(n1,m), f(n1,mw[n])+P(n,m)}這就是書本上寫的動(dòng)態(tài)規(guī)劃方程 . 回溯法 用回溯法求解 01背包問題的算法思路是按照物品的單位價(jià)值從大到小排序 ,計(jì)算當(dāng)前節(jié)點(diǎn)的上界 ,搜索左子樹。只有當(dāng)右子樹包含可行解時(shí)才搜索右子樹。剪去右子樹的條件是當(dāng)前價(jià)值加上剩余物品的總價(jià)值小于當(dāng)前的最優(yōu)總價(jià)值時(shí) ,不需搜索右子樹 ,可將右子樹剪去。 回溯法用一定的剪枝進(jìn)行優(yōu)化 ,算法的時(shí)間復(fù)雜度為 O ( n3 2n ) , n 為物品個(gè)數(shù)。 貪心算法 在求解 01背包問題時(shí) ,對(duì)貪心算法可以使用一些策略 , 使其得到的解更接近最優(yōu)解。具體方案如下 : (1) 價(jià)值優(yōu)先策略 :從剩余的物品中 ,選取價(jià)值最大的可以裝入背包的物品。此時(shí) ,價(jià)值最大的優(yōu)先被裝入背包 ,然后裝入下一個(gè)價(jià)值最大的物品 ,直到不能再裝入剩下的物品為止。 (2) 重量優(yōu)先策略 :從剩余的物品中選 取重量最小的物品裝入背包中 ,這種策略一般不能得到最優(yōu)解。 (3) 單位價(jià)值優(yōu)先策略 :根據(jù)價(jià)值 /重量的比值 ,按照每一次選取剩下的物品中比值最大的物品裝入背包 ,直到不能再裝入為止。 以上三種策略都不能保證得到最優(yōu)解 ,但三種策略相比較而言 ,第三種策略與最優(yōu)解相差較小。如果可以選擇物品的一部分 ,用單位價(jià)值策略可以保證得到最優(yōu)解。 在貪心算法時(shí)間復(fù)雜度的估算中 ,由于需要對(duì)重量或價(jià)值或兩者的比值進(jìn)行排序，所以貪心算法的時(shí)間復(fù)雜度為 O(n*logn)。 分支限界法 在解 01 背包問題的優(yōu)先隊(duì)列式分支限界法中，活結(jié)點(diǎn) 優(yōu)先隊(duì)列中結(jié)點(diǎn)元素N 的優(yōu)先級(jí)由該結(jié)點(diǎn)的上界函數(shù) Bound 計(jì)算出的值 uprofit 給出。子集樹中以結(jié)點(diǎn) N 為根的子樹中任一結(jié)點(diǎn)的價(jià)值不超過 。可用一個(gè)最大堆來實(shí)現(xiàn)活結(jié)點(diǎn)優(yōu)先隊(duì)列。堆中元素類型為 HeapNode，其私有成員有 uprofit,profit,weight 和 level。對(duì)于任意活結(jié)點(diǎn) N， 是結(jié)點(diǎn) N 所相應(yīng)的重量； 是 N 所相應(yīng)的價(jià)值； 是結(jié)點(diǎn) N 的價(jià)值上界，最大堆以這個(gè)值作為優(yōu)先級(jí)。子集空間樹中結(jié)點(diǎn)類型為 bbnode。 3 算法比較 以上方法對(duì)背包問題 的求解各有其優(yōu)缺點(diǎn)，如表 31 所示。 表 31 求解背包問題的算法比較 算法名稱 時(shí)間復(fù)雜度 優(yōu)點(diǎn) 缺點(diǎn) 改進(jìn) 回溯法 O(n*2n ) 優(yōu)解 速度慢 剪枝 動(dòng)態(tài)規(guī)劃 O(n*m) 最優(yōu)解 速度慢 遞歸方程求解 貪心算法 O(n*logn) 速度快 不一定是最優(yōu)解 啟發(fā)式方法 分支限界法 O(n*2n) 最優(yōu)解 速度慢 01背包問題是一個(gè)經(jīng)典的 NP問題。對(duì)于規(guī)模過大的 01背包問題，人們還是無法找到完美的求解方法。所有智能算法都有其局限性，只能在一定范圍內(nèi)求解。由于各種算法都有其自身的優(yōu)缺點(diǎn)，許 多學(xué)者通過利用一種算法的優(yōu)點(diǎn)同時(shí)結(jié)合其他算法避免該算法的不足，出現(xiàn)了混合算法，這樣就取得了很大的成功。 01背包問題未來的發(fā)展趨勢(shì)是繼續(xù)研究結(jié)合多種算法的混合優(yōu)化算法；通過其他學(xué)科的算法得到啟發(fā)，提出一種新的算法，繼而推動(dòng) 01背包問題的研究。 4 總結(jié) 在寫論文的過程中，我上網(wǎng)查詢了很多資料，并且也參考了書本里的內(nèi)容，通過這些我對(duì)算法分析設(shè)計(jì)又有了進(jìn)一步的了解，對(duì)算法的復(fù)雜度也有了新的認(rèn)識(shí)。對(duì)于我們常用的動(dòng)態(tài)規(guī)劃算法、回溯法、分支限界法、貪心算法等的思想有了進(jìn)一步的了解，我相信這對(duì)我以后的學(xué)習(xí)是非常有用 的。雖然這門課程已經(jīng)結(jié)束了，但是我所掌握的卻很少，因此在接下來的時(shí)間里我還會(huì)繼續(xù)學(xué)習(xí)算法分析與設(shè)計(jì)，從而能夠運(yùn)用這些算法解決更多的問題。 參考文獻(xiàn) : [ 1 ]王曉東 .計(jì)算機(jī)算法設(shè)計(jì)與分析（第 3版） 電子工業(yè)出版社 , 2021. [ 2 ]應(yīng)莉 01背包問題及其算法 計(jì)算機(jī)與現(xiàn)代化 （ 2021）06002403 [ 3 ]徐穎 回溯法在 01背包問題中的應(yīng)用 軟件導(dǎo)刊（ 2021）1200540
畢業(yè)設(shè)計(jì)相關(guān)推薦
鄂ICP備17016276號(hào)-1