【正文】 算法解背包問題的基本步驟： 12 回溯發(fā) 13 回溯法基本思想 13 回溯發(fā)解題基本步驟 13 實例——01背包問題 14 分支限界法 15 分支限界法思想 15 實例——裝載問題 16總結(jié) 18參考文獻(xiàn) 181. 前言 論文背景 算法（Algorithm）是指解題方案的準(zhǔn)確而完整的描述，是一系列解決問題的清晰指令，算法代表著用系統(tǒng)的方法描述解決問題的策略機(jī)制。也就是說，能夠?qū)σ欢ㄒ?guī)范的輸入，在有限時間內(nèi)獲得所要求的輸出。description to the problem solving scheme算法中的指令描述的是一個計算，當(dāng)其運(yùn)行時能從一個初始狀態(tài)和（可能為空的）初始輸入開始，經(jīng)過一系列有限而清晰定義的狀態(tài)，最終產(chǎn)生輸出并停止于一個終態(tài)。通過對五中常用算法的單獨(dú)講解、綜合對比，分析出各種算法的特點(diǎn)以及適用領(lǐng)域，最后列舉相應(yīng)的算法實例，讓讀者對這五中常用算法有更深的了解。 表達(dá)算法的抽象機(jī)制高級程序設(shè)計語言的主要好處是：（1）高級語言更接近算法語言，易學(xué)、易掌握，一般工程技術(shù)人員只需要幾周時間的培訓(xùn)就可以勝任程序員的工作；（2）高級語言為程序員提供了結(jié)構(gòu)化程序設(shè)計的環(huán)境和工具，使得設(shè)計出來的程序可讀性好，可維護(hù)性強(qiáng)，可靠性高；（3）高級語言不依賴于機(jī)器語言，與具體的計算機(jī)硬件關(guān)系不大，因而所寫出來的程序可植性好、重用率高抽象數(shù)據(jù)類型是算法的一個數(shù)據(jù)模型連同定義在該模型上并作為算法構(gòu)件的一組運(yùn)算。分治法的設(shè)計思想，是將一個難以直接解決的大問題，分割成一些規(guī)模較小的相同問題，以便各個擊破，分而治之。因此，當(dāng)P的規(guī)模不超過n0時，直接用算法Adhoc（P）求解。 動態(tài)規(guī)劃 動態(tài)規(guī)劃基本思想動態(tài)規(guī)劃過程中，每次決策依賴于當(dāng)前狀態(tài)，又隨即引起狀態(tài)的轉(zhuǎn)移。② 無后效性：即某階段狀態(tài)一旦確定，就不受這個狀態(tài)以后決策的影響。在劃分階段時，注意劃分后的階段一定要是有序的或者是可排序的，否則問題就無法求解。考察這n個矩陣的連乘積A1A2…An由于矩陣乘法滿足結(jié)合律，所以計算矩陣的連乘可以有許多不同的計算次序。 j ]=Ai，為單一矩陣，無需計算，因此m[ i ][ i ]=0。 m[ i ][ j ] = min{ m[ i ][ k ]+m[ k+1 ][ j ]+Pi1*Pk*Pj } m[ i ][ j ]給出了最優(yōu)值，即計算A[ i : j ]所需的最少數(shù)乘次數(shù)。每個子問題只計算一次，而在后面需要時只要簡單查一下，從而避免大量的重復(fù)計算 。但是，從許多可以用貪心算法求解的問題中看到這類問題一般具有2個重要的性質(zhì)：貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。 貪心算法和動態(tài)規(guī)劃的區(qū)別 貪心算法和動態(tài)規(guī)劃算法都要求問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，這是2類算法的一個共同點(diǎn)。i因此，算法的計算時間上界為（其實回溯法就是對隱式圖的深度優(yōu)先搜索算法）。在任何時刻，算法只保存從根結(jié)點(diǎn)到當(dāng)前擴(kuò)展結(jié)點(diǎn)的路徑。否則將右子樹剪去。（2）優(yōu)先隊列式分支限界法按照優(yōu)先隊列中規(guī)定的優(yōu)先級選取優(yōu)先級最高的節(jié)點(diǎn)成為當(dāng)前擴(kuò)展節(jié)點(diǎn)。 實例——裝載問題(1):問題描述有一批共n個集裝箱要裝上2艘載重量分別為c1和c2的輪船上，其中集裝箱i的重量為wi，且w1+w2+...+wn = c1+c2。由此可知，裝載問題也是NP難的。由于此次設(shè)計主要是在校內(nèi)進(jìn)行的，在設(shè)計的過程中得到了導(dǎo)師和同學(xué)以及論壇上朋友的大量的幫助，從而能順利的完成該設(shè)計。如果有，找出一種裝載方案。②搜索方式的不同：回溯法以深度優(yōu)先的方式搜索解空間樹，而分支限界法則以廣度優(yōu)先或以最小耗費(fèi)優(yōu)先的方式搜索解空間樹。在分支限界法中，每一個活結(jié)點(diǎn)只有一次機(jī)會成為擴(kuò)展結(jié)點(diǎn)。而顯式地存儲整個解空間則需要O(2^h(n))或O(h(n)!)內(nèi)存空間。 而若使用回溯法求任一個解時，只要搜索到問題的一個解就可以結(jié)束。 回溯發(fā) 回溯法基本思想回溯法（探索與回溯法）是一種選優(yōu)搜索法，又稱為試探法，按選優(yōu)條件向前搜索，以達(dá)到目標(biāo)。n。01背包問題：給定n種物品和一個背包。這是貪心算法可行的第一個基本要素，也是貪心算法與動態(tài)規(guī)劃算法的主要區(qū)別。也就是說貪心算法并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇。③.計算最優(yōu)值根據(jù)計算m[ i ][ j ]的遞歸式，容易寫一個遞歸算法計算m[ 1 ][ n ]。事實上，若計算A[ i : j ]的最優(yōu)次序在Ak和Ak+1之間斷開，i=kj，則m[ i ][ j ]=m[ i ][ k ]+m[k+1][ j ]+Pi1*Pk*Pj。因此，矩陣連乘積計算次序問題的最優(yōu)解包含著其子問題的最優(yōu)解。若一個矩陣連乘積的計算次序完全確定，也就是說該連乘積已完全加括號，則可以依此次序反復(fù)調(diào)用2個矩陣相乘的標(biāo)準(zhǔn)算法計算出矩陣連乘積(2) 算法設(shè)計①.分析最優(yōu)解的結(jié)構(gòu)設(shè)計求解具體問題的動態(tài)規(guī)劃算法的第一步是刻畫該問題的最優(yōu)解的結(jié)構(gòu)特征。（3）以自底向上或自頂向下的記憶化方式（備忘錄法）計算出最優(yōu)值（1）分析最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征。 (4)尋找邊界條件：給出的狀態(tài)轉(zhuǎn)移方程是一個遞推式，需要一個遞推的終止條件或邊界條件。 (2)確定狀態(tài)和狀態(tài)變量：將問題發(fā)展到各個階段時所處于的各種客觀情況用不同的狀態(tài)表示出來。③有重疊子問題：即子問題之間是不獨(dú)立的，一個子問題在下一階段決策中可能被多次使用到。基本思想與分治法類似，也是將待求解的問題分解為若干個子問題（階