貪心算法與動(dòng)態(tài)規(guī)劃

1、貪心算法 與 動(dòng)態(tài)規(guī)劃,貪心算法（Greedy Algorithm ）,,貪心法的基本思路：,——從問(wèn)題的某一個(gè)初始解出發(fā)逐步逼近給定的目標(biāo)，以盡可能快的地求得更好的解。當(dāng)達(dá)到某算法中的某一步不能再繼續(xù)前進(jìn)時(shí)，算法停止。該算法存在問(wèn)題：1. 不能保證求得的最后解是最佳的；2. 不能用來(lái)求最大或最小解問(wèn)題；3. 只能求滿足某些約束條件的可行解的范圍。,貪心算法的基本步驟,1、從問(wèn)題的某個(gè)初始解出發(fā)。2

2、、采用循環(huán)語(yǔ)句，當(dāng)可以向求解目標(biāo)前進(jìn)一步時(shí)，就根據(jù)局部最優(yōu)策略，得到一個(gè)部分解，縮小問(wèn)題的范圍或規(guī)模。3、將所有部分解綜合起來(lái)，得到問(wèn)題的最終解。,活動(dòng)安排問(wèn)題,活動(dòng)安排問(wèn)題就是要在所給的活動(dòng)集合中選出最大的相容活動(dòng)子集合。貪心算法使得盡可能多的活動(dòng)能兼容地使用公共資源設(shè)待安排的11個(gè)活動(dòng)的開始時(shí)間和結(jié)束時(shí)間按結(jié)束時(shí)間的非減序排列如下：,,若被檢查的活動(dòng)i的開始時(shí)間Si小于最近選擇的活動(dòng)j的結(jié)束時(shí)間fi，則不選擇活動(dòng)i，否則選擇活動(dòng)

3、i加入集合A中?？梢宰C明，如果在可能的事件a1<a2<…<an中選取在時(shí)間上不重疊的最長(zhǎng)序列，那么一定存在一個(gè)包含a1（結(jié)束最早）的最長(zhǎng)序列。,,貪心算法并不總能求得問(wèn)題的整體最優(yōu)解。但對(duì)于活動(dòng)安排問(wèn)題，貪心算法greedySelector卻總能求得的整體最優(yōu)解，即它最終所確定的相容活動(dòng)集合A的規(guī)模最大。這個(gè)結(jié)論可以用數(shù)學(xué)歸納法證明。,,所以做多可以容納4個(gè)活動(dòng),代碼:int greedySelector(int

4、 *s, int *f, bool *a){a[1]=true;int j=1;int count=1;for (int i=2;i=f[j]) {a[i]=true;j=i;count++;}else a[i]=false;}return count;},FOJ 1111 Radar Installation,給出雷達(dá)的掃描半徑R與孤島的個(gè)數(shù)N與坐標(biāo)，求最小要用幾個(gè)這樣的雷達(dá)。,,枚舉每一個(gè)孤島求出其與

5、X軸的交點(diǎn)dx = sqrt(r * r - y * y);x_min = x - dx;x_max = x + dx;Nlog(n)排序判斷其它點(diǎn)也X軸的交點(diǎn)是否在[x_min,x_max]范圍內(nèi),或包含,相關(guān)題目,1574一食堂宣傳欄 1230區(qū)間相交問(wèn)題,FOJ 1106 Sum of Factorials,問(wèn)一個(gè)數(shù)能否由相應(yīng)的階乖的和組合而成列表{1,1,2,6,24,120,720,5040,40320,362

6、880}; 將N嘗試性的減去表中的數(shù)，為零則YES，否則為NO證明？,FOJ 1085 Work Reduction,給出初始時(shí)的工作量n，結(jié)束時(shí)剩下的工作量m，給出可以完成這些工作量的公司，這些公司的收費(fèi)方式有兩種，A一種是減少一個(gè)單位的的工作量，每減少一單位工作量花費(fèi)a，B一種是減少一半單位的工作量，總的花費(fèi)為b，問(wèn)，分別由這些公司完成的最小的費(fèi)用。,,當(dāng)前工作量cur_n的一半小于m時(shí)，只能用A方法否則(Cur_n-cur

7、_n/2)*a > b時(shí)，選擇B方法選擇A方法如此循環(huán)N <= 100000如此log(N)的復(fù)雜度很好的避免了用其它方法可能出現(xiàn)的TLE,1150Peter's smokes,皮特有n根煙,有一個(gè)兌換數(shù)k.皮特每抽一根煙都把煙頭留著,直到足夠k個(gè)煙頭時(shí),就可以換一根新煙抽.要編寫一個(gè)程序,輸入n,k,算出皮特最多能抽多少煙.,,sum = n; while (n / k) { sum += n / k

