華南理工大學廣州學院,算法設計與期末考試復習

復習考試題型：選擇題（算法類型、時間復雜度，共15題，30分）簡答題（設計思想，共2題，12分）應用題（解題步驟、搜索空間樹等，共4題，48分）編程題（上機實驗題，作業(yè)題等，共1題，10分）復習2023/5/21復習Page32023/5/21Page3算法的幾種描述方法（重點掌握偽代碼和C++語言，會使用偽代碼寫算法）；理解大O符號的含義；算法的幾個重要特性：輸入、輸出、有窮性、確定性、可行性。第一章、第二章⑴自然語言優(yōu)點：容易理解缺點：冗長、二義性使用方法：粗線條描述算法思想

注意事項：避免寫成自然段算法的幾種描述方法（重點掌握偽代碼和C++語言，會使用偽代碼寫算法）；⑵流程圖

優(yōu)點：流程直觀缺點：缺少嚴密性、靈活性使用方法：描述簡單算法注意事項：注意抽象層次⑶程序設計語言優(yōu)點：能由計算機執(zhí)行缺點：抽象性差，對語言要求高使用方法：算法需要驗證注意事項：盡量將算法寫成子函數(shù)⑷偽代碼——算法語言偽代碼（Pseudocode）：介于自然語言和程序設計語言之間的方法，它采用某一程序設計語言的基本語法，操作指令可以結合自然語言來設計。優(yōu)點：表達能力強，抽象性強，容易理解理解大O符號的含義；時間復雜度算法的五大特性：2023/5/21第1章算法設計基礎Page9輸入：一個算法有零個或多個輸入。輸出：一個算法有一個或多個輸出。有窮性：一個算法必須總是在執(zhí)行有窮步之后結束，且每一步都在有窮時間內(nèi)完成。算法的有窮性意味著不是所有的計算機程序都是算法.確定性：算法中的每一條指令必須有確切的含義，對于相同的輸入只能得到相同的輸出?？尚行裕核惴枋龅牟僮骺梢酝ㄟ^已經(jīng)實現(xiàn)的基本操作執(zhí)行有限次來實現(xiàn)（每步可執(zhí)行）。2023/5/21復習Page102023/5/21Page10蠻力法的基本思想（重要?。?蠻力法依賴的基本技術——掃描技術，即采用一定的策略將待求解問題的所有元素依次處理一次，從而找出問題的解;關鍵——依次處理所有元素。第三章蠻力法2023/5/21復習Page112023/5/21Page11熟記哪些問題使用了蠻力法進行解決：順序查找、串匹配（KMP,BM,BF），選擇排序，冒泡排序，生成排列對象，生成子集，0/1背包，任務分配，哈密頓回路，TSP，最近對問題，凸包問題，7-11問題，百錢買百雞問題；并熟記這些問題的時間復雜度；第三章蠻力法2023/5/21復習Page122023/5/21Page12其中：BF：依次掃描，對比，O(n+m)；KMP：依次掃描，對比（雖然這個“依次”已經(jīng)是按照一定的規(guī)律，效率較高），O(n+m)，注意：對于KMP算法，必須求出next數(shù)組；選擇排序：掃描整個序列，找到整個序列的最小記錄和序列中的第一個記錄交換位置，再掃第二小，依此類推…，O(n2)；第三章蠻力法2023/5/21復習Page132023/5/21Page13其中：冒泡排序：掃描整個序列，在掃描過程中兩兩比較相鄰記錄，如果反序則交換，直到n-1趟掃描后，即排好序，O(n2)

；TSP：把所有可能的回路都找出來，就可以得到最短路徑，O(n!)；7-11：把所有可能都計算一遍，就能得到正確的解；百錢買百雞：把所有可能都計算一遍，就能得到正確的解。第三章蠻力法2023/5/21復習Page142023/5/21Page14冒泡排序、選擇排序、TSP問題的設計思想和偽代碼（可能出簡答題）7-11問題、百錢買百雞問題的代碼實現(xiàn)（猜測是編程題）第三章蠻力法冒泡排序設計思想選擇麗排序設計株思想TS勸P問杯題設計價思想TS弊P問題輸：旅幟行家郵要旅光行n個城蝕市然毒后回烤到出奇發(fā)城動市，刮要求各個弄城市錘經(jīng)歷幣且僅塔經(jīng)歷傍一次佛，并盟要求零所走否的路潛程最蹤蝶短。用蠻洽力法賤解決TS援P問題舉，可姐以找出與所有晃可能為的旅拆行路餃線，車從中土選取敞路徑琴長度承最短鬧的簡炒單回慣路。8abdc23571序號路徑路徑長度是否最短1a→b→c→d→a18

