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

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

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

3、i加入集合A中。可以證明，如果在可能的事件a1<a2<…<an中選取在時間上不重疊的最長序列，那么一定存在一個包含a1（結(jié)束最早）的最長序列。,,貪心算法并不總能求得問題的整體最優(yōu)解。但對于活動安排問題，貪心算法greedySelector卻總能求得的整體最優(yōu)解，即它最終所確定的相容活動集合A的規(guī)模最大。這個結(jié)論可以用數(shù)學(xué)歸納法證明。,,所以做多可以容納4個活動,代碼: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,給出雷達的掃描半徑R與孤島的個數(shù)N與坐標(biāo)，求最小要用幾個這樣的雷達。,,枚舉每一個孤島求出其與

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

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

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

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

9、)找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。(2)遞歸地定義最優(yōu)值。（寫出動態(tài)規(guī)劃方程）；(3)以自底向上的方式計算出最優(yōu)值。(4)根據(jù)計算最優(yōu)值時得到的信息，構(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;},從一個簡單的問題入手,人每次從頂部往下走，都有2種選擇。如果搜索，到第n層的搜索量為為2n。1<=n<=1000，這種搜索量是從時間角度無法接受的。細(xì)心觀察，不難發(fā)現(xiàn)實際上做了很多重復(fù)

13、的搜索。,用動態(tài)規(guī)劃思想解決,減少重復(fù)計算：自底向上。狀態(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]),動態(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,給一個整數(shù)n，要你找一個值為n的表達式，這個表達式只有1 + * ( ) 夠成。并且1不能連續(xù)，比如11+1就不合法。輸入n,(1<=n<=10000)輸出最少需要多少個1才能構(gòu)成表達式。樣例：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 算法時間可以以計算機每秒執(zhí)行8,000,000語

18、句進行估算。,FOJ1319 Blocks of Stones,經(jīng)典的石子歸并問題有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ù)。用s[i]表示初始時從第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的。,最長公共子序列問題LCS,最長公共子序列問題也有最優(yōu)子結(jié)構(gòu)性質(zhì)，因為我們有如下定理：定理: LCS的最優(yōu)子結(jié)構(gòu)性質(zhì)設(shè)序列X=和Y=的一個最長公共子序列Z=，則：若xm=yn，則zk=xm=yn且Zk-1是Xm-1和Yn-1的最長公共子序列； 若xm≠yn

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

21、和Y的一個最長公共子序列及X和Yn-1的一個最長公共子序列。這兩個公共子序列中較長者即為X和Y的一個最長公共子序列。,,我們來建立子問題的最優(yōu)值的遞歸關(guān)系。用c[i,j]記錄序列Xi和Yj的最長公共子序列的長度。其中Xi=，Yj=。當(dāng)i=0或j=0時，空序列是Xi和Yj的最長公共子序列，故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