區(qū)間類型動態(tài)規(guī)劃ppt課件-wenkub
2023-05-21 12:39:04 本頁面
【正文】 四次 9 6 9得分 15 第五次 15 9得分 24 第六次 24 總分： 62 然而有更好的方案： 第一次 3 4 6 5 4 2得分 7 第二次 7 6 5 4 2得分 13 第三次 13 5 4 2得分 6 第四次 13 5 6得分 11 第五次 13 11得分 24 第六次 24 總分： 61 顯然，貪心法是錯誤的。 ? F[i， j]表示把這個數(shù)前 i位分成 j段得到的最大乘積。但有反例。 ? 特征：能將問題分解成為兩兩合并的形式 ? 求解：對整個問題設最優(yōu)值，枚舉合并點，將問題分解成為左右兩個部分，最后將左右兩個部分的最優(yōu)值進行合并得到原問題的最優(yōu)值。有點類似分治算法的解題思想。如 191919分成 3段 19*19*19=6859 但 191*91*9=156429，顯然乘積更大。 ? F[i,j]=F[k,j1]*A[k+1,i], ? 1ki=n, j=m ? 時間復雜度為 O[mn2] ? 由于有 10000組數(shù)據(jù)，因此估計時間復雜度為10000*203=8*107 ? 至于說輸出，記錄轉移的父親就可以了。 分析 ? 假設只有 2堆石子，顯然只有 1種合并方案 ? 如果有 3堆石子，則有 2種合并方案， ((1,2),3)和 (1,(2,3)) ? 如果有 k堆石子呢？ ? 不管怎么合并，總之最后總會歸結為 2堆，如果我們把最后兩堆分開，左邊和右邊無論怎么合并，都必須滿足最優(yōu)合并方案，整個問題才能得到最優(yōu)解。 ? 時間復雜度為 O(8n3),如下圖： 猜想 ? 合并第 i堆到第 j堆石子的最優(yōu)斷開位置 s[i,j]要么等于 i+1，要么等于 j1，也就是說最優(yōu)合并方案只可能是： { (i) (i+1… j) } 或者 { (i… j1) (j) } 證明 ? 設合并第 i堆到第 j堆石子的斷開位置 p，且 ipj1。 情況 2： t[i, p]t[p+1,j] 與情況 1是對稱。 ? 能量珠是一顆有頭標記與尾標記的珠子，這些標記對應著某個正整數(shù)。 ? 分析樣例： N=4， 4顆珠子的頭標記與尾標記依次為 (2， 3) (3， 5) (5， 10) (10， 2)。 凸多邊形的三角剖分 ? 給定由 N頂點組成的凸多邊形 ? 每個頂點具有權值 ? 將凸 N邊形剖分成 N2個三角形 ? 求 N2個三角形頂點權值乘積之和最??？ ? 樣例 上述凸五邊形分成△ 123 ， △ 135， △ 345 三角形頂點權值乘積之和為： 121*122*123+121*123*231+123*245*231= 12214884 分析 ?性質：一個凸多邊形剖分一個三角形后，可以將凸多邊形剖分成三個部分： ?一個三角形 ?二個凸多邊形（圖 2可以看成另一個凸多邊形為 0） 動態(tài)規(guī)劃 ? 如果我們按順時針將頂點編號，則可以相鄰兩個頂點描述一個凸多邊形。 每個頂點有一個整數(shù)標記 ，每條邊上有一個 “ +”號或 “ *” 號 。 7 425+*1234+ *樣例 分析 分析 ? 我們先枚舉第一次刪掉的邊，然后再對每種狀態(tài)進行動態(tài)規(guī)劃求最大值 。我們從前的方程，只是盡量使得局部解最大，而從來沒有想過負數(shù)的積為正數(shù)這個問題。 青蛙的煩惱 ? 有一個 n片荷葉正好在一凸多邊形頂點上 ? 有一只小青蛙恰好站在 1號荷葉的點 ? 小青蛙可以從一片荷葉上跳到另外任意一片荷葉上 ? 給出 N個點的坐標 ? 求小青蛙想通過最短的路程遍歷所有的荷葉一次且僅一次的最短路徑。 分析 ? 結論：青蛙在 1號結點只能跳到 2號結點或者 n號結點。 動態(tài)規(guī)劃 (1) ? f(s,L,0)表示從 s出發(fā)，遍歷 s..s+L1一次且僅一次的最短距離 。 ????
教學課件相關推薦
鄂ICP備17016276號-1