一、实验目的

1．加深学生对动态规划算法设计方法的基本思想、基本步骤、基本方法的理解与掌握；
2．提高学生利用课堂所学知识解决实际问题的能力；
3．提高学生综合应用所学知识解决实际问题的能力。

二、实验任务

1、矩阵链相乘问题

2、投资问题

3、背包问题

4、TSP问题
旅行家要旅行n个城市，要求经历各个城市且仅经历一次，然后回到出发城市，并要求所走的路程最短。
5、数字三角形
问题描述：在上面的数字三角形中寻找一条从顶部到底边的路径，使得路径上所经过的数字之和最大。路径上的每一步都只能往左下或右下走。

三、实验设备及编程开发工具

编程开发工具：Microsoft Visual c++

四、实验过程设计（算法设计过程）

（一）、矩阵链相乘问题

1 动态规划的4个步骤为：
（1）.寻找一个最优子结构。
对于原问题，我们使用表示乘积的结果矩阵，如果我们将在处进行一次括号划分，假设将其划分为和两部分，则=++(两个划分矩阵合并的代价)。假设这样划分是最优的，则只需继续在和上继续取到最佳划分即可。
（2）. 递归地定义最优解的值
在原问题中，我们定义数组m[i][j]表示计算矩阵所需乘法的最小值，则原问题计算所需最小代价为m[1][n]。
如果k表示矩阵i到j之间的划分点，那么m数组的公式为：

（3）.计算最优代价
如果直接递归计算的话，我们会发现计算量仍然会很大，并没有明显改善。因此在这里，我们使用自底向上的方法进行计算，并且在计算中保存已经计算过的值，这样当上一层划分计算时，直接调用下层之前计算保存过的值即可。
在这整个过程中，我们使用m[i][j]从矩阵i到j的最小代价，用s[i][j]保存最小代价时的划分位置。根据2步骤的公式，我们只需按链条长度递增的顺序进行求解即可。在这里，它的长度是从2到n的(长度为1时直接为0)。由于只知道链的长度，因此有多个乘法问题，因此我们需要求解出所有乘法问题的最小代价。
（4).构造最优解
2 源程序

#include<stdio.h>
#include<string.h>
#define N 1000
int m[N][N];//m[i][j]表示从第i个矩阵乘到第j个矩阵所需的最小代价
int s[N][N];  //s[i][j]表示最优值m[i][j]对应的分割点
int p[N];     //p[]代表矩阵链

void MATRIX_CHAIN_ORDER(int p[], int n) //对矩阵链p求解最佳组合方法
{
    for(int i = 1; i <= n; i++) //子问题链长1时代价为0
        m[i][i] = 0;
    //对子问题链长2到n从小到大求出代价
    for(int length = 2; length <= n; length++) //枚举子问题链长
    {
        //在对应链长下求出所有情况
        for(int i = 1; i <= n-length+1; i++)  //所有情况的开始位置
        {
            int j = i+length-1;
            m[i][j] = 999999;   //此时求出从i到j的最小代价m[i][j]=min{m[i][k]+m[k+1][j]+Pi-1*Pk*Pj}
            for(int k = i; k <= j-1; k++)
            {
                if(m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j] < m[i][j])
                {
                    m[i][j] = m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
                    s[i][j] = k;
                }
            }
        }
    }
}

void PRINT_OPTIMAL_PARENS(int s[][N], int start, int ends)//利用表s输出从start乘到ends的最优方案
{
    if(start == ends)
        printf("A[%d]", start);
    else
    {
        printf("(");
        PRINT_OPTIMAL_PARENS(s, start, s[start][ends]);
        PRINT_OPTIMAL_PARENS(s, s[start][ends]+1, ends);
        printf(")");
    }
}

int main()
{
    int number;
    printf("请输入待乘矩阵的个数:\n");
    while(scanf("%d",&number) && number>0)
    {
        memset(m, 0, sizeof(m));
        memset(p, 0, sizeof(p));
        printf("请输入矩阵链:\n");
        for(int i = 0; i <= number; i++)
            scanf("%d", &p[i]);
        MATRIX_CHAIN_ORDER(p, number);
        PRINT_OPTIMAL_PARENS(s, 1, number);
        printf("\n");
        printf("请输入待乘矩阵的个数:\n");
    }
    return 0;
}

（二）、投资问题

