【文章內(nèi)容簡(jiǎn)介】 0≤y≤Wn 和f(i,y)=max(f(i+1,y),f(i+1,yWi)+Pi)y≥Wi f(i,y)=f(i+1,y)0≤y≤Wi 這個(gè)方程非常重要，基本上所有跟背包相關(guān)的問題的方程都是由它衍生出來的，所以有必要將它詳細(xì)解釋一下：“將前i件物品放入容量為y的背包中”這個(gè)子問題，若只考慮第i件物品的策略（放或不放），那么就可以轉(zhuǎn)化為一個(gè)只牽扯前i1件物品的問題。如果不放第i件物品，那么問題就轉(zhuǎn)化為“前i1件物品放入容量為y的背包中”，價(jià)值為f[i1][y]；如果放第i件物品，那么問題就轉(zhuǎn)化為“前i1件物品放入剩下的容量為yWi的背包中”，此時(shí)能獲得的最大價(jià)值就是f[i1][yWi]再加上通過放入第i件物品獲得的價(jià)值Pi。用貪心算法解決問題的基本思路如下：由所有解元素組合成問題的一個(gè)可行解；從問題的某一個(gè)初始解出發(fā)逐步逼近給定的目標(biāo)，以盡可能快的地求得更好的解。當(dāng)達(dá)到某算法中的某一步不能再繼續(xù)前進(jìn)時(shí)，算法停止。實(shí)現(xiàn)該算法的過程： 從問題的某一初始解出發(fā)；while 能朝給定總目標(biāo)前進(jìn)一步do求出可行解的一個(gè)解元素；該算法存在問題：首先不能保證求得的最后解是最佳的；其次不能用來求最大或最小解問題，并且只能求滿足某些約束條件的可行解的范圍?；厮莘ㄊ且粋€(gè)既帶有系統(tǒng)性又帶有跳躍性的的搜索算法。所以01背包問題也可以用回溯法解決。其基本思路是可先將物品依其單位重量?jī)r(jià)值從大到小排序，此后只要順序考察各物品即可，這是為了便于計(jì)算上界。在實(shí)現(xiàn)時(shí)，由bound計(jì)算當(dāng)前結(jié)點(diǎn)處的上界。在搜索解空間樹時(shí)，只要其左兒子節(jié)點(diǎn)是一個(gè)可行結(jié)點(diǎn)，搜索就進(jìn)入左子樹，在右子樹中有可能包含最優(yōu)解是才進(jìn)入右子樹搜索。否則將右子樹剪去。當(dāng)然01背包問題還有許多的解決方案，此處就不一一列出。不過通過01背包問題，我深刻體會(huì)到算法的魅力，體會(huì)到同一個(gè)問題用不同的方法解決的妙處。學(xué)無(wú)止境，《算法設(shè)計(jì)與分析》僅僅是我學(xué)習(xí)算法知識(shí)入門課，我不會(huì)停下腳步，在此之后我依然會(huì)努力學(xué)習(xí)算法知識(shí)。第四篇：“算法設(shè)計(jì)與分析”課程教學(xué)大綱與教學(xué)規(guī)程“算法設(shè)計(jì)與分析”課程教學(xué)大綱和教學(xué)規(guī)程課程編號(hào)：課程名稱（中文）：算法設(shè)計(jì)與分析課程名稱（英文）：The design and analysis of algorithms 開課學(xué)期： 見培養(yǎng)方案與教學(xué)計(jì)劃 課程類別： 專業(yè)基礎(chǔ)課程課程學(xué)時(shí)數(shù)與學(xué)分： 56學(xué)時(shí)（4學(xué)分，不含實(shí)驗(yàn)課時(shí)，4學(xué)時(shí)/周）實(shí)驗(yàn)學(xué)時(shí)數(shù)與學(xué)分： 28學(xué)時(shí)（學(xué)分計(jì)算并入計(jì)算機(jī)科學(xué)實(shí)驗(yàn)課程，4學(xué)時(shí)/次/周）先修課程： 高等數(shù)學(xué)或數(shù)學(xué)分析，線性代數(shù)或高等代數(shù)，概率論與數(shù)理統(tǒng)計(jì)，離散數(shù)學(xué)，高級(jí)語(yǔ)言程序設(shè)計(jì)，數(shù)據(jù)結(jié)構(gòu)教學(xué)形式： 課堂講授 + 課外教學(xué) + 實(shí)驗(yàn)教學(xué)（實(shí)驗(yàn)課程實(shí)行單列）使用教材：張德富，算法設(shè)計(jì)與分析，國(guó)防工業(yè)出版社，2009,8。教學(xué)參考書：[1] , , and , Introduction to Algorithms(the second edition)，The MIT Press，2001 該書國(guó)內(nèi)已引進(jìn)，見《算法導(dǎo)論（第二版）》（影印版，中文本），高等教育出版社，2003 [2] ，Algorithms Design Techniques and Analysis，World Scientific Publishing Company，1998 ，吳偉昶 等譯，《算法設(shè)計(jì)技巧與分析》（中文版），電子工業(yè)出版社，2004 [3] Sartaj Sahni著，汪詩(shī)林等譯，《數(shù)據(jù)結(jié)構(gòu)、算法與應(yīng)用C++語(yǔ)言描述》，機(jī)械工業(yè)出版社，2003 [4] 王曉東編著，《計(jì)算機(jī)算法設(shè)計(jì)與分析》，電子工業(yè)出版社，2005 [5] Gilles Brassard, Paul Bratley.《FUNDAMENTALS OF ALGORITHMICS》(算法基礎(chǔ))，清華大學(xué)出版社，2005 注：[1]和[2]兩本書為主要教學(xué)參考書。大綱制定者： 張德富、趙致琢、蘇 暢（廈門大學(xué)計(jì)算機(jī)科學(xué)系）大綱審定者： 趙致琢（廈門大學(xué)計(jì)算機(jī)科學(xué)系）2．課程性質(zhì)、類別與任務(wù)“算法設(shè)計(jì)與分析”是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)一門重點(diǎn)專業(yè)基礎(chǔ)課程，也是學(xué)科核心專業(yè)基礎(chǔ)課程之一，屬于必修課程。本課程主要介紹算法的基礎(chǔ)知識(shí)，包括抽象計(jì)算模型、算法基本概念、算法復(fù)雜性分析基礎(chǔ)、算法設(shè)計(jì)的基本方法、以及算法復(fù)雜性理論基礎(chǔ)。通過本課程的學(xué)習(xí)，要求學(xué)生理解并熟練掌握：了解可支持算法運(yùn)行的抽象機(jī)器計(jì)算模型，算法的定義和復(fù)雜性概念，算法設(shè)計(jì)的基本技術(shù)方法，包括遞歸與分治法、貪心法、動(dòng)態(tài)規(guī)劃方法、回溯法、分支限界法以及高級(jí)圖論算法等，理解并掌握算法復(fù)雜性的分析方法、NP完全性理論基礎(chǔ)等計(jì)算復(fù)雜性的基本知識(shí)以及完全性證明概要。通過教學(xué)和實(shí)踐，培養(yǎng)學(xué)生運(yùn)用數(shù)學(xué)工具和方法分析問題和從算法的角度運(yùn)用數(shù)學(xué)工具解決問題的基本能力，培養(yǎng)學(xué)生設(shè)計(jì)算法和分析算法復(fù)雜性的基本能力，訓(xùn)練學(xué)生的邏輯思維能力和想象力，從而使他們能夠正確地分析和評(píng)價(jià)一個(gè)算法，進(jìn)一步設(shè)計(jì)出真正有效或更有效的算法，并使之了解算法理論的基礎(chǔ)知識(shí)和發(fā)展概況。在教學(xué)中，鼓勵(lì)學(xué)生運(yùn)用算法知識(shí)解決各個(gè)學(xué)科的實(shí)際計(jì)算問題，培養(yǎng)學(xué)生初步的獨(dú)立開展科研工作的能力和理論聯(lián)系實(shí)踐，解決實(shí)際問題的能力，同時(shí)，為后續(xù)課程以及將來的研究工作提供必要的算法設(shè)計(jì)與分析的基礎(chǔ)。此外，配合實(shí)驗(yàn)課程的教學(xué)，學(xué)生應(yīng)理論聯(lián)系實(shí)際，理論指導(dǎo)實(shí)踐，通過規(guī)范地完成一系列算法設(shè)計(jì)實(shí)驗(yàn)進(jìn)一步鞏固所學(xué)的相關(guān)書本知識(shí)，在知識(shí)、能力、素質(zhì)上得到進(jìn)一步的提高。3．課程教學(xué)的基本要求（教學(xué)內(nèi)容和教學(xué)重點(diǎn)）“算法設(shè)計(jì)與分析”內(nèi)容的重點(diǎn)是各種常用的算法設(shè)計(jì)方法和復(fù)雜性分析方法，包括遞歸與分治法、貪心法、動(dòng)態(tài)規(guī)劃方法、回溯法、分支限界法，以及高級(jí)圖論算法、時(shí)空復(fù)雜性的分析方法、NP完全性理論基礎(chǔ)。課程教學(xué)的基本要求是通過教學(xué)活動(dòng)，使每一個(gè)學(xué)生較好地掌握課程的主要內(nèi)容，同時(shí)具備對(duì)實(shí)際問題應(yīng)用所學(xué)知識(shí)設(shè)計(jì)出有效算法并編程實(shí)現(xiàn)這些算法的能力。課程的教學(xué)內(nèi)容主要包括如下知識(shí)點(diǎn)，其中，屬于重點(diǎn)的內(nèi)容用黑體標(biāo)示，今后教學(xué)改革擬增加的內(nèi)容用“{??}”標(biāo)示，部分非重要內(nèi)容用括弧標(biāo)注為“一般了解”： 基本概念：?jiǎn)栴}。抽象計(jì)算模型；算法的概念；算法正確性。算法效率；問題下界 算法的評(píng)估：時(shí)間復(fù)雜性和空間復(fù)雜性分析；算法的最優(yōu)、最差和平均效率；漸近復(fù)雜性符號(hào)和基本效率類型；非遞歸算法的數(shù)學(xué)分析；{概率分析（一般了解）；分?jǐn)偡治觯ㄒ话懔私猓凰惴ǖ慕?jīng)驗(yàn)分析；算法可視計(jì)算方法}； 遞歸：遞歸設(shè)計(jì)；遞歸算法轉(zhuǎn)非遞歸算法；遞歸算法的設(shè)計(jì)實(shí)例；遞歸算法的數(shù)學(xué)分析，{三種求解遞歸方程的方法}；分治法：分治法的基本思想；分治法設(shè)計(jì)的特點(diǎn)；分治法的時(shí)間復(fù)雜性；分治法的應(yīng)用（大整數(shù)乘法和Strassen矩陣乘法；棋盤覆蓋）； 基本的排序算法及其復(fù)雜性分析：插入排序；堆排序；快速排序；排序算法復(fù)雜度分析及其比較（此處的教學(xué)重點(diǎn)在于算法分析，透過算法分析從中深入了解算法的特性，進(jìn)一步揭示設(shè)計(jì)更為有效的算法的思路和途徑）； 動(dòng)態(tài)規(guī)劃方法：動(dòng)態(tài)規(guī)劃的基本要素（含最優(yōu)性原理）；矩陣連乘問題；0/1背包問題；裝配線的調(diào)度問題；最長(zhǎng)公共子序列；貪心算法：貪心算法的基本要素；背包問題；哈夫曼編碼；活動(dòng)選擇問題；{貪心算法的理論基礎(chǔ)（一般了解）}；回溯法：回溯法的基本思想；裝載問題；0/1背包問題；旅行商問題；批處理的作業(yè)調(diào)度問題；n皇后問題；子集合問題；回溯法的效率分析；分支限界法（分支定界法）：分