區(qū)間類型動態(tài)規(guī)劃ppt課件-展示頁
2025-05-15 12:39本頁面
【正文】 猜想 ? 合并第 i堆到第 j堆石子的最優(yōu)斷開位置 s[i,j]要么等于 i+1，要么等于 j1，也就是說最優(yōu)合并方案只可能是： { (i) (i+1… j) } 或者 { (i… j1) (j) } 證明 ? 設(shè)合并第 i堆到第 j堆石子的斷開位置 p，且 ipj1。 Fmax(i,j)表示將從第 i堆石子合并到第 j堆石子的最大的得分 Fmin(i,j)表示將從第 i堆石子合并到第 j堆石子的最小的得分 同理， ? Fmax[i,i] = 0， Fmin[i,i] = 0 ? 時間復(fù)雜度為 O(n3) ]},[),1m ax (),m ax ({),m ax ( m a x1jitjkFkiFjiFjki???????]},[),1m i n (),m i n ({),m i n ( m i n1jitjkFkiFjiFjki???????優(yōu)化 ? 由于石子堆是一個圈，因此我們可以枚舉分開的位置，首先將這個圈轉(zhuǎn)化為鏈，因此總的時間復(fù)雜度為 O(n4)。 分析 ? 假設(shè)只有 2堆石子，顯然只有 1種合并方案 ? 如果有 3堆石子，則有 2種合并方案， ((1,2),3)和 (1,(2,3)) ? 如果有 k堆石子呢？ ? 不管怎么合并，總之最后總會歸結(jié)為 2堆，如果我們把最后兩堆分開，左邊和右邊無論怎么合并，都必須滿足最優(yōu)合并方案，整個問題才能得到最優(yōu)解。 1. 選擇一種合并石子的方案 ,使得做 N1次合并 ,得分的總和最少 2. 選擇一種合并石子的方案 ,使得做 N1次合并 ,得分的總和最大 示例 貪心法 N=5 石子數(shù)分別為 3 4 6 5 4 2。 ? F[i,j]=F[k,j1]*A[k+1,i], ? 1ki=n, j=m ? 時間復(fù)雜度為 O[mn2] ? 由于有 10000組數(shù)據(jù)，因此估計時間復(fù)雜度為10000*203=8*107 ? 至于說輸出，記錄轉(zhuǎn)移的父親就可以了。 ? 證明： – 假設(shè) AB分成 A和 B,且 A,B10,則有 – AB=10*A+BA*B(相當(dāng)于 B個 A相加 ) – 同理可證明 A,B為任意位也成立 動態(tài)規(guī)劃 ? 可以先預(yù)處理出原數(shù)第 i到 j段的數(shù)值 A[i,j]是多少，這樣轉(zhuǎn)移就方便了，預(yù)處理也要盡量降低復(fù)雜度。如 191919分成 3段 19*19*19=6859 但 191*91*9=156429，顯然乘積更大。 整數(shù)劃分 ? 給出一個長度為 n的數(shù) ? 要在其中加 m1個乘號，分成 m段 ? 這 m段的乘積之和最大 ? mn=20 ? 有 T組數(shù)據(jù)， T=10000 貪心法 ? 盡可能平均分配各段，這樣最終的數(shù)值將會盡可能大。有點(diǎn)類似分治算法的解題思想。區(qū)間類動態(tài)規(guī)劃 合并類動態(tài)規(guī)劃的特點(diǎn) ? 合并：意思就是將兩個或多個部分進(jìn)行整合，當(dāng)然也可以反過來，也就是是將一個問題進(jìn)行分解成兩個或多個部分。 ? 特征：能將問題分解成為兩兩合并的形式 ? 求解：對整個問題設(shè)最優(yōu)值，枚舉合并點(diǎn)，將問題分解成為左右兩個部分，最后將左右兩個部分的最優(yōu)值進(jìn)行合并得到原問題的最優(yōu)值。 ? 典型試題：整數(shù)劃分，凸多邊形劃分、石子合并、多邊形合并、能量項(xiàng)鏈等。但有反例。 ? 將一個數(shù)分成若干段乘積后比該數(shù)小，因?yàn)檩斎霐?shù)不超過20位，因此不需高精度運(yùn)算。 ? F[i， j]表示把這個數(shù)前 i位分成 j段得到的最大乘積。 石子合并 ?在一園形操場四周擺放 N堆石子 (N≤100)； ?現(xiàn)要將石子有次序地合并成一堆； ?規(guī)定每次只能選相臨的兩堆合并成一堆 ,并將新的一堆的石子數(shù) ,記為該次合并的得分。 用貪心法的合并過程如下： 第一次 3 4 6 5 4 2得分 5 第二次 5 4 6 5 4得分 9 第三次 9 6 5 4得分 9 第四次 9 6 9得分 15
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1