否2a→b→d→c→a11

是3a→c→b→d→a23

否4a→c→d→b→a11

是5a→d→b→c→a23

否6a→d→c→b→a18

否注意添到，眨在圖禾中有3對不前同的濱路徑淚，對納每對阻路徑乘來說束，不列同的擋只是咬路徑幻玉的方紀向，李因此足，可漿以將驢這個癢數(shù)量添減半袍，則可能游的解唉有(n-1)!/2個。這尾是一它個非當常大有的數(shù)助，隨伙著n的增始長，TS鞠P問題李的可釀能解般也在遷迅速冬地增謹長。用蠻捷力法銜求解TS坑P問題誘，其時郵間復羊雜性熄為O(n!)，只番能解桶決問職題規(guī)冤模很復小的島實例斜。一個非簡單種的例甲子——百元婆買百勉雞問菊題已知葵公雞5元一叮只，忌母雞3元一請只，小雞1元三白只，用10汗0元錢尋買10吊0只雞挖，問蛾公雞酒、母猴雞、晉小雞屋各多交少只巴？vo廊id宗c跨hi呈ck查en面()哀{in盤t鮮x,束y,燃z;fo田r(蜜x=憤0;驗x<念=2宅0;旗x+剩+)塑{fo錫r(財y=扔0;置y<擔=3偵3;陰y+言+)慌{z=激10此0-盤x-清y;if澆((z%怪3=畏=0)&渠&(攻5*達x+對3*程y+溫z/笑3=遠=1呆00乘))屬{co綿ut比<<從"公雞:"允<<拋x<繞<"母雞:"毫<<蛙y<史<"小雞:"盛<<粘z<極<e肢nd盆l;}}}}（編頭程，裹代碼驢要記部牢）7-桐11俊問題罪（編誕程，皺代碼觀要記己牢）設計煉蠻力晉算法翅找出得四件職物品災的價鋪格各逝是什俘么？#i恐nc宴lu語de腎<i溉os反tr雖ea坡m.搏h>vo越id房誠m順ai怕n(禽){in白t憲a,廣b,況c,受d;fo痛r(餡a=褲1;錄a<礎=7任11趨;a憑++躺){fo旬r(從b=博1;賀b<翼=7沉11懷;b切++憐){fo租r(快c=懇1;絨c<憐=7紐奉11塊;c柴++取){d=涌71型1-諸a-紙b-芬c;if薯(a暮*b乘*c和*d灘==萬71庸1)罰{co硬ut液<<罰a/誤10嫂0.寨0<勵<'更\t競'<肯<b敏/1分00甘.0績<<妨'\選t'獲<<暗c/番10園0.族0<歸<'秘\t組'<苦<d蒜/1丟00懇.0戚<<雨en灘dl樓;re璃tu激rn毅;}}}}20弊23爪/5需/1習8復習Pa聲ge2220掠23把/5謀/1蒼8Pa好ge22分治粉法的衣基本服思想絨（重要壺！自底鉆向上，理飄解+應用伐）：將要關求解臥的原問翠題劃啞分成k個較負小規(guī)晃模的繞子問民題，對浪這k個子性問題眠分別逃求解睛。如稱果子猜問題響的規(guī)鄉(xiāng)豐模仍每然不悶夠小蜜，則唇再將信每個津子問鳴題劃疏分為k個規(guī)怖模更偵小的劇子問王題，域如此渴分解風下去說，直恥到問斧題規(guī)捆模足詳夠小扁，很逼容易依求出總其解枯為止凡，再姓將子泊問題別的解丑合并暑為一脫個更域大規(guī)騙模的懶問題掀的解說，自底牛向上逐步殼求出孔原問付題的稻解。步驟肚：（1）劃分（2）求銜解子銹問題（3）合父并第四持章示分弱治法20零23賢/5仗/1贏8復習Pa縱ge2320侵23糧/5上/1店8Pa才ge23分治愈法的扶基本聯(lián)思想板（自底黑向上，理剩解+應用撐）：第四窩章田分扎治法

子問題1的規(guī)模是n/2

子問題1的解

子問題2的解

子問題2的規(guī)模是n/2

原問題的解

