算法分析与设计课程复习之动态规划

算法分析与设计课程复习之动态规划

一、基本思想

将待求解问题分解成若干个子问题。保存已解决的子问题的答案。

二、动态规划和分治法的区别

分治法是把大问题分解成一些相互独立的子问题，递归的求解这些子问题然后将他们合并来得到整个问题的解。分治法是自顶向下
动态规划是通过组合子问题的解来解决整个大问题。各个子问题不是独立的，也就是各个子问题包含公共子问题。它可以避免遇到的子问题的重复求解。动态规划法是自底向上

三、动态规划算法的基本要素

• 最优子结构
• 重叠子问题

四、动态规划解法的基本步骤

1. 找出最优解的性质，并刻划其结构特征。

2. 递归地定义最优值。

3. 以自底向上的方式计算出最优值。

4. 根据计算最优值时得到的信息，构造最优解

五、经典问题

1.背包问题(0-1背包)

设U = {u1,u2,. . . ,un}是一个准备放入容量为C的背包中的n项物品的集合。对于1 ≤ j ≤ n1。，令sj, 和vj分别为第j项物品的体积和价值，这里， C ， sj，vj和j都是正整数
要解决的问题是用U中的一些物品来装满背包，这些物品的总体积不超过C，然而要使它们的总价值最大。

#include
using namespace std;
const int MAXN = 1005;
int v[MAXN];    // 体积
int w[MAXN];    // 价值 
int f[MAXN][MAXN];  // f[i][j], j体积下前i个物品的最大价值 

int main() 
{
    int n, m;   
    cin >> n >> m;
    for(int i = 1; i <= n; i++) 
        cin >> v[i] >> w[i];

    for(int i = 1; i <= n; i++) 
        for(int j = 1; j <= m; j++)
        {
            //  当前背包容量装不进第i个物品，则价值等于前i-1个物品
            if(j < v[i]) 
                f[i][j] = f[i - 1][j];
            // 能装，需进行决策是否选择第i个物品
            else    
                f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
        }           

    cout << f[n][m] << endl;

    return 0;
}

2.最长公共子序列（求出长度和值）

给定两个序列A = a1, a2, …,an and B = b1, b2, …, bm ，并希望找到A和B中的最长公共子序列以及序列长度。

设序列A={a1,a2,…,an}和B={b1,b2,…,bm}的最长公共子序列为C={c1,c2,…,ck} ，则
(1)若an=bm，则ck=an=bm，且Ck-1是An-1和Bm-1的最长公共子序列。
(2)若an≠bm且ck≠an, 则C是An-1和B的最长公共子序列。
(3)若an≠bm且ck≠bm，则C是A和Bn-1的最长公共子序列。