1 算法分析
根据题目要求的项目个数，将解题思路分为项目数个阶段：
第一阶段：只考虑第一个项目，即将所有的资金都投资给该项目,那么此时可以获取的利益可以计算出来；
第二阶段：将第二个项目加进去，即投资的资金可以同时分配给两个项目，那么此时可以获取的利益可以计算出来；
第三阶段：将第三个项目加进去，即投资的资金可以同时分配给三个项目，同样可以用上述方法得到此时能获取的利益。
后面以此类推。
2 源程序

 #include<stdio.h> 
#include<conio.h>
 void main() 
{      
void jie(int,int,int d[][6]);     
void Invest(int m,int n,int f[][6],int g[][6],int d[][6]);    
int m=5,n=4,f[5][6],d[5][6];   
int g[5][6]={{0},{0,11,12,13,14,15},
{0,0,5,10,15,20},{0,2,10,30,32,40},{0,20,21,22,23,24}};     
Invest(m,n,f,g,d);     
printf("可获得的最大收益为：%d\n",f[4][5]);     
jie(m,n,d); 
 
} 
 void Invest(int m,int n,int f[][6],int g[][6],int d[][6]) 
{   
int i,j,k,s;  
for(j=0;j<=m;j++)       
{    
f[1][j]=g[1][j];d[1][j]=j;}
           for(i=2;i<=n;i++)               
 for(j=0;j<=m;j++)                  
{    f[i][j]=0;                      
for(k=0;k<=j;k++)                      
 { 
s=f[i-1][j-k]+g[i][k];                           if(s>f[i][j])     
{   
f[i][j]=s;  d[i][j]=k;  
}                     
  }               
 }    
}  

void jie(int m,int n,int d[][6])
{  
int s=m;  int k[5];  
int i;  
k[n]=d[n][m];  
for(i=n-1;i>0;i--)  
{        
 s = s-k[i+1];        
k[i] = d[i][s];  
}  

for(i=1;i<=4;i++)   
printf("%5d",k[i]);  
printf("\n");    
 getch();
 }         

（三）、背包问题

1 算法过程

#include <iostream>  
#include <cstring>  
using namespace std;

const int N = 150;
char t[N] = {'A','B','C','D'};
int v[N] = { 0, 12, 8, 9, 5 };
int w[N] = { 0, 15, 10, 12, 8 };
int x[N];
int m[N][N];
int c = 30;
int n = 4;
void traceback()
{
	for (int i = n; i>1; i--)
	{
		if (m[i][c] == m[i - 1][c])
			x[i] = 0;
		else
		{
			x[i] = 1;
			c -= w[i];
		}
	}
	x[1] = (m[1][c]>0) ? 1 : 0;
}

int main()
{
	memset(m, 0, sizeof(m));
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= c; j++)
		{
			if (j >= w[i])
			if (m[i - 1][j]> m[i - 1][j - w[i]] + v[i])
				m[i][j] = m[i - 1][j];
			else 
				m[i][j] = m[i - 1][j - w[i]] + v[i];
			else
				m[i][j] = m[i - 1][j];
		}
	}/*
	 for(int i=1;i<=6;i++)
	 {
	 for(int j=1;j<=c;j++)
	 {
	 cout<<m[i][j]<<' ';
	 }
	 cout<<endl;
	 }
	 */
		printf("项目  ");
		for (int q = 0; q < 4; q++)
		{
			printf("   %c",t[q]);
		}
		
		printf("\n");
		printf("投资额");

		for (int q = 1; q < 5; q++)
		{
			printf("%4d", v[q]);
		}
		
		printf("\n");
		printf("收益  ");
	
		for (int q = 1; q < 5; q++)
		{
			printf("%4d", w[q]);
		}
		printf("\n");
	traceback();
	cout << "项目选择结果是：" ;
	for (int i = 1; i <= n; i++)
		cout <<"   "<< x[i];
		cout << endl;
	system("pause");
	return 0;
}

(四)TSP问题

1 动态规划解决方法
假定我们从城市1出发，经过了一些地方，并到达了城市j。毋庸置疑，我们需要记录的信息有当前的城市j。同时我们还需要记录已经走过的城市的集合。同理，使用S记录未走过的城市的集合也可以的，且运算方便。
于是我们可以得出状态转移方程 go(S,init)=min{go(S−i,i)+dp[i][init]}∀s∈Sgo(S,init)=min{go(S−i,i)+dp[i][init]}∀s∈S go(s,init)表示从init点开始，要经过s集合中的所有点的距离
因为是NP问题，所以时间复杂度通常比较大。使用dis[s][init]用来去重，初始化为-1，如果已经计算过init—>S（递归形式），则直接返回即可.
2 源程序