原問題的規(guī)模是n20奴23冬/5目/1盡8復習Pa供ge2420址23殺/5吳/1法8Pa疤ge24熟記妨哪些霞問題輸使用熄了分峽治法稼進行抗解決債：歸并拘排序，快速狂排序，最大禿子段奔和，棋典盤覆懶蓋，頂循環(huán)琴賽日怨程安字排，捐最近插對問推題，椅凸包柱問題洋；并堡熟記段這些演問題歪的時間孤復雜巷度：第四圾章年分遮治法20搬23傘/5環(huán)/1慚8復習Pa茅ge2520乖23雀/5犧/1匠8Pa眉ge25其中煤：歸并單排序：劃姜分成取等長健子序駕列分別耐對兩累子序句列歸嶼并排嫩序?qū)⑴偶{完的塌有序潛子序躺列合圖并成鼠一個蒸有序涌序列棵，O(疏nl瘦og2n)；快速醉排序：用匹一個煩軸值鄰劃分眠成兩已個子請序列分別門對兩生個子聲序列恥遞歸航地快科速排淚序，O(揪nl近og2n)；最大欄子段突和：劃嘉分成衛(wèi)等長挺子序底列針對3種情啊況分揪別處勝理求容子序遠列最肚大子腸段和合并3種情著況下競的最響大子茶段和疊，O(稠nl留og2n)。第四影章添分勁治法20摘23拆/5蔥/1思8復習Pa凈ge2620漏23釀/5砌/1駱8Pa僑ge26歸并洪排序快、快聲速排譽序、母最大貫子段妙和問索題的往設計條思想遲和偽倚代碼蟻；（可看能出大簡答狀題）用快賞速排質(zhì)序和摘歸并經(jīng)排序盒算法銜對數(shù)閱字序政列排意序。第四卡章鐮分朱治法歸并金排序設計躺思想二路茄歸并昨排序先的分擁治策嘗略是歸：（1）劃分：將濱待排搜序序閑列r1,r2,奔…,rn劃分蠢為兩縱個長糊度相逗等的堤子序再列r1,塔…,rn/2和rn/2＋1,偏…,rn；（2）求解敲子問耳題：分吹別對旱這兩現(xiàn)個子定序列瓣進行戴排序凱，得喝到兩它個有葡序子林序列令；（3）合并：將短這兩金個有裝序子槐序列佩合并鬼成一面?zhèn)€有例序序磁列。二路躬歸并舊排序紀在合墻并過門程中岡需要冷與原捎始記態(tài)錄序字列同欲樣數(shù)咱量的使存儲袍空間本，因享此其空間化復雜留性為O(n)。

r1……rn/2

rn/2＋1……rn

劃分r‘1<……<r’n/2r’n/2＋1<……<r’n

遞歸處理r''1<……<r''n/2<r''n/2＋1<……<r''n

合并解

r1……rn/2

rn/2＋1……rn

劃分r‘1<……<r’n/2r’n/2＋1<……<r’n

遞歸處理r''1<……<r''n/2<r''n/2＋1<……<r''n

合并解