8、; n = n / k + n % k; },,若要用貪心算法求解某問(wèn)題的整體最優(yōu)解，必須首先證明貪心思想在該問(wèn)題的應(yīng)用結(jié)果就是最優(yōu)解??！,,1316Tian Ji -- The Horse Racing1541Exploration1505Minimum value,動(dòng)態(tài)規(guī)劃（Dynamic Programming ）,,,動(dòng)態(tài)規(guī)劃算法的基本要素（1）最優(yōu)子結(jié)構(gòu)性質(zhì)（2）重疊子問(wèn)題性質(zhì)掌握設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法的步驟。(1

9、)找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。(2)遞歸地定義最優(yōu)值。（寫出動(dòng)態(tài)規(guī)劃方程）；(3)以自底向上的方式計(jì)算出最優(yōu)值。(4)根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解。,FOJ1004 Number Triangle,求人從頂端到底部,每次只能向左下右下走,最多能取得的值.,數(shù)據(jù)規(guī)模: 行數(shù)1<=R<=1000 數(shù)塔中數(shù)值0..100如圖最優(yōu)解為[ 7-3-8-7-5 ]=30,,狀

10、態(tài)表示 用a[i][j]表示第i行第j列的值。 用F(i,j)表示第i行第j列走到底部所能取得的最大值。而F(1,1)就是題目所求的答案。,搜索源代碼,#includeconst int M=1000+5;int a[M][M],n;inline int max(int x,int y){ return x<y?y:x; }int f(int i,int j){ if (

11、i==n) return a[i][j]; else return a[i][j]+max(f(i+1,j),f(i+1,j+1));} int main(){ int i,j; while(scanf("%d",&n)==1){ for(i=1;i<=n;i++) for(j=1;j<=i;j++)

12、 scanf("%d",&a[i][j]); printf("%d\n",f(1,1)); } return 0;},從一個(gè)簡(jiǎn)單的問(wèn)題入手,人每次從頂部往下走，都有2種選擇。如果搜索，到第n層的搜索量為為2n。1<=n<=1000，這種搜索量是從時(shí)間角度無(wú)法接受的。細(xì)心觀察，不難發(fā)現(xiàn)實(shí)際上做了很多重復(fù)

13、的搜索。,用動(dòng)態(tài)規(guī)劃思想解決,減少重復(fù)計(jì)算：自底向上。狀態(tài)表示 用a[i][j]表示第i行第j列的值。 用F[i][j]表示第i行第j列走到底部所能取得的最大值。而F[1][1]就是題目所求的答案。狀態(tài)轉(zhuǎn)移F[i][j]=a[i][j]+max(F[i+1][j],F[i+1][j+1]),動(dòng)態(tài)規(guī)劃源代碼,#includeconst int M=1000+5;int f[M][M],a[

14、M][M];inline int max(int x,int y){ return x=1;i--) for(j=1;j<=i;j++) f[i][j]=a[i][j]+max(f[i+1][j],f[i+1][j+1]); printf("%d\n",f[1][1]); } return 0;},FOJ1320

15、 Ones,給一個(gè)整數(shù)n，要你找一個(gè)值為n的表達(dá)式，這個(gè)表達(dá)式只有1 + * ( ) 夠成。并且1不能連續(xù)，比如11+1就不合法。輸入n,(1<=n<=10000)輸出最少需要多少個(gè)1才能構(gòu)成表達(dá)式。樣例：n=2=1+1 ans=2 n=10=(1+1)*(1+1+1+1+1) ans=7,Ones,讓f[i]表示最少數(shù)量的1能夠

16、表示i。add: f[i]=f[j]+f[i-j] 0<j<imultiply: f[i]=f[j]+f[i/j] 0<j<i, i%j=0for(i=1;i<=n;i++){ f[i]=i; for(j=1;j<i;j++){ f[i]=min(f[i],f[j]+f[i-j]); if (i%j==

17、0) f[i]=min(f[i],f[j]+f[i/j]); }}O(n2) n<=10000,Ones,How to improve?For multiply, 1<j*j<i.f[i]=min{f[j]+f[i/j]+f[i%j]} 1<j*j<iO(n1.5) 1<=n<=10000n1.5=1,000,000 算法時(shí)間可以以計(jì)算機(jī)每秒執(zhí)行8,000,000語(yǔ)

