ACM競賽之動態(tài)規(guī)劃

第8講:ACM競賽之動態(tài)規(guī)劃8.1基本概念動態(tài)規(guī)劃(dynamicprogramming)是運籌學的一個分支，是求解決策過程(decisionprocess)最優(yōu)化的數(shù)學方法。20世紀50年代初美國數(shù)學家R.E.Bellman等人在研究多階段決策過程(multistepdecisionprocess)的優(yōu)化問題時，提出了著名的最優(yōu)化原理(principleofoptimality)，把多階段過程轉化為一系列單階段問題，利用各階段之間的關系，逐個求解，創(chuàng)立了解決這類過程優(yōu)化問題的新方法——動態(tài)規(guī)劃。第8講:ACM競賽之動態(tài)規(guī)劃8.1基本概念術語階段：把所給求解問題的過程恰當?shù)胤殖扇舾蓚€相互聯(lián)系的階段，以便于求解，過程不同，階段數(shù)就可能不同。狀態(tài)：表示每個階段開始面臨的自然狀況或客觀條件，它不以人們的主觀意志為轉移，也稱為不可控因素。無后效性：如果給定某一階段的狀態(tài)，則在這一階段以后過程的發(fā)展不受這階段以前各段狀態(tài)的影響，所有各階段都確定時，整個過程也就確定了。狀態(tài)變量：過程的狀態(tài)通?？梢杂靡粋€或一組數(shù)來描述，稱為狀態(tài)變量。一般，狀態(tài)是離散的，但有時為了方便也將狀態(tài)取成連續(xù)的。

第8講:ACM競賽之動態(tài)規(guī)劃8.1基本概念術語決策：一個階段的狀態(tài)給定以后，從該狀態(tài)演變到下一階段某個狀態(tài)的一種選擇（行動）稱為決策。

