[計(jì)算機(jī)]動(dòng)態(tài)規(guī)劃的模型構(gòu)建-在線瀏覽
2024-12-03 23:00本頁(yè)面
【正文】 性。 ? 寫出狀態(tài)轉(zhuǎn)移方程（包括邊界條件和取值范圍）：根據(jù)問題的性質(zhì)（求最大 /最?。?，用數(shù)學(xué)方程描述狀態(tài)轉(zhuǎn)移的方法和過程 編程實(shí)現(xiàn)？ ? 循環(huán) – For i … – For j … – (dummy) ? 遞歸 – Solve(i,j) – If solved f[i][j] return f[i][j] – (dummy) 數(shù)字三角形求解 ? 狀態(tài)： f(i,j)表示走到第 i行 j列獲得的最大值 ? 狀態(tài)轉(zhuǎn)移方程 : f(i,j)=max{f(i1,j),f(i1,j+1)}+a[i,j] 初始： f(0,0)=0 問題 1：求最短距離（ 1） ? 某人要從 S1前往 SN，其中 Si至 Si+1有若干種行進(jìn)方式（步行，自行車，公交車，越野車， etc），分別要花費(fèi)一定的時(shí)間 ? 問最快到達(dá)的時(shí)間是多少？ 分析 ? 劃分階段、選擇狀態(tài)： ? 到達(dá)各個(gè)不同的地點(diǎn)作為一個(gè)階段 ? 一個(gè)階段里就一個(gè)狀態(tài) ? 用 F[i]表示從 S1到達(dá) Si所需最短的時(shí)間 ? 寫出規(guī)劃方程（包括邊界條件）： ? F[1]=0 ? F[i]=F[i1]+Si1到達(dá) Si所需花費(fèi)的最短時(shí)間 問題 1：求最短距離（ 2） ? 某人要從 S1前往 SN，其中 Si至 Si+1有若干種行進(jìn)方式（步行，自行車，公交車，越野車， etc），分別要花費(fèi)一定的時(shí)間，并且如果在一個(gè)地點(diǎn)選擇切換行進(jìn)方式，需要額外消耗一定的時(shí)間。 則 , f(i)=max{f(j)+1},其中 ji and a[j]=a[i] 這里 0ji=n。 ? 上述式子的含義：找到 i之前的某 j，這個(gè)數(shù)不比第 i個(gè)數(shù)小 ,對(duì)于所有的 j取 f(j)的最大值。 ? 例如， X=“ ABCBDAB”， Y=“ BCDB”是 X的一個(gè)子序列。 動(dòng)態(tài)規(guī)劃 ? 設(shè) f(i,j)表示 S的前 i位與 T的前 j位的最長(zhǎng)公共子串長(zhǎng)度。amp。amp。 ? 給出一個(gè)串，求最小編輯次數(shù)，使得某個(gè)串變成回文串？ 問題 3： 01背包問題 ? 有 N件物品 。 ? 第 i件物品價(jià)值 Ci元 。 ? 問選取裝載哪些物品，使得卡車運(yùn)送的總價(jià)值最大？ 動(dòng)態(tài)規(guī)劃 ? 可以按每個(gè)物品進(jìn)行規(guī)劃，同樣每種物品有選和不選兩種選擇 ? 設(shè) F(i,j)表示前 i件物品載重為 j的最大效益，則有 ? 1=i=N, 0=j=N ? 初值： F(0,j)=0 ? F(N,M)即答案 ? 顯然時(shí)間復(fù)雜度為 O(NM) ????????種物品不裝載第種物品裝載第ijiFiiCiwjiFM a xjiF),1(],[])[,1(),(思考？ ? 完全背包問題：即每個(gè)物品可取無限次。 ? 帶條件背包問題：取某種物品，必須取另外一種物品的限制。 ? 每個(gè)物品有個(gè)編號(hào)，價(jià)值最大的前提下，所取物品組成的排列字典序最小。編一程序 ,由文件讀入堆數(shù) N及每堆石子數(shù) (≤20), (1)選擇一種合并石子的方案 ,使得做 N1次合并 ,得分的總和最少 (2) 選擇一種合并石子的方案 ,使得做 N1次合并 ,得分的總和最大 ? 輸入數(shù)據(jù) : 第一行為石子堆數(shù) N。 用貪心法的合并過程如下： 第一次 3 4 6 5 4 2得分 5 第二次 5 4 6 5 4得分9 第三次 9 6 5 4得分 9 第四次 9 6 9得分 15 第五次 15 9得分 24 第六次 24 總分： 62 然而仔細(xì)琢磨后，發(fā)現(xiàn)更好的方案： 第一次 3 4 6 5 4 2得分 7 第二次 7 6 5 4 2得分 13 第三次 13 5 4 2得分 6
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1