ACM競(jìng)賽之動(dòng)態(tài)規(guī)劃

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

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

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

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

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

方法2：遞推計(jì)算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]時(shí)間復(fù)雜度O(n2)

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

方法2：遞推計(jì)算可以用遞推發(fā)法計(jì)算狀態(tài)轉(zhuǎn)移方程，其關(guān)鍵是邊界和計(jì)算順序。在多數(shù)情況下，遞推法的時(shí)間復(fù)雜度是：狀態(tài)總數(shù)×每個(gè)狀態(tài)的決策個(gè)數(shù)×決策時(shí)間。如果不同狀態(tài)的決策個(gè)數(shù)不同，需具體問題具體分析。第8講:ACM競(jìng)賽之動(dòng)態(tài)規(guī)劃8.1基本概念例題：數(shù)字三角形解決方法：動(dòng)態(tài)規(guī)劃狀態(tài)轉(zhuǎn)移方程：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));}時(shí)間復(fù)雜度O(n2)

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

其中：d(i)表示從結(jié)點(diǎn)i出發(fā)的最長(zhǎng)路長(zhǎng)度。第8講:ACM競(jìng)賽之動(dòng)態(tài)規(guī)劃8.2DAG上的動(dòng)態(tài)規(guī)劃8.2.1DAG（有向無(wú)環(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競(jìng)賽之動(dòng)態(tài)規(guī)劃8.2DAG上的動(dòng)態(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競(jìng)賽之動(dòng)態(tài)規(guī)劃8.2DAG上的動(dòng)態(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競(jìng)賽之動(dòng)態(tài)規(guī)劃8.2DAG上的動(dòng)態(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競(jìng)賽之動(dòng)態(tài)規(guī)劃8.2DAG上的動(dòng)態(tài)規(guī)劃8.2.3固定終點(diǎn)的最長(zhǎng)路和最短路例題：硬幣問題有n種硬幣，面值分別為V1,V2,…,Vn,每種都有無(wú)限多。給定非負(fù)整數(shù)S，可以選用多少個(gè)硬幣，使得面值之和恰好為S？輸出硬幣數(shù)目的最小值和最大值。1≤n≤100，0≤S≤10000，1≤Vi≤S。狀態(tài)轉(zhuǎn)移方程硬幣數(shù)目的最小值：d(i)=min{d(S-V[i])+1}硬幣數(shù)目的最大值：d(i)=max{d(S-V[i])+1}

其中d(i)表示從結(jié)點(diǎn)i出發(fā)到結(jié)點(diǎn)0的最長(zhǎng)路徑長(zhǎng)度第8講:ACM競(jìng)賽之動(dòng)態(tài)規(guī)劃8.2DAG上的動(dòng)態(tài)規(guī)劃8.2.3固定終點(diǎn)的最長(zhǎng)路和最短路例題：硬幣問題（根據(jù)指標(biāo)函數(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競(jìng)賽之動(dòng)態(tài)規(guī)劃8.2DAG上的動(dòng)態(tài)規(guī)劃8.2.3固定終點(diǎn)的最長(zhǎng)路和最短路例題：硬幣問題（根據(jù)指標(biāo)函數(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競(jìng)賽之動(dòng)態(tài)規(guī)劃8.2DAG上的動(dòng)態(tài)規(guī)劃8.2.3固定終點(diǎn)的最長(zhǎng)路和最短路例題：硬幣問題（根據(jù)指標(biāo)函數(shù)重建方案）……printf("%d%d\n",min[S],max[S]);print_ans(min,S);printf("\n");print_ans(max,S);printf("\n");return0;}第8講:ACM競(jìng)賽之動(dòng)態(tài)規(guī)劃8.2DAG上的動(dòng)態(tài)規(guī)劃8.2.3固定終點(diǎn)的最長(zhǎng)路和最短路例題：硬幣問題（遞推時(shí)保存最優(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競(jìng)賽之動(dòng)態(tài)規(guī)劃8.2DAG上的動(dòng)態(tài)規(guī)劃8.2.3固定終點(diǎn)的最長(zhǎng)路和最短路例題：硬幣問題（遞推時(shí)保存最優(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競(jìng)賽之動(dòng)態(tài)規(guī)劃8.2DAG上的動(dòng)態(tài)規(guī)劃8.2.3固定終點(diǎn)的最長(zhǎng)路和最短路例題：硬幣問題（遞推時(shí)保存最優(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競(jìng)賽之動(dòng)態(tài)規(guī)劃8.2DAG上的動(dòng)態(tài)規(guī)劃8.2.3固定終點(diǎn)的最長(zhǎng)路和最短路例題：硬幣問題（遞推時(shí)保存最優(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;}