在許多問題中，決策可以表示為一個數(shù)或一組數(shù)。不同的決策對應著不同的數(shù)值。描述決策的變量稱決策變量。因狀態(tài)滿足無后效性，故在每個階段選擇決策時只需考慮當前的狀態(tài)而無須考慮過程的歷史。決策變量的范圍稱為允許決策集合。第8講:ACM競賽之動態(tài)規(guī)劃8.1基本概念術語策略：由每個階段的決策組成的序列稱為策略。對于每一個實際的多階段決策過程，可供選取的策略有一定的范圍限制，這個范圍稱為允許策略集合。允許策略集合中達到最優(yōu)效果的策略稱為最優(yōu)策略。狀態(tài)轉移方程：給定k階段狀態(tài)變量x(k)的值后，如果這一階段的決策變量一經確定，第k+1階段的狀態(tài)變量x(k+1)也就完全確定，即x(k+1)的值隨x(k)和第k階段的決策u(k)的值變化而變化，那么可以把這一關系看成(x(k)，u(k))與x(k+1)確定的對應關系，用x(k+1)=Tk(x(k),u(k))表示。這是從k階段到k+1階段的狀態(tài)轉移規(guī)律，稱為狀態(tài)轉移方程。第8講:ACM競賽之動態(tài)規(guī)劃8.1基本概念術語最優(yōu)化原理:作為整個過程的最優(yōu)策略，它滿足：相對前面決策所形成的狀態(tài)而言，余下的子策略必然構成“最優(yōu)子策略”。一個問題滿足最優(yōu)化原理也稱其擁有最優(yōu)子結構性質。多階段決策問題：一類活動過程可以分為若干個互相聯(lián)系的階段，在每一個階段都需作出決策，一個階段的決策確定以后，常常影響到下一個階段的決策，從而就完全確定了一個過程的活動路線。各階段決策構成一個決策序列，稱為一個策略。每一階段都有若干個決策可供選擇，因而就有許多策略供我們選取，對應于一個策略可以確定活動的效果，這個效果可以用數(shù)量來確定。多階段決策問題是要在可以選擇的那些策略中間，選取一個最優(yōu)策略，使在預定標準下達到最好的效果.第8講:ACM競賽之動態(tài)規(guī)劃8.1基本概念例題：數(shù)字三角形描述：有一個由非負整數(shù)組成的三角形，第一行只有一個數(shù)，除了最下行之外每個數(shù)的左下方和右下方各有一個數(shù)。問題：從第一行的數(shù)開始，每次可以往左下或右下走一格，直到走到最下行，把沿途經過的數(shù)全部加起來。如何走才能使得這個和盡量大？第8講:ACM競賽之動態(tài)規(guī)劃8.1基本概念例題：數(shù)字三角形解決方法：回溯法時間復雜度O(2n）第8講:ACM競賽之動態(tài)規(guī)劃8.1基本概念例題：數(shù)字三角形解決方法：動態(tài)規(guī)劃階段:分層狀態(tài):當前的位置(i,j)決策變量或指標函數(shù):d(i,j)從格子(i,j)出發(fā)時能得到的最大和（包括格子(i,j)本身的值）狀態(tài)轉移方程：d(i,j)=a(i,j)+max{d(i+1,j),d(i+1,j+1)}

多階段決策問題求解：d(1,1)第8講:ACM競賽之動態(tài)規(guī)劃8.1基本概念例題：數(shù)字三角形解決方法：動態(tài)規(guī)劃狀態(tài)轉移方程：d(i,j)=a(i,j)+max{d(i+1,j),d(i+1,j+1)}

方法1：遞歸計算intd(inti,intj){returna[i][j]+(i==n?0:d(i+1,j)>?d(i+1,j+1));}用直接遞歸的方法計算狀態(tài)轉移方程，效率往往十分低下。其原因是相同的子問題被重復計算了多次。第8講:ACM競賽之動態(tài)規(guī)劃8.1基本概念例題：數(shù)字三角形解決方法：動態(tài)規(guī)劃狀態(tài)轉移方程：d(i,j)=a(i,j)+max{d(i+1,j),d(i+1,j+1)}

方法2：遞推計算inti,j;for(j=1;j<=n;j++)d[n][j]=a[n][j];for(i=n-1;i>=1;i--)for(j=1;j<=i;j++)d[i][j]=a[i][j]+d[i+1][j]>?d[i+1][j+1]時間復雜度O(n2)

第8講:ACM競賽之動態(tài)規(guī)劃8.1基本概念例題：數(shù)字三角形解決方法：動態(tài)規(guī)劃狀態(tài)轉移方程：d(i,j)=a(i,j)+max{d(i+1,j),d(i+1,j+1)}

方法2：遞推計算可以用遞推發(fā)法計算狀態(tài)轉移方程，其關鍵是邊界和計算順序。在多數(shù)情況下，遞推法的時間復雜度是：狀態(tài)總數(shù)×每個狀態(tài)的決策個數(shù)×決策時間。如果不同狀態(tài)的決策個數(shù)不同，需具體問題具體分析。第8講:ACM競賽之動態(tài)規(guī)劃8.1基本概念例題：數(shù)字三角形解決方法：動態(tài)規(guī)劃狀態(tài)轉移方程：d(i,j)=a(i,j)+max{d(i+1,j),d(i+1,j+1)}

方法3：記憶化搜索intd(inti,intj){if(d[i][j]>=0)returnd[i][j];returnd[i][j]=a[i][j]+(i==n?0:d(i+1,j)>?d(i+1,j+1));}時間復雜度O(n2)

第8講:ACM競賽之動態(tài)規(guī)劃8.2DAG上的動態(tài)規(guī)劃8.2.1DAG（有向無環(huán)圖）模型例題：嵌套矩形有n個矩形，每個矩形可以用兩個整數(shù)a，b描述，表示它的長和寬。矩形X(a,b)可以嵌套在矩形Y(c,d)中當且僅當a<c,b<d（相當于把矩形X旋轉90o)。例如(1,5)可以嵌套在(6,2)內，但不能嵌套在(3,4)內。你的任務是選出盡量多的矩形排成一行，使得除了最后一個之外，每一個矩形都可以嵌套在下一個矩形內。第8講:ACM競賽之動態(tài)規(guī)劃8.2DAG上的動態(tài)規(guī)劃8.2.1DAG（有向無環(huán)圖）模型例題：硬幣問題有n種硬幣，面值分別為V1,V2,…,Vn,每種都有無限多。給定非負整數(shù)S，可以選用多少個硬幣，使得面值之和恰好為S？輸出硬幣數(shù)目的最小值和最大值。1≤n≤100，0≤S≤10000，1≤Vi≤S。第8講:ACM競賽之動態(tài)規(guī)劃8.2DAG上的動態(tài)規(guī)劃8.2.2最長路及其字典序例題：嵌套矩形有n個矩形，每個矩形可以用兩個整數(shù)a，b描述，表示它的長和寬。矩形X(a,b)可以嵌套在矩形Y(c,d)中當且僅當a<c,b<d（相當于把矩形X旋轉90o)。例如(1,5)可以嵌套在(6,2)內，但不能嵌套在(3,4)內。你的任務是選出盡量多的矩形排成一行，使得除了最后一個之外，每一個矩形都可以嵌套在下一個矩形內。狀態(tài)轉移方程d(i)=max{d(j)+1|(i,j)E}

