SCAU 算法设计与分析期末复习

桃扇骨 2023-10-03 17:56 29阅读 0赞

## 一、动态规划 ##

矩阵连乘问题 最长公共子序列问题 最大子段和问题 0-1背包问题

--------------------

### 1.1 矩阵连乘问题 ###

代码

// m数组保存的是最优值；s数组保存的是最优解
    void matrixChain(int *p,int n,int **m,int **s){
        
        for(int i=0;i<=n;i++)m[i][i]=0;
        for(int r=2;r<=n;r++)  //r是用来确定i需要循环的次数
            for(int i=1;i<=n-r+1;i++){
        
                int j = i+r-1; //j由i来决定
                m[i][j] = m[i+1][j] + p[i-1]*p[i]*p[j];
                s[i][j]=i;
                for(int k=i+1;k<j;k++){
        
                    int t = m[i][k] +m[k+1][j] + p[i-1]*p[k]*p[j];
                    
                    if(t<m[i][j]){
        
                        m[i][j] =t;
                        s[i][j]=k;
                    }
                }
            }
    }
    
    //输出最优次序
    void Traceback(int i,int j,int **s){
        
        if(i ==j)return;
        Traceback(i,s[i][j],s);
        Traceback(s[i][j]+1,j,s);
        cout<<"Multiply"<<i<<","<<s[i][j];
        cout<<"and A "<<s[i][j]+1<<","<<j<<endl;
    }

**总结**  
若A是p*q的矩阵，B是q*r的矩阵，则计算量是pqr次数乘

**递推关系：**  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP5rGk5rGk5rGk5rGk_size_20_color_FFFFFF_t_70_g_se_x_16]

## 1.2 最长公共子序列问题 ##

**代码**

void LCSLength(int m,int n,char *x,char *y,int **c,int **b){
        
        int i,j;
        for(i=1;i<=m;i++)c[i][0]=0;
        for(i=1;i<n;i++)c[0][i]=0;
            for(i=1;i<m;i++){
        
                for(j=1;j<=n;j++){
        
                    if(x[i]==y[i]){
        
                        c[i][j] = c[i-1][j-1]+1;
                        b[i][j]=1; //b数组用来保存由哪一个子问题得到的
                    }
                    // xi != yi
                    else if(c[i-1][j]>=c[i][j-1]){
        
                        c[i][j] = c[i-1][j];
                        b[i][j]=2;
                    }
                    else{
        
                        c[i][j] = c[i][j-1];
                        b[i][j] = 3;
                    }
                }
            }
    }
    
    //输出最长公共子序列
    void LCS(int i,int j,int *x,int **b){
        
        if(i==0||j==0)return;
        if(b[i][j]==1){
        
            LCS(i-1,j-1,x,b);
            cout<<x[i];
        } else if(b[i][j]==2)LCS(i-1,j,x,b);
        else LCS(i,j-1,x,b);
    }

**总结**  
c\[i\]\[j\]记录序列Xi和Yj的最长公共子序列的长度。  
递推方程：  
![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP5rGk5rGk5rGk5rGk_size_20_color_FFFFFF_t_70_g_se_x_16 1][]

### 1.3 最大字段和 ###

代码

int MaxSum(int n,int *a){
        
        int sum =0,b=0;
        for(int i=1;i<=n;i++){
        
            if(b>0)b+=a[i];
            else b = a[i];
            if(b>sum)sum = b;
        }
        return sum;
    }

**总结**  
当b\[j-1\]>0时b\[j\] = b\[j-1\] +a\[j\],否者b\[j\] = a\[j\]

### 1.4 0-1背包问题 ###

代码

void Knapsack(Type v,int* w,int c,int n,Type **m){
        
        int jMax = min(w[n]-1,c);
        for(int j=0;j<=jMax;j++)m[n][j] = 0;
        for(int j=w[n];j<=c;j++)m[n][j] = v[n];
        for(int i=n-1;i>1;i--){
        
            jMax = min(w[i]=1,c);
            for(int j=0;j<=jMax;j++)m[i][j] = m[i+1][j];
            for(int j=w[i];j<=c;j++)m[i][j] = max(m[i+1],m[i+1][j-w[i]]+v[i]);
        }
        m[1][c] = m[2][c];
        if(c>=w[1])m[1][c] = max[m[1][c],m[2][c-w[1]]+v[1]];
    }
    
    void Traceback(Type **m,int* w,int c,int n,int* x){
        
        for(int i=1;i<n;i++)
            if(m[i][c] ==m[i+1][c]) x[i]=0;
            else{
        
                x[i] = 1;
                c -=w[i];
            }
            x[n] = (m[n][c])?1:0;
    }

