3/3實(shí)驗(yàn)二：動(dòng)態(tài)規(guī)劃實(shí)驗(yàn)二：動(dòng)態(tài)規(guī)劃

實(shí)驗(yàn)?zāi)康模豪斫鈩?dòng)態(tài)規(guī)劃的基本思想，理解動(dòng)態(tài)規(guī)劃算法的兩個(gè)基本要素最優(yōu)子結(jié)構(gòu)性質(zhì)和子問題的重疊性質(zhì)。熟練掌握典型的動(dòng)態(tài)規(guī)劃問題。掌握動(dòng)態(tài)規(guī)劃思想分析問題的

一般方法，對(duì)較簡(jiǎn)單的問題能正確分析，設(shè)計(jì)出動(dòng)態(tài)規(guī)劃算法，并能快速編程實(shí)現(xiàn)。實(shí)驗(yàn)內(nèi)容：編程實(shí)現(xiàn)講過的例題：最長(zhǎng)公共子序列問題、投資問題等。

1．最長(zhǎng)公共子序列

一個(gè)給定序列的子序列是在該序列中刪去若干元素后得到的序列。確切地說，若給定序列X=，則另一序列Z=是X的子序列是指存在一個(gè)嚴(yán)格遞增的下標(biāo)序列，使得對(duì)于所有j=1,2,…,k有

解答如下：

a)最長(zhǎng)公共子序列的結(jié)構(gòu)

若用窮舉搜索法，耗時(shí)太長(zhǎng)，算法需要指數(shù)時(shí)間。

易證最長(zhǎng)公共子序列問題也有最優(yōu)子結(jié)構(gòu)性質(zhì)

設(shè)序列X=和Y=的一個(gè)最長(zhǎng)公共子序列Z=，則：

i.若xm=yn，則zk=xm=yn且Zk-1是Xm-1和Yn-1的最長(zhǎng)公共子序列；

ii.若xm≠yn且zk≠xm，則Z是Xm-1和Y的最長(zhǎng)公共子序列；

iii.若xm≠yn且zk≠yn，則Z是X和Yn-1的最長(zhǎng)公共子序列。

其中Xm-1=，Yn-1=，Zk-1=。

最長(zhǎng)公共子序列問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。

注意：需要輸出最長(zhǎng)公共子序列

A:備忘錄方法

B．動(dòng)態(tài)規(guī)劃算法

程序如下：

#include

#include

intlcs_length(charx[],chary[]);

intmain()

{

charx[100],y[100];

intlen;

while(1)

{

scanf("%s%s",x,y);

if(x[0]=='0')//約定第一個(gè)字符串以‘0’開始表示結(jié)束

break;

len=lcs_length(x,y);

printf("%d\n",len);

}

}

intlcs_length(charx[],chary[])

{

intm,n,i,j,l[100][100];

m=strlen(x);

n=strlen(y);

for(i=0;il[i+1][j])

l[i][j]=l[i][j-1];

else

l[i][j]=l[i-1][j];

returnl[m][n];

}

2.投資問題

?例：某公司擬將4萬元，向A、B、C三個(gè)項(xiàng)目追加投資，三個(gè)項(xiàng)目可以有不同的投資額度，相應(yīng)的效益值如表所示，問如何分配資金，才使總效益值最大？最優(yōu)值：190

?

?

A:遞歸方法（自頂向下）+備忘錄

#include

usingnamespacestd;

intValue[3][5]={47,51,59,71,76,49,52,61,71,78,46,70,76,88,88};

intMaxValue(intStage,intMoney)

{

intsplitmoney=0;

inttempmax=0;

inttemp=0;

if(Stage==1)//邊界條件

{

returnValue[0][Money];

}

for(splitmoney=0;splitmoney<=Money;splitmoney++)

{

temp=MaxValue(Stage-1,splitmoney)+Value[Stage][splitmoney];

if(tempmax<temp)

tempmax=temp;

}

returntempmax;

}

voidmain()

{

cout<<MaxValue(3,4);

}

B:動(dòng)態(tài)規(guī)劃算法（自底向上,本質(zhì)上即狀態(tài)轉(zhuǎn)移方程的非遞歸實(shí)現(xiàn)？？？）

核心偽代碼：

int

Value[3][5]={47,51,59,71,76,49,52,61,71,78,46,70,76,88,88};

intMoney=4;

intMaxValue[3][5]={0};

inttemp=0;

inttempmax=0;

for(inti=0;i<5;i++)

MaxValue[0][i]=Value[0][i];

for(intstage=2;stage<=3;stage++)

{

for(intsplitmoney=0;splitmoney<=Money;splitmoney++)

temp=MaxValue[stage][splitmoney]+