其中：d(i)表示從結點i出發(fā)的最長路長度。第8講:ACM競賽之動態(tài)規(guī)劃8.2DAG上的動態(tài)規(guī)劃8.2.1DAG（有向無環(huán)圖）模型例題：嵌套矩形（輸出字典序最小解）#include<stdio.h>#include<string.h>#defineMAXN1010intn,G[MAXN][MAXN];intx[MAXN],y[MAXN],d[MAXN];intdp(inti){int&ans=d[i];if(ans>0)returnans;ans=1;for(intj=1;j<=n;j++)if(G[i][j])ans>?=dp(j)+1;returnans;}……第8講:ACM競賽之動態(tài)規(guī)劃8.2DAG上的動態(tài)規(guī)劃8.2.1DAG模型例題：嵌套矩形（輸出字典序最小解）#include<stdio.h>#include<string.h>#defineMAXN1010intn,G[MAXN][MAXN];intx[MAXN],y[MAXN],d[MAXN];……voidprint_ans(inti){printf("%d",i);for(intj=1;j<=n;j++)if(G[i][j]&&d[i]==d[j]+1){print_ans(j);break;}}第8講:ACM競賽之動態(tài)規(guī)劃8.2DAG上的動態(tài)規(guī)劃8.2.1DAG模型例題：嵌套矩形（輸出字典序最小解）intmain(){inti,j,ans,best;scanf("%d",&n);for(i=1;i<=n;i++){scanf("%d%d",&x[i],&y[i]);if(x[i]>y[i]){intt=x[i];x[i]=y[i];y[i]=t;}}第8講:ACM競賽之動態(tài)規(guī)劃8.2DAG上的動態(tài)規(guī)劃8.2.1DAG模型例題：嵌套矩形（輸出字典序最小解）memset(G,0,sizeof(G));for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(x[i]<x[j]&&y[i]<y[j])G[i][j]=1;ans=0;for(i=1;i<=n;i++)if(dp(i)>ans){best=i;ans=dp(i);}printf("%d\n",ans);print_ans(best);printf("\n");return0;}第8講:ACM競賽之動態(tài)規(guī)劃8.2DAG上的動態(tài)規(guī)劃8.2.3固定終點的最長路和最短路例題：硬幣問題有n種硬幣，面值分別為V1,V2,…,Vn,每種都有無限多。給定非負整數(shù)S，可以選用多少個硬幣，使得面值之和恰好為S？輸出硬幣數(shù)目的最小值和最大值。1≤n≤100，0≤S≤10000，1≤Vi≤S。狀態(tài)轉移方程硬幣數(shù)目的最小值：d(i)=min{d(S-V[i])+1}硬幣數(shù)目的最大值：d(i)=max{d(S-V[i])+1}

