算法设计与分析动态规划实验

袂

实

验

5

动

态

规

划

实

验

肀

羇0

肆A

蚄C

膀B

莈C

螈D

蒃A

蒃B

蝿D

芆0

蒆0

薃0

芀0

羈0

芅0

蚃0

蚁0

蒆0

肄0

螃A

螈0

膈1

螃1

袃1

腿1

薅1

袆2

羃2

蕿2

莇B

薄0

肃1

羀1

螅2

莃2

肃2

肇2

蒇3

膂3

膂D

蒈0

羅1

膅1

节1

衿1

蚇2

羄2

莂2

芀3

膅C

蚃0

蒂1

蚁2

袇2

螆3

薂3

袈3

薈3

蒄3

蚂A

芈0

羆2

芃2

蚂2

虿2

螈2

肂3

螂3

肀3

膆B

肅0

袁2

膇2

袈3

袄3

羁3

薈3

莆4

蚃4

肁A

罿0

肈3

蚆3

膁3

莀3

薆3

蒅4

芁4

螁4

羇#include<iostream>

蚅#include<string>

羂#include<iomanip>

莁using namespace std;

莈

莇int dp[1000][1000];

羅string str1,str2,s1,s2;

蒁

蝿int max(int a,int b,int c)

袅{

螄 if(a>b && a>c)

薀 return a;

膀 if(b>a && b>c)

薇 return b;

薃 if(c>a && c>b)

蚀 return c;

薁}

肅

薆int lcs(int len1,int len2)

螀{

蚈 memset(dp,0,sizeof(dp));

螇 int i,j,x;

莅 dp[0][1]=0;

袀 dp[1][0]=0;

聿 dp[1][1]=0;

葿 dp[0][0]=0;

肄 for(i=2;i<len1+2;i++)

袀 {

蒀 dp[i][1]=-2*(i-1);

羆 }

袂 for(j=2;j<len2+2;j++)

羀 {

袀 dp[1][j]=-2*(j-1);

蚈 }

羅 for(j=2;j<len2+2;j++)

肀 {

羇 for(i=2;i<len1+2;i++)

肆 {

蚄 if(str1[i-2]==str2[j-2])

膀 x=dp[i-1][j-1]+5;

莈 else

螈 x=dp[i-1][j-1]-1;

蒃 dp[i][j]=max(x,dp[i-1][j]-2,dp[i][j-1]-2);

蒃 }

蝿 }

芆 return dp[i-1][j-1];

蒆}

薃

芀void print(int len1,int len2)

羈{

芅 int i,j;

蚃 i=len1+1;

蚁 j=len2+1;

蒆 while(i>1 && j>1)

肄 {

螃 if(dp[i][j]+2==dp[i-1][j])

螈 {

膈 s2=s2+'_';

螃 s1=s1+str1[i-2];

袃 i--;

腿 continue;

薅

袆 }

羃 if(dp[i][j]+2==dp[i][j-1])

蕿 {

莇 s1=s1+'_';

薄 s2=s2+str2[j-2];

肃 j--;

羀 continue;

螅 }

莃 if(dp[i][j]+1==dp[i-1][j-1] || dp[i][j]-5==dp[i-1][j-1])

肃 {

肇

蒇 s1=s1+str1[i-2];

膂 s2=s2+str2[j-2];

膂 j--;

蒈 i--;

羅 continue;

膅 }

节 }

衿 for(i=len1-1;i>=0;i--)

蚇 {

羄 cout<<s1[i];

莂 }

芀 cout<<endl;

膅 for(j=len1-1;j>=0;j--)

蚃 {

蒂 cout<<s2[j];

蚁 }

袇 cout<<endl;

螆}

薂

int main()
{
int len1,len2;
while(cin>>str1>>str2)
{
len1=str1.size();
len2=str2.size();
cout<<lcs(len1,len2)<<endl;
for(int i=1;i<=len1+1;i++)
{
for(int j=1;j<=len2+1;j++)
{
cout<<setw(5)<<dp[i][j]<<" "; }
cout<<endl;
}
print(len1,len2);

}
return 0;
}

w

v

4

8

6

10

2

6

2

3

5

7

1

2

#include<stdio.h>

int c[10][100];/*对应每种情况的最大价值*/

int knapsack(int m,int n)

{

int i,j,w[10],p[10];

printf("请输入每个物品的重量,价值：\n");

for(i=1;i<=n;i++)

scanf("%d,%d",&w[i],&p[i]);

for(i=0;i<10;i++)

for(j=0;j<100;j++)

c[i][j]=0;/*初始化数组*/

for(i=1;i<=n;i++)

for(j=1;j<=m;j++)

{

if(w[i]<=j) /*如果当前物品的容量小于背包容量*/

{

if(p[i]+c[i-1][j-w[i]]>c[i-1][j])

/*如果本物品的价值加上背包剩下的空间能放的物品的价值

*/

/*大于上一次选择的最佳方案则更新c[i][j]*/

c[i][j]=p[i]+c[i-1][j-w[i]];

else

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

}

else c[i][j]=c[i-1][j];

}

return(c[n][m]);

}

int main()

{

int m,n;int i,j;

printf("请输入背包的承重量,物品的总个数：\n");

scanf("%d,%d",&m,&n);

printf("旅行者背包能装的最大总价值为%d",knapsack(m,n));

printf("\n");

return 0;

}

Project

Wk

Vk

A

15

12

B

10

8

C

12

9

D

8

5