#include<iostream>
#include<cmath> 
#include<iomanip>
using namespace std;
int s;
int N;//点的个数 
int init_point;
double x[20];
double y[20];
double dp[20][20];//两个城市的距离 
double dis[1048577][20];//2^20=1048576 表示出发点到S集合是否已经访问过 
double go(int s,int init)
{
    if(dis[s][init]!=-1) return dis[s][init];//去重 
    if(s==(1<<(N-1))) return dp[N-1][init];//只有最后一个点返回 
    double minlen=100000;
    for(int i=0;i<N-1;i++)//只能在1到n-2点中查找 
    {
        if(s&(1<<i))//如果i点在s中且不为发出点 
        {
            if(go(s&(~(1<<i)),i)+dp[i][init]<minlen)
                minlen=go(s&(~(1<<i)),i)+dp[i][init];
        } 
    } 
    return dis[s][init]=minlen;
}
int main()
{
    int T;
    cin>>T;
    while(T--)//测试样例数 
    {
        cin>>N;
        for(int i=0;i<N;i++)
            cin>>x[i]>>y[i];//读入城市的坐标 
        for(int i=0;i<N;i++)
            for(int j=0;j<N;j++)
            {
                dp[i][j]=sqrt(pow((x[i]-x[j]),2)+pow((y[i]-y[j]),2));
                //计算两个城市的距离 
            }   

        for(int i=0;i<pow(2,N);i++)
            for(int j=0;j<N;j++)
                dis[i][j]=-1;//去重数组初始化  
        init_point=0;
        s=0; 
        for(int i=1;i<N;i++)
            s=s|(1<<i);//从1开始，保证初始点没有在S里面           
        double distance=go(s,init_point);
        cout<<fixed<<setprecision(2)<<distance<<endl;

    }       
} 

（五）数字三角形

1 动态规划解决问题
设 d( i , j )表示数字三角形中的第 i 行第 j 个点。　max[i][j]表示 第 i 行 第 j 个数字到低端的最佳路径之和，则原问题的解就是 max[1][1] 的值了。
　　从d( i,j )这个点向下走，显然只能走 d( i+1,j ) 和 d( i+1 ,j+1 ) 这两个点了。
　　而 max[i][j] 的最优值= d( i,j) 的值 + max{ max[i+1][j] ，max[i+1][j+1] }。
　　所以，我们可以至底向上来计算。先计算最后一层的点的，然后倒二层的，一直算到第一层。
2 源程序

#include <stdlib.h>
int main()
{
	int n, a[101][101], d[101][101], i, j, k;
	scanf_s("%d", &n);
	for (i = 1; i <= n; i++)
	for (j = 1; j <= i; j++)
		scanf_s("%d", &d[i][j]);
	for (j = 1; j <= n; j++)
		a[n][j] = d[n][j];//从最后一行开始；
	for (i = n - 1; i >= 1; i--)
	for (j = 1; j <= i; j++)
	{
		if (a[i + 1][j + 1]>a[i + 1][j]) a[i][j] = d[i][j] + a[i + 1][j + 1];
		else
			a[i][j] = d[i][j] + a[i + 1][j];
	}
	printf("%d\n", a[1][1]);
	system("pause");
	return 0;
}

五、实验结果及算法复杂度分析

（一） 矩阵链相乘问题
1 实验结果

2 算法复杂度分析
计算时间复杂度为：
$$\begin{gathered} O(1+1+2+\dots +1+2+\dots +(N-1)) \\ =O(\sum n=1N-1\sum r=1nr) \\ =O(\sum n=1N-1(n+1)n2) \\ =O(\sum n=1N-1n2+\sum n=1N-1n) \\ =O(N3) \end{gathered}$$

（二）投资最少问题
1 实验结果

2 算法复杂度分析
时间复杂度为O（nC）,把一个多维决策问题转化为多个一维最优化问题，能求出全局极大或者极小，但是缺点在于空间占据过多。

（三）背包问题
1 实验结果

2 算法复杂度分析
时间复杂度为O（n），每次循环都需要进行比较，

（四）TSP问题
1 实验结果

2 算法复杂度

(五) 数字三角形
1 实验结果

2 算法复杂度
动态规划将计算过的数值保存，再次要用的时候直接取就可以大大减少计算次数，得出时间复杂度就是$O（n）=n^2$

实验小结（包括问题和解决方法、心得体会等）

通过实现动态规划的这些题目，对动态规划算法有了进一步的了解，先分析问题，判断是否具有最优子结果和重叠字问题的性质。动态规划算法是由单阶段的决策最优逐步转化为多阶段的决策最优，最后构造一个最优解。经过反复的调试操作，程序运行才得出结果。