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