動(dòng)態(tài)規(guī)劃教學(xué)課件

動(dòng)態(tài)規(guī)劃講師:目錄A二三四一理解什么是動(dòng)態(tài)規(guī)劃掌握動(dòng)態(tài)規(guī)劃地步驟掌握如何定義狀態(tài)轉(zhuǎn)移函數(shù)掌握記憶化搜索方法掌握使用自底向上法理解常見問題如背包問題,最長遞增子序列問題五六動(dòng)態(tài)規(guī)劃什么是動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃是一種算法設(shè)計(jì)技術(shù),通常用于求解最優(yōu)化問題動(dòng)態(tài)規(guī)劃旨在剔除遞歸地重疊子問題,對每個(gè)子問題只求解一次斐波那契數(shù)列一,一,二,三,五,八,一三,二一……F(n)=F(n-一)+F(n-二)F(一)=一F(二)=一斐波那契數(shù)列F(六)F(五)F(四)F(四)F(三)F(三)F(二)動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃問題地基本步驟一.分析原問題最優(yōu)解地結(jié)構(gòu)特征。二.遞歸地定義最優(yōu)解地值（狀態(tài)轉(zhuǎn)移函數(shù)）。三.計(jì)算最優(yōu)解地值,通常采用自底向上地方法。四.綜合計(jì)算信息,構(gòu)造最優(yōu)解。爬樓梯問題A爬樓梯問題動(dòng)態(tài)規(guī)劃一.分析原問題最優(yōu)解地結(jié)構(gòu)特征F(一零)=F(九)+F(八)二.建立遞歸關(guān)系,寫出狀態(tài)轉(zhuǎn)移函數(shù)二.建立遞歸關(guān)系,寫出狀態(tài)轉(zhuǎn)移函數(shù)初始條件:F(一)=一,F(二)=二最優(yōu)子結(jié)構(gòu):F(n)地最優(yōu)子結(jié)構(gòu)即F(n-一)與F(n-二)狀態(tài)轉(zhuǎn)移函數(shù):F(n)=F(n-一)+F(n-二)三.計(jì)算最優(yōu)解地值臺階數(shù)一二三四五六七八九一零走法數(shù)一二

三.計(jì)算最優(yōu)解地值臺階數(shù)一二三四五六七八九一零走法數(shù)一二三

三.計(jì)算最優(yōu)解地值臺階數(shù)一二三四五六七八九一零走法數(shù)一二三五

三.計(jì)算最優(yōu)解地值臺階數(shù)一二三四五六七八九一零走法數(shù)一二三五八一三二一三四五五八九四.構(gòu)造最優(yōu)解最優(yōu)解=F(一零)抓小偷問題A動(dòng)態(tài)規(guī)劃三一一八二房屋地金錢數(shù)動(dòng)態(tài)規(guī)劃一二四一七八二房屋地金錢數(shù)一.分析原問題最優(yōu)解地結(jié)構(gòu)特征F(六)=max(F(四)+二,F(五))F(五)=max(F(三)+八,F(四))二.建立遞歸關(guān)系,寫出狀態(tài)轉(zhuǎn)移函數(shù)初始條件:F(零)=V(零),F(一)=max(V(零),V(一))最優(yōu)子結(jié)構(gòu):F(n)地最優(yōu)子結(jié)構(gòu)即F(n-二)+V(n)與F(n-一)地最大值狀態(tài)轉(zhuǎn)移函數(shù):F(n)=max(F(n-一),F(n-二)+V(n))三.計(jì)算最優(yōu)解地值房子數(shù)一二三四五六七八九一零價(jià)值一二五

背包問題A動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃設(shè)物品i地重量為wi,價(jià)值為vi,一≤i≤n,則已知wi>零,vi>零,C>零。求n元向量{x一,x二,...,xn},其,xi∈{零,一},零表示不選擇該物體,一表示選擇該物體,一≤i≤n,使得:動(dòng)態(tài)規(guī)劃F(i,j)為包含前i個(gè)物品地重量為j地背包所能裝入地最大價(jià)值。F(i,j)<==>F(i-一,j),F(i-一,j-wi)+vi

動(dòng)態(tài)規(guī)劃初始條件:狀態(tài)轉(zhuǎn)移函數(shù):動(dòng)態(tài)規(guī)劃電子詞典籃球網(wǎng)球拍單詞書w二四五三v五四六二動(dòng)態(tài)規(guī)劃i/j零一二三四五六七八零零零零零零零零零零一零

二零

三零

四零

動(dòng)態(tài)規(guī)劃i/j零一二三四五六七八零零零零零零零零零零一零零五五五五五五五二三四v(一)=五w(一)=二F(一,二)=max(F(零,二),v(一)+F(零,二-二))動(dòng)態(tài)規(guī)劃i/j零一二三四五六七八零零零零零零零零零零一零零五五五五五五五二零零五五五五九九九三四動(dòng)態(tài)規(guī)劃i/j零一二三四五六七八零零零零零零零零零零一零零五五五五五五五二零零五五五五九九九三零零五五五六九一一一一四v(三)=六w(三)=五F(三,五)=max(F(二,五),v(三)+F(二,零))動(dòng)態(tài)規(guī)劃i/j零一二三四五六七八零零零零零零零零零零一零零五五五五五五五二零零五五五五九九九三零零五五五六九一一一一四零零五五五七九一一一一最長遞增子序列A動(dòng)態(tài)規(guī)劃Ai{a一,a二,……,ai}Ai-一{a一,a二,……,ai-一}ai動(dòng)態(tài)規(guī)劃A{三,一,四,五,九,二,六,五,零}當(dāng)處理到第三個(gè)元素(四)時(shí)三,四一,四動(dòng)態(tài)規(guī)劃A{三,一,四,五,九,二,六,五,零}當(dāng)處理到第七個(gè)元素(六)時(shí)三,一 三,四三,四,五三,四,五,九一,二動(dòng)態(tài)規(guī)劃A{三,一,四,五,九,二,六,五,零}當(dāng)處理到第八個(gè)元素(五)時(shí)三,五一,五三,四,五三,四,五三,四,五,九一,二,五動(dòng)態(tài)規(guī)劃A{三,一,四,五,九,二,六,五,零}當(dāng)處理到第六個(gè)元素(二)時(shí),長度是二地序列為三,四一,二動(dòng)態(tài)規(guī)劃A{六,八,九,一,三,四,五}當(dāng)處理前三次循環(huán)時(shí),會(huì)得到長度是一,二,三地序列為六六,八六,八,九B=[六,八,九]

動(dòng)態(tài)規(guī)劃A{六,八,九,一,三,四,五}當(dāng)處理第四個(gè)數(shù)字時(shí),會(huì)得到長度是一,二,三地序列為六六,八六,八,九一B=[一,八,九]

動(dòng)態(tài)規(guī)劃A{六,八,九,一,三,四,五}當(dāng)處理第五個(gè)數(shù)字時(shí),會(huì)得到長度是一,二,三地序列為一六,八六,八,九一,三B=[一,三,九]

動(dòng)態(tài)規(guī)劃A{六,八,九,一,三,四,五}當(dāng)處理第六個(gè)數(shù)字時(shí),會(huì)得到長度是一,二,三地序列為一一