快速仿排序設計取思想以第擱一個淘記錄否作為喇軸值搭，對險待排域序序析列進賭行劃靜分的痕過程灰為：（1）初始羞化：取趨第一鋸個記誰錄作私為基個準，姨設置失兩個祖參數(shù)i，j分別構用來烏指示蘆將要沸與基閱準記胖錄進寒行比案較的警左側(cè)芽記錄松位置耀和右察側(cè)記鴿錄位向置，棟也就虎是本蛇次劃鴉分的而區(qū)間簡；（2）右側(cè)席掃描守過程：將娃基準銅記錄鋪與j指向賊的記榆錄進召行比博較，仔如果j指向披記錄潑的關簽鍵碼迫大，吸則j前移嗚一個芝記錄束位置哭。重紡復右專側(cè)掃衣描過膽程，互直到膀右側(cè)奏的記族錄小羊（即調(diào)反序扶），導若i＜j，則搞將基撤準記圈錄與j指向辮的記個錄進飛行交營換；（3）左側(cè)名掃描漆過程：將目基準粗記錄江與i指向救的記依錄進桌行比土較，響如果i指向草記錄源的關眨鍵碼乎小，介則i后移刊一個顯記錄宏位置濫。重截復左侮側(cè)掃汁描過畜程，善直到悼左側(cè)蘭的記第錄大近（即逝反序弊），遇若i＜j，則育將基刑準記炮錄與i指向張的記翠錄交宅換；（4）重復（2）（3）步后，直氣到i與j指向杠同一訪位置偷，即鏈基準綁記錄觀最終炭的位蚊置。最大領子段奪和問旗題設計摘思想復習減治扔法的誘基本鄭思想補（理油解+應用賢）：原問輝題的結解只存閘在于圣其中顫一個較小稀規(guī)模新的子硬問題螞中，百所以達，只需饑求解姨其中幟一個麥較小口規(guī)模園的子藍問題還就可演以得僚到原泛問題爬的解蕉。熟記敗哪些姿問題址使用鋪了減浙治法貌進行呈解決諷：折半勢查找，二念叉樹旬查找怪，插入割排序，堆設排序墓，選擇仆問題，淘鍋汰賽貝冠軍田問題耕，假幣他問題尿（8枚硬纖幣不倘知道咬假幣輸輕重史）；并胞熟記與這些魔問題惑的時餡間復疏雜度粒：第五材章片減茅治法20花23友/5厘/1唐8復習Pa童ge3320螺23蔥/5符/1謊8Pa杠ge33其中僚：折半是查找穿：在有序腦表中，取中坦間記醉錄作患為比榴較對欄象，若給追定值嚴與中賺間記瓶錄的繁關鍵區(qū)碼相普等，濕則查尤找成裳功；劉若給房誠定值防小于質(zhì)中間攻記錄影的關純鍵碼家，則哲在中野間記菠錄的城左半簽區(qū)繼購續(xù)查女找；駐若給衫定值疫大于風中間段記錄忙的關須鍵碼責，則農(nóng)在中志間記歷錄的家右半溪區(qū)繼始續(xù)查本找，O(幟lo不g2n)。插入樹排序蔽：依次妖將待顫排序泉序列孫中的百每一詠個記兇錄插入火到一零個已棚排好擺序的醫(yī)序列中，嘩直到寧全部樹記錄頁都排豈好序村，O(媽n2)第五佩章恨減亞治法20稈23迫/5稼/1艘8復習Pa橡ge3420極23恰/5眼/1烘8Pa轟ge34其中些：選擇傳問題珠：考慮崗快速狗排序粒中的跪劃分藍過程饑，選假定一棍個軸擾值將裹序列ri～rj進行小劃分皆，使佳得比墊軸值湯小的眾元素臺都位板于軸域值的所左側(cè)餅，比購軸值滾大的忽元素由都位境于軸多值的辯右側(cè)個，假屆定軸訂值的惜最終看位置海是s，則給：（1）若k=s，則rs就是錯第k小元病素；（2）若k<s，則榆第k小元深素一種定在跪軸值胸前半秩區(qū)中宰；（3）若k>s，則介第k小元艱素一鼓定在狼軸值長后半仿區(qū)中扮；第五弊章禾減藍治法20咱23債/5網(wǎng)/1侵8復習Pa某ge3520弟23治/5蝦/1奧8Pa友ge35其中們：假幣純問題東（8枚硬至幣不錢知道引假幣淚輕重嚼）：從八齡枚硬核幣中如任取齡六枚a，b，c，d，e，f，在悶天平睬兩端蹦各放另三枚與進行簡比較直。假東設a，b，c三枚言放在狡天平信的一卻端，d，e，f三枚拐放在頁天平憐的另逐一端椅，可萄能出慢現(xiàn)三懲種比責較結昏果（再勿根據(jù)御三種慢比較乞結果尚進行集分析衛(wèi)）⑴a＋b＋c>d＋e＋f⑵a＋b＋c＝d＋e＋f⑶a＋b＋c<d＋e＋f第五包章薄減訓治法20曲23廉/5斤/1亂8復習Pa杯ge3620贈23息/5瞧/1艱8Pa輔ge36折半躁查找金問題稅的設枕計思貪想和筑偽代星碼（可許能出敢簡答印題）給一效個數(shù)泡字序瓶列，舍要求巴采用毀折半私查找思，找擇某個扶數(shù)，舞寫出散求解買的過約程。第五碌章蹤蝶減組治法折半蹦查找報問題設計拴思想在有序愛表中，取中遲間記仰錄作花為比封較對躍象，若給挖定值淺與中毛間記資錄的況關鍵贏碼相等，則簽查找茄成功衛(wèi)；若給親定值小于中間沫記錄鎖的關趟鍵碼衡，則沖在中傭間記黃錄的庭左半瞇區(qū)繼續(xù)查靠找；若給綱定值大于中間哭記錄獨的關科鍵碼奇，則際在中牽間記筋錄的輸右半般區(qū)繼續(xù)查印找。瓣不斷佩重復放上述朵過程撕，直標到查助找成興功，胳或所危查找倉的區(qū)域無只記錄售，查歇找失吼敗。

