目录

• • 实验环境
  • 动态规划
  • • 使用动态规划的特征
  • 1.矩阵连乘问题
  • • 问题描述
    • 解题思路
  • 2.剪绳子问题
  • • 问题描述
    • 解题思路
  • 3.国王和金矿
  • • 问题描述
    • 解题思路
  • 4.最长公共子序列
  • • 问题描述
    • 解题思路

实验环境

Windows 10+DEV-C++

动态规划

动态规划问题是算法设计与分析中的热门话题，如果要求一个问题最优解（通常是最大值或者最小值），而且该问题能够分解成若干个问题，并且小问题之间也存在重叠的子问题，则考虑采用动态规划。

使用动态规划的特征

使用动态规划特征：

1. 求一个问题的最优解
2. 大问题可以分解为子问题，子问题还有重叠的更小的子问题
3. 整体问题最优解取决于子问题的最优解（状态转移方程）
4. 从上往下分析问题，从下往上解决问题
5. 讨论底层的边界问题

1.矩阵连乘问题

问题描述

给定n个矩阵｛A1,A2,…,An｝，其中Ai与Ai+1是可乘的，i=1,2 ,…,n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。例如：
A1={30x35} ;A2={35x15} ;A3={15x5} ;A4={5x10} ;A5={10x20} ;A6={20x25} ;
最后的结果为：((A1(A2A3))((A4A5)A6)) 最小的乘次为15125。

解题思路

能用动态规划的一个性质就是最优子结构性质，也就是说计算A[i:j]的最优次序所包含的计算矩阵子琏A[i:k]和A[k+1:j]的次序也是最优的。动态规划算法解此问题，可依据其递归式以自底向上的方式进行计算（即先从最小的开始计算）。在计算过程中，保存已解决的子问题答案。每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算，最终得到多项式时间的算法。我们可以根据下面这个公式来计算结果。其中p[i-1]表示的是第i个矩阵的行数,p[k]表示i:k矩阵合起来后最后得到的列数，p[j]是k+1:j合起来后得到的列数。这个部分的计算方法其实就是计算两个矩阵相乘时总共的乘次数。

#include<iostream>
using namespace std;
 
const int N=7;
//p为矩阵链，p[0],p[1]代表第一个矩阵的行数和列数，p[1],p[2]代表第二个矩阵的行数和列数......length为p的长度
//所以如果有六个矩阵，length=7，m为存储最优结果的二维矩阵，s为存储选择最优结果路线的
//二维矩阵
void MatrixChainOrder(int *p,int m[N][N],int s[N][N],int length)
{
    int n=length-1;
    int l,i,j,k,q=0;
    //m[i][i]只有一个矩阵，所以相乘次数为0，即m[i][i]=0;
    for(i=1;i<length;i++)
    {
        m[i][i]=0;
    }
    //l表示矩阵链的长度
    // l=2时，计算 m[i,i+1],i=1,2,...,n-1 (长度l=2的链的最小代价)
    for(l=2;l<=n;l++)
    {
        for(i=1;i<=n-l+1;i++)
        {
            j=i+l-1; //以i为起始位置，j为长度为l的链的末位，
            m[i][j]=0x7fffffff;
            //k从i到j-1,以k为位置划分
            for(k=i;k<=j-1;k++)
            {
                q=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
                if(q<m[i][j])
                {
                    m[i][j]=q;
                    s[i][j]=k;
                }
            }
        }
    }
    cout << m[1][N-1] << endl;
}
void PrintAnswer(int s[N][N],int i,int j)
{
    if(i==j)
    {
        cout<<"A"<<i;
    }
    else
    {
        cout<<"(";
        PrintAnswer(s,i,s[i][j]);
        PrintAnswer(s,s[i][j]+1,j);
        cout<<")";
    }
}
int main()
{
    int p[N]={30,35,15,5,10,20,25};
    int m[N][N],s[N][N];
    MatrixChainOrder(p,m,s,N);
    PrintAnswer(s,1,N-1);
    return 0;
}

2.剪绳子问题

问题描述

给你一根长度为n的绳子，请把绳子剪成m段（m,n都是整数），每段绳子的 长度记为k[0],k[1],k[2]…. 请问如何剪绳子使得k[0],k[1],k[2] 的乘积最大
例如 绳子长度n=8 最大乘积18 = 233 剪成了m=3段。

解题思路

采用自底向上的动态规划方法。设f(n)代表长度为n的绳子剪成若干段的最大乘积，如果第一刀下去，第一段长度是i，那么剩下的就需要剪n-i，那么f(n)=max{f(i)f(n-i)}。而f(n)的最优解对应着f(i)和f(n-i)的最优解，假如f(i)不是最优解，那么其最优解和f(n-i)乘积肯定大于f(n)的最优解，和f(n)达到最优解矛盾，所以f(n)的最优解对应着f(i)和f(n-i)的最优解。
首先，剪绳子是最优解问题，其次，大问题包含小问题，并且大问题的最优解包含着小问题的最优解，所以可以使用动态规划求解问题，并且从小到大求解，把小问题的最优解记录在数组中，求大问题最优解时就可以直接获取，避免重复计算。
n<2时，由于每次至少剪一次，所以返回0。n=2时，只能剪成两个1，那么返回1。n=3时，可以剪成3个1，或者1和2，那么最大乘积是2。当n>3时，就可以使用公式进行求解。
f(4)=max{f(1)f(3), f(2)f(2)}
f(5)=max{f(1)f(4), f(2)f(3)}
…
f(n)=max{f(1)f(n-1), f(2)f(n-2), f(3)f(n-3), …, f(i)(fn-i), …} (0<i<=n/2)