**总结**  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP5rGk5rGk5rGk5rGk_size_20_color_FFFFFF_t_70_g_se_x_16 2]

## 二、递归 ##

递归求全排列

--------------------

### 2.1 递归求全排列 ###

void Perm(Type list[], int k,int m){
        
        if(k ==m){
        
            for(int i=0;i<=m;i++)
                cout<<list[i];
            cout<<endl;
        } else
            for(int i=k;i<=m;i++){
        
                swap(list[i],list[k]);
                Perm(list,list[k+1],m);
                swap(list[i],list[k]);
            }
    }

### 2.2 整数划分问题 ###

int q(int n,int m){
        
        if(n<1||m<1)return 0;
        if(n==1||m==1)return 1;
        if(n<m)return q(n,n);
        if(n==m)return q(n,m-1)+1;
        else return q(n,m-1)+q(n-m,m);//包含m和不包含m的情况
    }

## 三、贪心算法 ##

### 3.1 活动安排问题 ###

void GreedySelector(int n,Type s[],Type f[],bool A[])
    {
        
        A[1] = true;
        int j =1;
        for(int i=2;i<=n;i++){
        
            if(s[i]>=f[j]){
        
                A[i]= true;j=i;
            } else A[i]= false;
        }
    }

### 3.2 多机调度问题 ###

/**当作业n的数量小于机器的数量m的时，只需要作业一一分配到每一台机器中，只要把机器i的[0,ti]时间区间分配给作业i即可，所需要的时间便是max[ti]。
    当作业n的数量大于机器的数量m的时，应使所有机器尽可能忙碌，首先将n个作业依其所需的处理时间从大到小排序。然后以此顺序将作业分配给空闲的处理机。*/
    
    void Greedy(Type a[],int n,int m){
        
        if(n<=m){
        
            cout<<"为为一个作业分配一台机器"<<endl;
            return;
        }
        Sort(a,n);
        MinHeap<MachineNode> H(m);
        MachineNode x;
        for(int i=2;i<=m;i++){
        
            x.avail =0;
            x.ID =i;
            H.Insert(x);
        }
        for(int i=n;i>=1;i--){
        
            H.DeleteMin(x);
            cout<<"将机器"<<x.ID<<"从"<<x.avail<<"到"<<x.avail+a[i].time<<"的时间段分配给作业"<<a[i].ID<<endl;
            x.avail +=a[i].time;
            H.Insert(x);
        }
    }

**最小堆 minheap**  
最小堆的定义是，一棵完全二叉树，每一个节点都大于等于其父节点。完全二叉树是叶子都在最后一层，且尽量靠左。

## 四、课本知识总结 ##

### 4.1 回溯法 ###

回溯法就是通过两个树（排列树或者子集树）来求的问题的最优解。

**子集树**

void Backtrack(int t) {
             //t 表示当前是树的第t层，即对集合 S 中的第 t 个元素进行判断
        if (t > n)
            output(x);          //大于S中总的元素个数 ，遍历完成 
        else
            for (int i = 0; i < = l; i++) {
             // 两种可能 加入或者不加入到解集合 
                x[t] = i;
                if (Constraint(t) && Bound(t)){
             //满足约数条件  
                        Backtrack(t + 1);           //对 t+1 层进行判断 
                    } 
            }
    }

**排列树**

void Backtrack(int t) {
            //t 表示集合 S 的第 t 个元素 
        if (t > n)
            output(x);
        else
            for (int i = t; i <= n; i++) {
           //第t 个元素与其后面的所有元素进行交换位置 
                swap(x[t], x[i]); //这里类似全排列问题
                if (constraint(t) && bound(t)){
         
                        backtrack(t + 1);
                    } 
                swap(x[t], x[i]);
            }
    }

前提是先讲变量数组的x初始化为单位排列（1，2，3，…，n）

**装载问题**（子集树）**2^n**  
1.首先将第一艘轮船尽可能装满  
2.然后将剩余的集装箱装上第二艘轮船

**批处理作业调度**（排列树）**n！**

[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP5rGk5rGk5rGk5rGk_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/efe3ad1847c44313b90b71148a286e1a.jpg?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5bCP5rGk5rGk5rGk5rGk,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP5rGk5rGk5rGk5rGk_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/5639b804c215491dba01d30a71625da4.jpg?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5bCP5rGk5rGk5rGk5rGk,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP5rGk5rGk5rGk5rGk_size_20_color_FFFFFF_t_70_g_se_x_16 2]: https://img-blog.csdnimg.cn/2701dc618b5a4350a7040162675f1996.jpg?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5bCP5rGk5rGk5rGk5rGk,size_20,color_FFFFFF,t_70,g_se,x_16