[r1………rmid-1]rmid[rmid+1………rn]（mid=(1+n)/2）如果k<rmid查找這里如果k>rmid查找這里

k20授23場/5悟/1昆8第5章夠減治餓法Pa玻ge38例：觸查找?guī)椭禐?4的記如錄的后過程摸：0紫1常2葵3期4沾5蛋6箏7陪8歪9咽1希0太1抽1例1毯2技1潑37宅14仙18舞2盞1汗2跪3義2屯9傾3傅1側(cè)3頸5麗38品4虛2缺46尾4顫9稠5渾2low=1high=13mid=7

high=6mid=3

high=2

mid=1

31敬>1因418川>1告47<勵14low=2mid=2

14侄=1呀4查找歌成功肝！選擇肢下列暗數(shù)字里序列咐中的光第3款小的午元素12左,逢5,卡8糞,羨44派,睛23弓,爽7,讓9留,警220霧23危/5彩/1去8復習Pa筒ge4020車23奶/5殺/1兼8Pa類ge40動態(tài)族規(guī)劃枝法的籍基本皺思想詢（重要凍！自底唯向上，理解+應用蘇）：將待塊求解躬問題譽分解蓮成若蟲干個相互找重疊的子鏟問題想，每纖個子詞問題仍對應幕決策循過程瘋的一院個階段，將快子問亂題的伸解求向解一盡次并填入表中，秘當需錢要再渠次求竿解此蘇子問即題時趨，可稀以通典過查弦表獲疲得該絲式子問杰題的翅解而牌不用朱再次左求解哪。第六腐章討動由態(tài)規(guī)事劃法20方23監(jiān)/5悼/1登8復習Pa屑ge4120攻23瓶/5見/1許8Pa圓ge41動態(tài)待規(guī)劃究法的懼求解沃過程坑：分成盜相互穩(wěn)重疊費的子聽問題辦；求解均子問懼題，街填表羅；自底醋向上僅計算蘿出原葬問題命的解那。第六枕章豆動鴿態(tài)規(guī)揚劃法20滋23怠/5喂/1冶8復習Pa芬ge4220絨23延/5腐/1西8Pa哥ge42熟記宿哪些鏟問題直使用腿了動揉態(tài)規(guī)撓劃法蒸進行駕解決互：TS荷P，多段魂圖的癢最短田路徑鴨問題，0/燭1背包，最眼長公紫共子夢序列房誠問題弓，最拌優(yōu)二尺叉查勁找樹眨，近夕似串業(yè)匹配冤問題墻；并有熟記班這些依問題斯的時間娛復雜械度：多段易圖的擠最短這路徑碼問題事：O(n+m)0/門1背包殖問題悼：O(n×C)第六敬章蝕動腫態(tài)規(guī)工劃法20犧23未/5棍/1穿8第6族章值動機態(tài)規(guī)變劃法Pa求ge432120345678949387684756866537

一個多段圖用動胞態(tài)規(guī)重劃法極解決葵多段錦圖的忠最短潛路徑歇問題喇，寫出求吼解過輩程（可肝能出步應用腐題）第六雨章唐動者態(tài)規(guī)病劃法20祥23診/5棗/1衣8第6語章僵動牧態(tài)規(guī)捐劃法Pa梅ge45根據(jù)陜動態(tài)恭規(guī)劃甘函數(shù)炕，用慕一個(n量+1刑)×(C吧+1稈)的二肥維表V，V[角i]擔[j銷]表示培把前i個物居品裝黨入容球量為j的背蔥包中治獲得態(tài)的最林大價明值。實例券：有5個物星品，榴其重糟量分宋別是{2侄,蔬2,孩6摧,翠5,霜4疾}，價膛值分構別為{6負,笨3,當5世,稱4,續(xù)6址}，背逃包的賽容量越為10。

012345678910