#include <stdio.h>

int maxrope(int length){
	if(length < 2){ //如果绳子不足两米，不能剪，为0 
		return 0;
	}
	if(length == 2){ //如果绳子两米，则1*1 
		return 1;
	}
	if (length == 3){//如果绳子三米，则1*2 
		return 2;
	}
	if (length ==4){ //如果绳子四米，则2*2  
		return 4;
	}
int *products = new  int[length+1];
int max = 0;
int product = 0;
products[0] = 0; //剪断后一部分绳子为0米，则为0 
products[1] = 1;//剪断后一部分绳子为1米，则为1 
products[2] = 2;//剪断后一部分绳子为2米，则最优解为不把2米剪开 
products[3] = 3;//剪断后一部分绳子为3米，则最优解为不把3米剪开  
for(int i = 4;i < length+1;i++){
	max = 0;
	for (int j = 1;j <= i/2;j++){
		product = products[j] * products[i-j]; //j米最优解和i-j米最优解相乘 
		if (product > max){
			max = product;  
		}
	}
	products[i] = max;
}
return products[length];
}

int main(){
	int length = 0;
	printf("请输入绳子的长度："); 
	scanf("%d",&length); 
	printf("剪绳子问题的最优解为：");
	printf("%d",maxrope(length)); 
}

3.国王和金矿

问题描述

有一个国家发现了5座金矿，每座金矿的黄金储量不同，需要参与挖掘的工人数也不同。参与挖矿工人的总数是10人。每座金矿要么全挖，要么不挖，不能派出一半人挖取一半金矿。要求用程序求解出，要想得到尽可能多的黄金，应该选择挖取哪几座金矿？

解题思路

我们将金矿设为N，工人数设为W，金矿的黄金量设为数组G，金矿的用工量设为数组P。
状态转移方程：

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

int Goldbest(int w,int length,int p[],int g[]){
	int result[length+1][w+1]={0}; //result[金矿数][工人数]
	
	memset(result,0,sizeof result);
	
	for(int i = 1;i < length+1; i++){ //第i个金矿 
		for(int j=1;j < w+1; j++){  //分到的w个工人 
			if(j < p[i-1]){ //如果分到的工人数达不到第i个金矿的要求，result[i][j]延续上一个金矿i-1的结果 
				result[i][j] = result[i-1][j];
			}
			else{ //如果分到的人数够了，从（把j个人分给前i-1个金矿获得的金子）和（除去满足第i个金矿挖矿人数剩下人去挖前i-1个矿获得的金子数 ）中选择最大值 
				result[i][j]=max(result[i-1][j],result[i-1][j-p[i-1]]+g[i-1]);
			}
		}
	} 
	return result[length][w];
}

int main(){
	int g[5] = {500,200,300,350,400};
	int p[5] = {5,3,4,3,5};
	int length = 5;
	int w = 10;
	printf("能挖到最多的金矿为%d金",Goldbest(w,length,p,g));
}

4.最长公共子序列

问题描述

给定两个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最长公共子序列。
例如：X={A,B,C,B,D,A,B}, Y={B,D,C,A,B,A} 则序列{B,C,A}是X和Y的一个公共子序列。但它不是X和Y的一个最长公共子序列。序列{B,C,B,A}是X和Y的一个公共子序列，它的长度是4，而且它是X和Y的一个最长公共子序列。因为，X和Y没有长度大于4的公共子序列。它的另一个解是{B,C,A,B}。该问题的答案不唯一。

解题思路

由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用c[i][j]记录序列Xi和Yj的最长公共子序列的长度。其中， Xi={x1,x2,…,xi}；Yj={y1,y2,…,yj}。当i=0或j=0时，空序列是Xi和Yj的最长公共子序列。故此时C[i][j]=0。其它情况下，由最优子结构性质可建立递归关系如下：

#include<iostream>
#include<cmath>
#include<cstring>

using namespace std;
int main()
{
    char x[50],y[50],z[50];
    int l[51][51];
    int k = 0;
    while(scanf("%s %s",x+1,y+1)!=EOF){ //输入两个字符串 
        memset(l,0,sizeof(l));
        int m = strlen(x+1);
        int n = strlen(y+1);
 
        for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++){
            if(x[i]==y[j]){
                l[i][j] = l[i-1][j-1]+1;
                
            }else{
                l[i][j] = max(l[i-1][j],l[i][j-1]);
            }
 
        }
         printf("最长公共子序列的长度为%d\n",l[m][n]);
         
    }
    return 0;
}