18、句進(jìn)行估算。,FOJ1319 Blocks of Stones,經(jīng)典的石子歸并問(wèn)題有n (1[7 1]->[8] 分?jǐn)?shù)7+8=15合并方案二: [2 5 1]->[2 6]->[8] 分?jǐn)?shù)6+8=14,FOJ1319 Blocks of Stones,狀態(tài)表示：用a[i] 表示初始時(shí)每堆石子的個(gè)數(shù)。用s[i]表示初始時(shí)從第1堆到第i堆石子的總和。用f[i][j](i<=j)表示從第i堆合并到第j堆的

19、最小分?jǐn)?shù)。f[i][j]=min{f[i,k-1]+f[k,j]}+w[i,j];w[i][j]=sum{a[i]…a[j]}=s[j]-s[i-1];這樣枚舉是n^3的。,最長(zhǎng)公共子序列問(wèn)題LCS,最長(zhǎng)公共子序列問(wèn)題也有最優(yōu)子結(jié)構(gòu)性質(zhì)，因?yàn)槲覀冇腥缦露ɡ恚憾ɡ? LCS的最優(yōu)子結(jié)構(gòu)性質(zhì)設(shè)序列X=和Y=的一個(gè)最長(zhǎng)公共子序列Z=，則：若xm=yn，則zk=xm=yn且Zk-1是Xm-1和Yn-1的最長(zhǎng)公共子序列； 若xm≠yn

20、且zk≠xm，則Z是Xm-1和Y的最長(zhǎng)公共子序列； 若xm≠yn且zk≠yn，則Z是X和Yn-1的最長(zhǎng)公共子序列。 其中Xm-1=，Yn-1=，Zk-1=。,,由最長(zhǎng)公共子序列問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)可知，要找出X=和Y=的最長(zhǎng)公共子序列，可按以下方式遞歸地進(jìn)行：當(dāng)xm=yn時(shí)，找出Xm-1和Yn-1的最長(zhǎng)公共子序列，然后在其尾部加上xm(=yn)即可得X和Y的一個(gè)最長(zhǎng)公共子序列。當(dāng)xm≠yn時(shí)，必須解兩個(gè)子問(wèn)題，即找出Xm-1

21、和Y的一個(gè)最長(zhǎng)公共子序列及X和Yn-1的一個(gè)最長(zhǎng)公共子序列。這兩個(gè)公共子序列中較長(zhǎng)者即為X和Y的一個(gè)最長(zhǎng)公共子序列。,,我們來(lái)建立子問(wèn)題的最優(yōu)值的遞歸關(guān)系。用c[i,j]記錄序列Xi和Yj的最長(zhǎng)公共子序列的長(zhǎng)度。其中Xi=，Yj=。當(dāng)i=0或j=0時(shí)，空序列是Xi和Yj的最長(zhǎng)公共子序列，故c[i,j]=0。其他情況下，,,1160Common Subsequence 1502Letter Deletion,FOJ1147 Tili

22、ng,In how many ways can you tile a 2 x n rectangle by 2 x 1 or 2 x 2 tiles? Here is a sample tiling of a 2 x 17 rectangle. Input is a sequence of lines, each line containing an integer number 0 <= n <= 250. For

23、each line of input, output one integer number in a separate line giving the number of possible tilings of a 2xn rectangle.,狀態(tài)表示：F[n]表示2 x n的走道上鋪滿1 x 2， 2 x 2 的磚塊的方法數(shù)量考慮最后一塊磚和最后兩塊磚的放法，很容易寫出DP狀態(tài)轉(zhuǎn)移方程。F[i]=F[i-1]+F[i-2]+F[

24、i-2], 邊界：F[0]=F[1]=1;最后一塊1 x 2豎放:F[i-1]最后兩塊1 x 2橫放:F[i-2]最后放一塊 2 x 2的:F[i-2]另外： n <= 250，需要高精度,,1018Maximal Sum 1130Bridging Signals 1340Longest Ordered Subsequence 1392Linear Board Game 1432Coin Changing 155