0w1=2v1=61w2=2v2=32w3=6v3=53w4=5v4=44w5=4v5=65000000000000000006666666660669999999066999911111406699910111314066991212151515x5=1x4=0x3=0x2=1x1=1用動旦態(tài)規(guī)豎劃法鴿解決0/爐1背包充問題輪，寫剩出求訂解過孕程。（可銹能出鑒應用剃題）物品容量20惹23產(chǎn)/5棕/1課8復習Pa近ge4620別23駝/5棄/1似8Pa噴ge46貪心告法的環(huán)基本桂思想盞（重要鎮(zhèn)！局部史最優(yōu)，理仇解+應用情）：貪心書法在督解決伐問題母的策象略上居目光錘短淺賺，只著根據(jù)博當前生已有覺的信蕩息就影做出疼選擇走，而暗且一綿旦做艦出了忍選擇屆，不燭管將誤來有永什么果結果呢，這己個選冒擇都卵不會塔改變蜻。第七昨章益貪崖心法20送23胃/5上/1腳8復習Pa哨ge4720紀23域/5繩/1呼8Pa恒ge47熟記巾哪些贏問題延使用把了貪中心法閣進行仰解決坊：TS姐P，圖真著色胳問題份，最小尸生成馳樹問站題（Pr折im算法普、Kr衡us棚ka介l算法莖），笨背包道問題，活憂動安鑰排問汁題，蛾多機忌調(diào)度粉問題蛾，哈昌弗曼節(jié)編碼鈴；并寸熟記惡這些畢問題珍的時間丸復雜貸度：第七雷章航貪龍心法20賴23樸/5漂/1駛8復習Pa悔ge4820象23烈/5坊/1隊8Pa增ge48其中幻玉：背包制問題弟：每擁次從分物品坊集合虜中選擇頌單位祝重量店價值弓最大雅的物品偶，如壯果其毛重量羅小于彼背包學容量豬，就慰可以繩把它溜裝入組，并渣將背雹包容裁量減嗓去該帝物品溫的重薪量，O(nlo由g2n)。注意雄：背短包問誤題要岡求裝尸滿整笛個背壯包，文最后抹一個誘物體弓若裝麻不下更一個蔑整體偏，可份以裝洋其中溉的一并部分闖。第七傍章預貪線心法20紋23救/5傭/1岸8復習Pa既ge4920苗23謹/5已/1孤8Pa農(nóng)ge49背包資問題畏的貪匙心算玻法設湯計思收想和鄉(xiāng)豐偽代室碼；給定n種物車品和貧一個版容量統(tǒng)為C的背呼包，鬧物品i的重般量是wi，其乓價值央為vi，背忘包問佳題是耽如何選寇擇裝癢入背塑包的齡物品熱，使紹得裝搜入背強包中乘物品賣的總雜價值譽最大?4.用貪夫心法貞解決田背包衫問題巷，寫抽出求奶解過已程（般第7章作陷業(yè)：市先按維單位額價值伸重量特比排戚序，節(jié)再依飯次放轉(zhuǎn)置物譯品，寸最后嚼求出火總價恢值，蠟寫出忌）（可泰能出責應用倘題）第七鵲章較貪樂心法背包門問題（可慌能出宣簡答柴題）設計廣思想有三散種看拿似合席理的友貪心責策略挖：（1）選伏擇價值爽最大的物殺品，典因為壓這可鋪以盡公可能媽快地椅增加窗背包映的總售價值程。但斤是，餃雖然統(tǒng)每一僚步選序擇獲敘得了早背包野價值腦的極元大增礙長，沫但背白包容業(yè)量卻靜可能慣消耗匠得太探快，庫使得肺裝入贈背包蛇的物完品個即數(shù)減尤少，內(nèi)從而鋤不能玩保證登目標畢函數(shù)現(xiàn)達到題最大陸。（2）選姑擇重量驚最輕的物碗品，淹因為希這可腔以裝嗚入盡倘可能浮多的枯物品才，從說而增年加背夸包的豆總價奮值。另但是眨，雖適然每難一步考選擇劇使背徹包的梨容量征消耗缺得慢扭了，爽但背腿包的承價值紹卻沒買能保擊證迅摔速增園長，販從而英不能賀保證斷目標分函數(shù)而達到乘最大沃。（3）選講擇單位扇重量根價值宇最大的物憤品，乏在背救包價朋值增滑長和喪背包瓶容量虧消耗靠兩者艦之間苗尋找奮平衡女。20醋23過/5幅/1鐮8第7鼓章蔽貪槍心法Pa磚ge5112蝴0青50背包18箏0護19內(nèi)0賴20脆0(a渾)三個芽物品壇及背鉆包(b史)貪心龜策略1輕(c榨)貪心翼策略2被(d探)貪心魂策略350301020203020/30201010/203010例如翼，有3個物蘇品，葬其重等量分獅別是{2垃0,凍3飯0,原1樸0}，價綠值分妹別為{6丟0,傍1奶20飲,芹50鈔}，背捷包的徹容量抽為50，應墊用三項種貪純心策握略裝敘入背秋包的思物品蘭和獲狀得的智價值描如圖嶄所示勾。20擦23擔/5唐/1哲8復習Pa挪ge5320隔23皇/5哪/1掘8Pa蝕ge53回溯境法的竿基本穗思想嫂（深度徐優(yōu)先欣搜索，理位解+應用堡）：從根模結點箱出發(fā)唇，按認照深度備優(yōu)先你策略遍歷祝解空鋪間樹杜，在仙搜索酸至樹器中任堡一結暴點時制，先企判斷縮慧該結分點對室應的脊部分擋解是代否滿拉足約束蝦條件，或編者是徐否超瞞出目標拔函數(shù)的界斤，也犯就是譯判斷市該結護點是燙否包含問題夠的（稱最優(yōu)糞）解惠，如蠶果肯脈定不但包含扇，則法跳過航對以暈該結彈點為叉根的講子樹抗的搜慚索，炕即所君謂剪枝（Pr春un渠in修g）；歷否則乘，進蘆入以胖該結寄點為音根的舒子樹渾，繼罵續(xù)按遵照深形度優(yōu)透先策仇略搜請索。第八撞章記回藏溯法20探23珠/5聾/1搖8復習Pa癢ge5420眼23絹/5腐/1種8Pa捧ge54熟記壯哪些段問題稼使用振了回萍溯法衫進行竿解決越：圖m著色與問題，哈邀密頓伴回路牛問題名，八皇每后問灶題（4皇后怖問題但），批欠處理陵作業(yè)拉調(diào)度珠問題黨；第八叨章喬回勢溯法3.燒用回灣溯法闖解決m顏色嘩圖著既色問鍋題，巾畫出擊搜索欲空間掃圖；（可刺能出脖應用梨題）圖的m著色懸問題天描述扎為：頃給定挑無向縱連通戲圖G=(V,E)和正趙整數(shù)m，判荷斷能欣否用m種顏伯色對G中的枝頂點拴著色狀，使丹得任典意兩閘個相肢鄰頂夜點著脾色不筒同。D=1ACBDE1234567891011121314A=1B=2C=3D=3E=1(a)一個無向圖(b)回溯法搜索空間圖8.8回溯法求解圖著色問題示例4.隱畫出較用回想溯法僚求解鵲8皇做后或4皇后景問題炒的搜脅索過描程（棍課本P1房誠61）（可應能出擴應用以題）八皇梢后問殼題是媽十九極世紀被著名買的數(shù)端學家垃高斯吼于18回50年提慎出的黑。問午題是急：在8×兔8的棋瓶盤上騰擺放巷八個佳皇后芳，使姜其不陜能互烏相攻昌擊，炕即任缸意兩向個皇鼻后都余不能侵處于于同一道行、舞同一釋列或挽同一熄斜線氧上。買可以極把八畝皇后舞問題僅擴展淚到n皇后交問題蹦，即算在n×n的棋埋盤上繳擺放n個皇雜后，熄使任廢意兩犧個皇黎后都貴不能賊處于卸同一開行、張同一信列或做同一棉斜線向上。回溯黑法求礦解4皇后紙問題材的搜很索過甲程20射23鄉(xiāng)豐/5木/1揪8復習Pa省ge5720傍23只/5敘/1罰8Pa運ge57分支仍限界違法的笨基本語思想歲：首先巴確定悉一個越合理營的限索界函祖數(shù)，害并根速據(jù)限店界函潛數(shù)確定轉(zhuǎn)目標樣函數(shù)剃的界[do紗wn,up]；按照廣度嘆優(yōu)先秋策略遍歷巡壽問題漠的解壺空間皆樹，喉在分暴支結坊點上傻，依仁次搜呼索該沙結點怒的所跑有孩屈子結鉗點，銷分別龜估算筐這些該孩子眨結點晉的目嚴標函繼數(shù)的很可能虛取值交；如果好某孩勸子結黑點的連目標園函數(shù)么可能寬取得匆的值瞧超出禿目標吃函數(shù)纏的界技，則街將其叢丟棄滑；否惱則，棚將其食加入腿待處謀理結味點表志（以蔥下簡蜘稱表PT）中惜；依次癥從表PT中選戒取使敏目標論函數(shù)市的值說取得常極值錢的結速點成絕為當索前擴患展結奏點；重復攝上述恨過程雷，直核到找控到最史優(yōu)解始。第九陵章赤分向支限史界法20輩23若/5已/1進8復習Pa逆ge5820古23登/5霉/1潑8Pa搏ge58分支購限界吧法的胃基本盾思想近：⑥當搜兔索到稻一個奇葉子狡結點付時，滾如果撫該結扭點的總目標計函數(shù)谷值是膊表PT中的維極值掠（對以于最御小化錢問題疊，是徒極小建值；隔對于踐最大純化問廉題，蘋是極醒大值艙），圾則該彩葉子演結點坐對應趴的解續(xù)就是障問題喉的最遺優(yōu)解儲；⑦否則時，根協(xié)據(jù)這澤個葉消子結舅點調(diào)脈整目粉標函拒數(shù)的卵界（挑對于珠最小扎化問賢題，嚷調(diào)整袋上界逢；對神于最守大化鑒問題視，調(diào)迷整下跨界）秤，依荒次考右察表PT中的梳結點雁，將赤超出筐目標館函數(shù)輔界的湯結點余丟棄卵，然慕后從毯表PT中選醬取使安目標勤函數(shù)由取得傭極值超的結晚點繼鐮續(xù)進雄行擴經(jīng)展。第九愈章提分境支限膠界法20僻23飯/5辟/1決8復習Pa懼ge5920懷23堤/5坦/1細8Pa堤ge59熟記也哪些鄙問題造使用它了分補支限僵界法號進行黑解決剖：TS神P，多租段圖仔的最賢短路補徑問舉題，任務依分配冰問題，批每處理肥作業(yè)鏈調(diào)度巧問題娘，0/拼1背包；并藏熟記傳這些忽問題丸的時間毒復雜趨度；用分思支限騎界法揀解決慶任務狼分配箱問題俯，畫采出搜念索空媽間。（可嚷能出叔應用惰題）用分史支限總界法方解決0/跑1背包抱問題槳，畫租出搜辜索空摟間。（可斗能出蠟應用穴題）第九撞章投分詞支限退界法20憐23膝/5憑/1鼻8第9爸章悼分泳支限鉛界法Pa預ge60任務鵝分配頑問題譜要求乏把n項任憐務分誼配給n個人汽，每扛個人披完成纖每項丹任務旨的成脹本不紗同，這要求籌分配擊總成本適最小的最碎優(yōu)分喜配方紐奉案。賽如圖9.援10所示逃是一復個任乎務分清配的桃成本也矩陣此。C＝9278643758187694任務1任務2任務3任務4人員a人員b人員c人員d圖9.10任務分配問題的成本矩陣任務伯分配躺問題（可絹能出振應用昂題）20競23董/5置/1膀8第9近章奔分旺支限拾界法Pa梨ge61求最深優(yōu)分糖配成慚本的搞上界遣和下亞界考慮滔任意民一個暮可行厲解，腰例如鋤：矩陣諸中的對角預線是一霧個合湖法的棉選擇螺，表抽示將鐮任務1分配毯給人能員a、任魯務2分配貼給人鋒員b、任死務3分配渾給人濃員c、任叔務4分配犬給人棉員d，其辨成本載是9+狠4+番1+迷4=挎18；或者徹應用貪心蹈法求得片一個億近似評解：祖將任紫務2分配壘給人團員a、任怕務3分配得給人棒員b、任鹽務1分配待給人較員c、任頓務4分配慢給人治員d，其稠成本周是2+剪3+界5+餡4=鍛14。顯然栗，14是一巧個更李好的蛙上界記。為什了獲蜘得下論界，爬考慮漏人員a執(zhí)行巡壽所有襪任務恢的最網(wǎng)小代絨價是2，人酬員b執(zhí)行伴所有敗任務負的最飯小代警價是3，人級員c執(zhí)行確所有喊任務咱的最叛小代絹價是1，人鞏員d執(zhí)行叮所有逗任務橋的最伴小代債價是4。因爪此，棍將每一孤行的起最小擴元素病加起近來就得逆到解躍的下芬界，籮其成術本是2+廁3+低1+殲4=互10。需要異強調(diào)是的是份，這刃個解振并不柿是一黎個合侮法的遼選擇忘（3和1來自抱于矩均陣的踢同一沫列）繁，它缺僅僅俗給出告了一舉個參限考下高界，灑這樣只，最貝優(yōu)值濃一定板是[1辨0,援1孟4]之間隱的某獵個值理。20扯23律/5勇/1架8第9鎖章姜分谷支限蔽界法Pa宋ge62圖9.素11分支逢限界嶺法求閥解任傾務分很配問胃題示揚例(×表示耗該結呀點被明丟棄獻，結始點上啟方的讀數(shù)組撫表示拘搜索仰順序)4→alb=16104×startlb=101→alb=172→alb=103→alb=151→blb=133→blb=104→blb=141→clb=144→clb=174→clb=203→clb=134→dlb=13235