【正文】 算法原則上能夠精確地運(yùn)行，而 且人們用筆和紙做有限次運(yùn)算后即可完成。 Var J:integer。{U 和 L 分別是要查找的數(shù)組的下標(biāo)的上界和下界 } Found： boolean。 不過，應(yīng)該指出：用實(shí)例的運(yùn)行時(shí)間來度量算法的時(shí)間復(fù)雜性并不合適，因?yàn)檫@個(gè)實(shí)例時(shí)間與運(yùn)行該算法的實(shí)際計(jì)算機(jī)性能有關(guān)。因此 T(N,I)的表達(dá)式還得進(jìn)一步簡化，或者說，我們只能在規(guī)模為 N 的某些或某類有代表性的合法輸入中統(tǒng)計(jì)相應(yīng)的 ei , i=1,2,…,k ，評價(jià)時(shí)間復(fù)雜性。我們也可以通過對若干有代表性的問題的動態(tài)規(guī)劃算法進(jìn)行分析、討論，逐漸學(xué)會并掌握這一設(shè)計(jì)方法。 貪心算法的基本思路 ： 。在當(dāng)前的擴(kuò)展結(jié)點(diǎn)處，搜索向縱深方向移至一個(gè)新結(jié)點(diǎn)。隨后， Balas 和 Zemel 提出了背包問題的“核”思想，是背包問題的呀牛獲得了較大進(jìn)展。 動態(tài)規(guī)劃是用空間換時(shí)間的一種方法的抽象。此時(shí) ,價(jià)值最大的優(yōu)先被裝入背包 ,然后裝入下一個(gè)價(jià)值最大的物品 ,直到不能再裝入剩下的物品為止。由于各種算法都有其自身的優(yōu)缺點(diǎn)，許 多學(xué)者通過利用一種算法的優(yōu)點(diǎn)同時(shí)結(jié)合其他算法避免該算法的不足，出現(xiàn)了混合算法，這樣就取得了很大的成功。 3 算法比較 以上方法對背包問題 的求解各有其優(yōu)缺點(diǎn)，如表 31 所示。剪去右子樹的條件是當(dāng)前價(jià)值加上剩余物品的總價(jià)值小于當(dāng)前的最優(yōu)總價(jià)值時(shí) ,不需搜索右子樹 ,可將右子樹剪去。 021 背包問題的主要特點(diǎn)是在選擇物品 i 裝入背包時(shí) ,每種物品僅有一件 ,可以選擇放或不放。然而當(dāng) 問題的規(guī)模較大時(shí)，得到最優(yōu)解是極其困難的。而回溯法在用來求問題的任一解時(shí)，只要搜索到問題的一個(gè)解就可以結(jié)束。 在編程中常用解決最長公共子序列問題、矩陣連乘問題、凸多邊形最優(yōu)三角剖分問題、電路布線等 問題。 動態(tài)規(guī)劃 動態(tài)規(guī)劃程序設(shè)計(jì)是對解最優(yōu)化問題的一種途徑、一種方法，而不是一種特殊算法。設(shè)此抽象的計(jì)算機(jī)所提供的元運(yùn)算有 k 種，他們分別記為 O1,O2 ,..,Ok；再設(shè)這些元運(yùn)算每執(zhí)行一次所需要的時(shí)間分別為 t1,t2,..,tk ?？梢娝惴?B_Search 比算法 Search 高效得多。前一種情況找到了等于 c 的分量，后一種情況則找不到。對于給定的整數(shù) c，要求尋找一個(gè)下標(biāo) i，使得 A[i]=c；若找不到，則返回一個(gè) 0。 算法可以理解為有基本運(yùn)算及規(guī)定的運(yùn)算順序所構(gòu)成的完整的解題 步驟。 計(jì)算機(jī)科學(xué) 家尼克勞斯 沃思曾著過一本著名的書《數(shù)據(jù)結(jié)構(gòu)十算法 = 程序》，可見算法在計(jì)算機(jī)科學(xué)界與計(jì)算機(jī)應(yīng)用界的地位。 Begin J:=1。 Begin L:=1。換句話說，這個(gè)實(shí)例時(shí)間不單純反映算法的效率而是反映包括運(yùn)行該算法的計(jì)算機(jī)在內(nèi)的綜合效率。 下面只考慮三種 情況的復(fù)雜性，即最壞情況、最好情況和平均情況下的時(shí)間復(fù)雜性，并分別記為 Tmax(N )、 Tmin(N)和 Tavg(N )。 動態(tài)規(guī)劃算法通常用于求解具有某種最優(yōu)性質(zhì)的問題。 。這個(gè)新結(jié) 點(diǎn)就成為一個(gè)新的活結(jié)點(diǎn)，并成為當(dāng)前擴(kuò)展結(jié)點(diǎn)。上世紀(jì)九十年代以后，隨著生物仿生技術(shù)和網(wǎng)絡(luò)技術(shù)的飛速發(fā)展， 各種模擬生物物理規(guī)律的并行近似算法不斷涌現(xiàn)，例如遺傳算法已經(jīng)在 01 背包問題上得到了較好的應(yīng)用，螞蟻算法、粒子群等仿生算法也在組合優(yōu)化問題中得到了很好的應(yīng)用。其關(guān)鍵是發(fā)現(xiàn)子問題和記錄其結(jié)果。 (2) 重量優(yōu)先策略 :從剩余的物品中選 取重量最小的物品裝入背包中 ,這種策略一般不能得到最優(yōu)解。 01背包問題未來的發(fā)展趨勢是繼續(xù)研究結(jié)合多種算法的混合優(yōu)化算法；通過其他學(xué)科的算法得到啟發(fā)，提出一種新的算法，繼而推動 01背包問題的研究。子集空間樹中結(jié)點(diǎn)類型為 bbnode。只有當(dāng)右子樹包含可行解時(shí)才搜索右子樹。不能將物品 i 裝入背包多次 ,也不能只裝入部分的物品 i。隨著網(wǎng)絡(luò)技術(shù)的不斷發(fā)展，背包公鑰密碼在電子商務(wù)中的公鑰設(shè)計(jì)中也起著重要的作用?；厮莘ㄔ谟脕砬髥栴}的所有解時(shí)，要回溯到根，且根結(jié)點(diǎn)的所有子樹都已被搜索遍才結(jié)束。具體的動態(tài)規(guī)劃算法多種多樣，但它們具有相同的填表格式。接下來我主要介紹一下這幾種算法。 根據(jù) T(N,I)的概念，它應(yīng)該是算法在一臺抽象的計(jì)算機(jī)上運(yùn)行所需的時(shí)間。 算法 Search 和 B_Search 解決的是同一個(gè)問題，但在最壞的情況下（所給定的 c 不在 A 中），兩個(gè)算法所需要檢測的分量個(gè)數(shù)卻大不相同，前者要 m=2 k個(gè)，后者只要 k+1 個(gè)。照此重復(fù)下去，總有一個(gè)時(shí)候，或者找到一個(gè) i 使得 A[i]=c，或者子數(shù)組為空（即子數(shù)組下界大于上界）。還設(shè) m=2 k， k 是一個(gè)確定的非負(fù)整數(shù)）。一個(gè)算法的優(yōu)劣可以用空間復(fù)雜度與 時(shí)間復(fù)雜度 來衡量。 1 算法復(fù)雜性分析的方法介紹 算法的復(fù)雜性是算法效率的度量，是評價(jià)算法優(yōu)劣的重要依據(jù)。 {初始化 } {在還沒有到達(dá) A 的最后一個(gè)分量且等于 c 的分量還沒有找到時(shí)， 查找下一個(gè)分量并且進(jìn)行檢測 } While (A[i]c)and(jm) do j:=j+1。 U:=m。我們引入算法