算法描述：动态规划

动态规划算法步骤：

• 找出最优解的性质，刻画数据结构
• 递归定义最优值
• 自底向上计算出各子结构的最优值并添入表格中并保存
• 以最优值构造最优解

最长公共子序列

递归结构：

int LCSlength(char*a,char*b,int**len,int**flag)
//a,b输入字符串，输出数组len的元素len[i][j]记录len(i,j),
//数组flag在求a、b的最长公共子序列时作为标志使用
//flag[i][j]=0 表示lcs(ai,bj)=lcs(ai-1,bj-1)||a[i],a[i]=b[j]
//flag[i][j]=1 表示lcs(ai,bj)=lcs(ai-1,bj)
//flag[i][j]=-1 表示lcs(ai,bj)=lcs(a,bj-1)
{
    n = strlen(a);m=strlen(b);
    for(int i =1;i<=n;i++)len[i][0]=0;
    for(int i =1;i<=m;i++)len[0][i]=0;
    for(int i =1;i<=n;i++)
      for(int j =1;j<=m;j++)
       {
          if(a[i]==b[j])
              {
                   len[i][j]=len[i-1][j-1]+1;
                   flag[i][j]=0;

              }
          else if(len[i-1][j] >= len[i][j-1])       
                 {
                      len[i][j] = len[i-1][j];
                      flag =1;
                 }
          else{
                len[i][j]=len[i][j-1];
                flag[i][j]=-1;
              }
     return(len[n][m]);
}

机器分配

描述

总公司拥有高效设备M台，准备分给下属的N个分公司。各分公司若获得这些设备，可以为国家提供一定的盈利。问：如何分配这M台设备才能使国家得到的盈利最大？求出最大盈利值。其中M≤15，N≤10。分配原则：每个公司有权获得任意数目的设备，但总台数不超过设备数M.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<queue>
#include<vector>
#define INF 0x3f3f3f3f
#define N 30
#define MOD 2520
#define E 1e-12
using namespace std;
int a[N][N],f[N][N],res[N][N];
void print(int x,int y)
{
     if(x==0)
          return;
     print(x-1,y-res[x][y]);
     printf("%d %d\n",x,res[x][y]);
}
int main(){
      int n ,m;
      cin>>n>>m;
      for(int i =1;i<=n;i++) 
         for(int j =1;j<=m;j++)
              cin>>a[i][j];
      for(int i=1;i<=n;i++)
          for(int j =1;j<=m;j++)
              for(int k =0;k<=j;k++)
                   if(f[i][j] <=f[i-1][j-k]+a[i][k])
                    {
                         f[i][j]= f[i-1][j-k]+a[i][k];
                          res[i][j]=k;
                     }
       cout<<f[n][m]<<endl;
       print(n,m);
       return 0;
}

与分治法相比，都是分解为若干的子问题再递归求解，但是动态规划的子问题彼此并不独立。

能应用动态规划求解的问题应具有最优子结构性质。