其中d(i)表示從結點i出發(fā)到結點0的最長路徑長度第8講:ACM競賽之動態(tài)規(guī)劃8.2DAG上的動態(tài)規(guī)劃8.2.3固定終點的最長路和最短路例題：硬幣問題（根據(jù)指標函數(shù)重建方案）#include<stdio.h>#defineMAXN105#defineINF1000000000intV[MAXN],min[MAXN],max[MAXN];intn,S;voidprint_ans(int*d,intS){for(inti=1;i<=n;i++)if(S>=V[i]&&d[S]==d[S-V[i]]+1){printf("%d",i);print_ans(d,S-V[i]);break;}}……第8講:ACM競賽之動態(tài)規(guī)劃8.2DAG上的動態(tài)規(guī)劃8.2.3固定終點的最長路和最短路例題：硬幣問題（根據(jù)指標函數(shù)重建方案）……intmain(){scanf("%d%d",&n,&S);for(inti=1;i<=n;i++)scanf("%d",&V[i]);min[0]=max[0]=0;for(inti=1;i<=S;i++){min[i]=INF;max[i]=-INF;}for(inti=1;i<=S;i++)for(intj=1;j<=n;j++)if(i>=V[j]){min[i]<?=min[i-V[j]]+1;max[i]>?=max[i-V[j]]+1;}第8講:ACM競賽之動態(tài)規(guī)劃8.2DAG上的動態(tài)規(guī)劃8.2.3固定終點的最長路和最短路例題：硬幣問題（根據(jù)指標函數(shù)重建方案）……printf("%d%d\n",min[S],max[S]);print_ans(min,S);printf("\n");print_ans(max,S);printf("\n");return0;}第8講:ACM競賽之動態(tài)規(guī)劃8.2DAG上的動態(tài)規(guī)劃8.2.3固定終點的最長路和最短路例題：硬幣問題（遞推時保存最優(yōu)決策）#include<stdio.h>#defineMAXN105#defineINF1000000000intV[MAXN],min[MAXN],max[MAXN],min_coin[MAXN],max_coin[MAXN];intn,S;voidprint_ans(int*d,intS){while(S){printf("%d",d[S]);S-=V[d[S]];}}……第8講:ACM競賽之動態(tài)規(guī)劃8.2DAG上的動態(tài)規(guī)劃8.2.3固定終點的最長路和最短路例題：硬幣問題（遞推時保存最優(yōu)決策）……intmain(){scanf("%d%d",&n,&S);for(inti=1;i<=n;i++)scanf("%d",&V[i]);min[0]=max[0]=0;for(inti=1;i<=S;i++){min[i]=INF;max[i]=-INF;}第8講:ACM競賽之動態(tài)規(guī)劃8.2DAG上的動態(tài)規(guī)劃8.2.3固定終點的最長路和最短路例題：硬幣問題（遞推時保存最優(yōu)決策）……for(inti=1;i<=S;i++)for(intj=1;j<=n;j++)if(i>=V[j]){if(min[i]>min[i-V[j]]+1){min[i]=min[i-V[j]]+1;min_coin[i]=j;}if(max[i]<max[i-V[j]]+1){max[i]=max[i-V[j]]+1;max_coin[i]=j;}}第8講:ACM競賽之動態(tài)規(guī)劃8.2DAG上的動態(tài)規(guī)劃8.2.3固定終點的最長路和最短路例題：硬幣問題（遞推時保存最優(yōu)決策）……printf("%d%d\n",min[S],max[S]);print_ans(min_coin,S);printf("\n");print_ans(max_coin,S);printf("\n");return0;}