#include 
using namespace std;
const int N = 1010;
int n, m;
char a[N], b[N];
int f[N][N];//用来存最长公共子序列的长度
int temp[N];//用来存最长公共子序列的值
int k;//temp数组的下标
int main() {
  cin >> n >> m >> a + 1 >> b + 1;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      if (a[i] == b[j]) {
        f[i][j] = f[i - 1][j - 1] + 1;//相等的话直接长度加1
      } else {
        f[i][j] = max(f[i - 1][j], f[i][j - 1]);//不相等的话是原来最大的长度
      }
    }
  }
   //恢复最长公共序列，这里从a串还原最长公共子序列
   int l1=n,l2=m;
   while(l1!=0&&l2!=0)
   {
     if(f[l1][l2]!=f[l1-1][l2])//此时a[i]一定包含在最长公共子序列中
     {
       temp[++k]=a[l1];
       l1--;//继续判断a串中的前一个字符
       l2--;//不管b[j]来自那个哪个表达式，b[j]都已经判断过了
     }
      else if(f[l1][l2]==f[l1][l2-1])l2--;//当f[i][j]来自f[i][j-1]，说明b[j]不在最长公共子序列中
      else l1--;//说明a[i]不在最长公共子序列中
    }
  cout << f[n][m] <=1;i--)
  {
    cout< 
3.Floyd算法（求最短路径）
 
初始化：
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            if (i == j) d[i][j] = 0;
            else d[i][j] = INF;

// 算法结束后，d[a][b]表示a到b的最短距离
void floyd()
{
    for (int k = 1; k <= n; k ++ )
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
 
4.完全背包问题
 
有 N 种物品和一个容量是 V 的背包，每种物品都有无限件可用。
 
第 i 种物品的体积是 vi，价值是 wi。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。
 
#include
using namespace std;
const int N = 1010;
int f[N][N];
int v[N],w[N];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i = 1 ; i <= n ;i ++)
    {
        cin>>v[i]>>w[i];
    }
    //i表示物品，j表示总体积，k表示个数
    for(int i = 1 ; i<=n ;i++)
    for(int j = 0 ; j<=m ;j++)
    {
        for(int k = 0 ; k*v[i]<=j ; k++)
            f[i][j] = max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
    }
    //f[i-1][j-k*v[i]]+k*w[i]表示选择第i个物品后的总价值
    cout< 
5.硬币找零问题（完全背包问题）
 
给定 n 种不同面值的硬币，分别记为 c[0], c[1], c[2], … c[n]，假设每种硬币的数量是无限的。同时还有一个总金额 k，编写一个动态规划计算出最少需要几枚硬币凑出这个金额 k？
 
#include 
#include 
using namespace std;
const int N =1e2+10;
int sum;
int v[N];
int n;
int dp[N];
int main()
{
    cin>>sum;
    int x;
    while(cin>>x)
    {
        v[++n]=x;
        if(cin.get()=='n')break;
    }
    for(int i=0;i<=sum;i++)dp[i]=N;//初始化
    dp[0]=0;//当金额为0时，需要的硬币数量为0
    for(int i=1;i<=sum;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(v[j]<=i)//硬币价值小于当前价值
                dp[i]=min(dp[i],dp[i-v[j]]+1);
        }
    }
    cout< 
类比完全背包问题的解法：
 
#include 
#include 
using namespace std;
const int N =1e2+10;
int sum;
int v[N];
int n;
int dp[N][N];
int main()
{
    cin>>sum;
    int x;
    while(cin>>x)
    {
        v[++n]=x;
        if(cin.get()=='n')break;
    }
    //初始化操作，当金额为0时，dp赋值为0
    for(int i=0;i<=n;i++)
    {
        for(int j=1;j<=sum;j++)
        {
            dp[i][j]=N;
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=sum;j++)
        {
            for(int k=0;k*v[i]<=j;k++)
            {
                dp[i][j]=min(dp[i][j],dp[i-1][j-k*v[i]]+k);
            }
        }
    }
    cout< 
6.矩阵链相乘
 详细可参考：矩阵链相乘
 问题描述：给定n个矩阵{A1,A2,…,An}，其中Ai与Ai+1是可乘的，i=1,2,…,n-1。要算出这n个矩阵的连乘积A1A2…An。
 
解法：将矩阵连乘积A(i)A(i+1)…A(j)简记为A[i:j]
 A[i:j](1 <= i <= j <= n)所需要的最少数乘次数m[i,j]，则原问题的最优值为m[1,n]
 当i = j时，A[i:j]=Ai，因此，m[i,i] = 0，i = 1,2,…,n
 当i < j时，m[i,j] = m[i,k] + m[k+1,j] + p(i-1)p(k)p(j)
 这里A(i)的维数为p(i-1)*p (i)(注：p(i-1)为矩阵A(i)的行数，p(j)为矩阵A[j]的列数)
 
void MATRIX_CHAIN_ORDER(int p[],int Length,int m[][M],int s[][M])
{
	int q,n=Length-1;
	for(int i=1;i<=n;i++) m[i][i]=0;//初始化处理
	for(int l=2;l<=n;l++) 	// 矩阵链的长度 
	{
		for(int i=1;i<=n-l+1;i++) 
		{
			int j=i+l-1;         
			m[i][j]=INT_MAX;
			for(int k=i;k<=j-1;k++)
			{
				q=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
				if(q 
7.双机流水作业调度问题
 设有n个作业的集合{0，1，…，n-1}，每个作业都有两项任务要求在2台设备P1和P2组成的流水线上完成加工。每个作业加工的顺序总是先在P1上加工，然后在P2上加工。P1和P2加工作业i所需的时间分别为ai和bi。流水作业调度问题要求确定这n个作业的最优加工顺序，使得从第一个作业在设备P1上开始加工，到最后一个作业在设备P2上加工完成所需的时间最少。即求使F(S)有最小值的调度方案S。
 流水作业调度问题的Johnson算法：
 (1)令N1={i|ai=bi};
 (2)将N1中作业按ai的 非减序排序；将N2中作业按bi的非增序排序；
 (3)N1中作业接N2中作业构成满足Johnson法则的最优调度。
 
#include
#include 
using namespace std;
const int N = 100;
struct node
{
 int time;//执行时间
 int index;//作业序号
 bool group;//1代表第一个机器，0代表第二个机器
};
bool cmp(node a,node b)
{//升序排序
 return a.time>n;
 for(int i=0;i>a[i]>>b[i];
 }
 for(int i=0;ib[i]?b[i]:a[i];
     c[i].index=i;
     c[i].group=a[i]