算法-基础

yuiyake 12/9/2021

# 第一章算法引论

# 算法与程序

算法五大特性：输入，输出，有穷性，确定性，可行性
算法描述方法
- 自然语言
- 流程图
- 程序设计语言
- 伪代码
重要问题类型
- 查找问题（顺序，二叉树查找，串匹配查找）
- 排序问题（合并排序，快排，堆排）
- 图问题（最小生成树，图着色）
- 组合问题（背包，滑动窗口，哈夫曼编码，最长公共子序列，八皇后）
- 几何问题（最近对问题）

# 复杂性分析

时间复杂性，需要时间资源的量
空间复杂性，需要空间资源的量

# 第二章递归与分治

# 递归概念

定义：递归即调用自身函数
分类：直接递归和间接递归
优缺点
- 优：简化程序设计，使程序易读
- 缺：系统开销大（指内存）
适合递归求解：
1. 有初始状态
2. 后续情况可以由前面状态推
解决的问题：
- Fibonacci数列
- Ackerman函数
- 排列问题（perm）
- 整数划分问题
- Hanoi塔问题

# 分治

-思想

将一个规模为n的问题分解为k个规模较小的子问题, 这些子问题互相独立且与原问题相同，可分别求解。递归地解这些子问题，然后将各个子问题的解合并得到原问题的解。
用分治法的特征
1. 问题的规模缩小到一定程度时容易解决；
2. 问题可以分解为若干个规模较小的类型相同问题
3. 问题所分解出的各个子问题是相互独立的，
4. 子问题的解可以合并为原问题的解。
解决的问题：
- 二分搜索
- Strassen矩阵乘法
- 棋盘覆盖（分成4份）
- 合并排序
- 快速排序
- 最接近点对问题
- 循环赛日程表

# 第三章动态规划

# 求解步骤

步骤
1. 找出最优解性质，刻画结构特征
2. 递归地定义最优值
3. 自底向上计算出最优值
4. 构造最优解

# 基本要素

适用于求解最优化问题
基本要素：
- 最优子结构性质
- 子问题重叠性质
解决问题模式：自底向上

# 满足DP求解问题的特征：

分解多个重叠子问题
满足最优解原理（最优子结构性质）

# 最长公共子序列

题目：最长公共子序列问题：给定2个序列X={x1 , x2 , … , xm}和Y={y1 , y2 , … , yn}，找出X和Y的最长公共子序列。

  int CommonOrder(int m, int n, int x[ ], int y[ ], int z[ ])
     {
        for (j=0; j<=n; j++)   //初始化第0行
           L[0][j]=0;
        for (i=0; j<=m; i++)   //初始化第0列
           L[i][0]=0;
        for (i=1; i<=m; i++)
           for (j=1; j<=n; j++)
              if (x[i]= =y[j]) { L[i][j]=L[i-1][j-1]+1; S[i][j]=1; }
             else if (L[i][j-1]>=L[i-1][j]) { L[i][j]=L[i][j-1]; S[i][j]=2; }
                    else {L[i][j]=L[i-1][j]; S[i][j]=3; }
        i=m; j=n; k=L[m][n];
        for (i>0 && j>0)
       {
           if (S[i][j]= =1) { z[k]=x[i]; k--; i--; j--; }
          else if (S[i][j]= =2) j--;
                 else i--;
       }
       return L[m][n];
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

时间复杂度O(m*n)

# 0-1背包问题

0-1背包问题：给定n个物体和一个背包。物体 i 的重量为wi >0 ，价值为vi >0 , wi , vi >0 , 均为整数。背包的容量为整数C >0 。问应如何选择装入背包的物体，使得装入背包中物体的总重量不超过容量C ，且总价值最大?
设n个物品的重量存储在数组w[n]中，价值存储在数组v[n]中，背包容量为C，数组V[n+1][C+1]存放迭代结果，其中V[i][j]表示前i个物品装入容量为j的背包中获得的最大价值，数组x[n]存储装入背包的物品，动态规划法求解0/1背包问题的算法如下：

   int KnapSack(int n, int w[ ], int v[ ]) {
       for (i=0; i<=n; i++)   //初始化第0列
           V[i][0]=0;
       for (j=0; j<=C; j++)   //初始化第0行
           V[0][j]=0;
       for (i=1; i<=n; i++)   //计算第i行，进行第i次迭代
           for (j=1; j<=C; j++)
              if (j<w[i])   V[i][j]=V[i-1][j];         
              else   V[i][j]=max(V[i-1][j], V[i-1][j-w[i]]+v[i]);
  
       j=C;    //求装入背包的物品
       for (i=n; i>0; i--){
           if (V[i][j]>V[i-1][j]) {
              x[i]=1;
              j=j-w[i];
           }
           else x[i]=0;
       }
       return V[n][C];    //返回背包取得的最大价值
  }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

时间复杂度：O(n2^n)

# 最优二叉搜索树

设n个字符的查找概率存储在数组p[n]中，动态规划法求解最优二叉查找树的算法如下：

    double OptimalBST(int n, double p[ ], double C[ ][ ], int R[ ][ ] )
    {
      for (i=1; i<=n; i++)  //按式6.17和式6.18初始化
      {
         C[i][i-1]=0;
         C[i][i]=p[i];
         R[i][i]=i;
      }
      C[n+1][n]=0;
      for (d=1; d<n; d++)     //按对角线逐条计算
          for (i=1; i<=n-d; i++)
          {
              j=i+d;
              min=∞; mink=i; sum=0;
              for (k=i; k<=j; k++)
             {
                 sum=sum+p[k];
                 if (C[i][k-1]+C[k+1][j]<min) {
                    min=C[i][k-1]+C[k+1][j];
                    mink=k;
                 }
              }
              C[i][j]=min+sum;
              R[i][j]=mink;
           }
           return C[1][n];
      }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

时间复杂度：O(n^3)

# 图中的动态规划

TSP

TSP问题是指旅行家要旅行n个城市，要求各个城市经历且仅经历一次然后回到出发城市，并要求所走的路程最短。各个城市间的距离可以用代价矩阵来表示。
设顶点之间的代价存放在数组c[n][n]中，动态规划法求解TSP问题的算法如下：

  1．for (i=1; i<n; i++)     //初始化第0列
        d[i][0]=c[i][0]; 
  2．for (j=1; j<2n-1-1; j++)  
  for (i=1; i<n; i++)   //依次进行第i次迭代
  if (子集V[j]中不包含i)
  对V[j]中的每个元素k，计算d[i][j]=min(c[i][k]+d[k][j-1]);
  3．对V[2n-1-1]中的每一个元素k，
  计算d[0][2n-1-1]=min(c[0][k]+d[k][2n-1-2]);
  4．输出最短路径长度d[0][2n-1-1];

1
2
3
4
5
6
7
8
9

多断图的最短路径
- W先生每天驾车去公司上班。W先生的住所位于A，公司位于F，图中的直线段代表公路，交叉点代表路口，直线段上的数字代表两路口之间的平均行驶时间。现在W先生的问题是要确定一条最省时的上班路线。
- 用一个数组cost[n]作为存储子问题解的表格，cost[i]表示从顶点i到终点n-1的最短路径，数组path[n]存储状态，path[i]表示从顶点i到终点n-1的路径上顶点i的下一个顶点。则：
- cost[i]=min{cij+cost[j]} (i≤j≤n且顶点j是顶点i的邻接点)（式6.7）
- path[i]=使cij+cost[j]最小的j式6.8）
```
  1．初始化：数组cost[n]初始化为最大值，数组path[n]初始化为-1；
  2．for (i=n-2; i>=0; i--)
      2.1 对顶点i的每一个邻接点j，根据式6.7计算cost[i];
      2.2 根据式6.8计算path[i];
  3．输出最短路径长度cost[0];
  4. 输出最短路径经过的顶点：
      4.1  i=0
      4.2 循环直到path[i]=n-1
          4.2.1 输出path[i];
          4.2.2  i=path[i];
```
1
2
3
4
5
6
7
8
9
10
- 时间复杂度O(n+m)

# 第四章贪心算法

设计思想
- 贪心只能解决局部最优并不能求得整体最优解，但通常能获得***近似最优解***
特征：
- 最优子结构性质
- 贪心选择性质
解决问题模式：自顶向下

# （普通）01背包[算法knapsack]

时间上界O(nlogn)
设背包容量为C，共有n个物品，物品重量存放在数组w[n]中，价值存放在数组v[n]中，问题的解存放在数组x[n]中。

  public static float knapsack(float c,float [] w, float [] v,float [] x)
     {
        int n=v.length;
        Element [] d = new Element [n];
        for (int i = 0; i < n; i++) d[i] = new Element(w[i],v[i],i);
        MergeSort.mergeSort(d);
        int i;
        float opt=0;
        for (i=0;i<n;i++) x[i]=0;
        for (i=0;i<n;i++) {
          if (d[i].w>c) break;
          x[d[i].i]=1;
          opt+=d[i].v;
          c-=d[i].w;
          }
        if (i<n){
          x[d[i].i]=c/d[i].w;
          opt+=x[d[i].i]*d[i].v;
          }
        return opt;
     }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

# 最优装载（loading算法）

题目：有一批集装箱要装上一艘载重量为c的轮船。其中集装箱i的重量为Wi。最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。
- element类见书P115
- 时间复杂度：O(nlogn)

  public static float loading(float c, float [] w, int [] x)
     {
        int n=w.length;
        Element [] d = new Element [n];
        for (int i = 0; i < n; i++)
          d[i] = new Element(w[i],i);
        MergeSort.mergeSort(d);
        float opt=0;
        for (int i = 0; i < n; i++) x[i] = 0;
        for (int i = 0; i < n && d[i].w <= c; i++) {
           x[d[i].i] = 1;
           opt+=d[i].w;
           c -= d[i].w;
           }
        return opt;
     }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 哈夫曼编码

时间复杂度O(nlogn)
哈夫曼提出构造最优前缀码的贪心算法，由此产生的编码方案称为哈夫曼编码。
时间复杂度：O(nlogn)

  ？代码消失了

# Dijk最短路径

给定带权有向图G =(V,E)，其中每条边的权是非负实数。另外，还给定V中的一个顶点，称为源。现在要计算从源到所有其它各顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。

  奇怪的代码消失了

# 最小生成树（Prim & Kruskal）

prim算法

基本思想：S={1}, 只要S是V的真子集，就去i属于S，j属于V-S，且c[i][j]最小的边，将顶点j添加到S中，直到S=V。即从任意顶点开始，每一步为这棵树添加一个分枝，直到生成树中包含全部顶点。（简单地把不在生成树中的最近顶点添加到生成树中。）
时间复杂度：O(n^2)

  1. 初始化两个辅助数组lowcost和adjvex；
  2. U={u0}; 输出顶点u0;    //将顶点u0加入生成树中
  3. 重复执行下列操作n-1次
       3.1 在lowcost中选取最短边，取adjvex中对应的顶点序号k；
       3.2 输出顶点k和对应的权值；
       3.3 U=U+{k}；
       3.4 调整数组lowcost和adjvex；

1
2
3
4
5
6
7
8

kruskal算法
- 基本思想：最短边策略：设G=(V，E)是一个无向连通网，令T=(U，TE)是G的最小生成树。最短边策略从TE={}开始，每一次贪心选择都是在边集E中选取最短边(u, v)，如果边(u, v) 加入集合TE中不产生回路，则将边(u, v)加入边集TE中，并将它在集合E中删去。
- 它使生成树以一种随意的方式生长，先让森林中的树木随意生长，每生长一次就将两棵树合并，到最后合并成一棵树。
- 时间复杂度：O(elog2e)
```
  1. 初始化：U=V；  TE={ }；
  2. 循环直到T中的连通分量个数为1  
     2.1 在E中寻找最短边(u，v);
     2.2 如果顶点u、v位于T的两个不同连通分量，则
     2.2.1 将边(u，v)并入TE；
     2.2.2 将这两个连通分量合为一个；
     2.3  E=E-{(u，v)}；
```
1
2
3
4
5
6
7
8

# 多机调度问题

多机调度问题要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。
设有n个独立的作业{1, 2, …, n}，由m台相同的机器{M1, M2, …, Mm}进行加工处理，作业i所需的处理时间为ti（1≤i≤n），每个作业均可在任何一台机器上加工处理，但不可间断、拆分。多机调度问题要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。

变量语义：

t[n]：n个作业的处理时间；
p[n]：n个作业的序号；
d[m]：m台机器的空闲时间（从什么时候开始空闲）；
S[m]：每台机器所处理的作业。

1．将数组t[n]由大到小排序，对应的作业序号存储在数组p[n]中；
2．将数组d[m]初始化为0；
3．for (i=1; i<=m; i++) //将m个作业分配给m个机器
3.1 S[i]={p[i]};   
3.2 d[i]=t[i];
4.  for (i=m+1; i<=n; i++)
    4.1  j=数组d[m]中最小值对应的下标；  //j为最先空闲的机器序号
    4.2  S[j]=S[j]+{p[i]};   //将作业i分配给最先空闲的机器j
    4.3  d[j]=d[j]+t[i];      //机器j将在d[j]后空闲

1
2
3
4
5
6
7
8
9

# 第五章回溯

# 概念

具有限界函数的深度优先生成法称为回溯法
以深度优先方式搜索解空间，过程中用***剪枝函数避免无效搜索***
常用剪枝函数：用约束函数在扩展结点处剪去不满足约束的子树，用限界函数剪去得不到最优解的子树。
分递归回溯和迭代回溯

# 子集树与排列树

# 01背包（子集树）

时间复杂度：O(2^n)

  private static double bound(int i)
     {// 计算上界
        double cleft = c - cw;   // 剩余容量
        double bound = cp;
        // 以物品单位重量价值递减序装入物品
        while (i <= n &&  w[i] <= cleft)
        {
           cleft -= w[i];
           bound += p[i];
           i++;
        }
        // 装满背包
        if (i <= n)     bound += p[i] / w[i] * cleft;
        return bound;
     }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 八皇后问题（n后）

在8×8的棋盘上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上。

   void Queue(int n)
   {
       for (i=1; i<=n; i++)    //初始化
          x[i]=0;
       k=1;
       while (k>=1)
       {
            x[k]=x[k]+1;     //在下一列放置第k个皇后
            while (x[k]<=n && !Place(k)) //若有冲突
                 x[k]=x[k]+1;     //搜索下一列
            if (x[k]<=n && k= =n) {   //得到一个解，输出
                 for (i=1; i<=n; i++)  
                     输出x[i];
                 return;
            } 
            else if (x[k]<=n && k<n)
                  k=k+1;      //放置下一个皇后
            else {      
                x[k]=0;     //重置x[k]，回溯
                k=k-1;
            }
       }
   }
   bool Place(int k)   //考察皇后k放置在x[k]列是否发生冲突
    {
         for (i=1; i<k; i++)   
             if (x[k]= =x[i] | | abs(k-i)= =abs(x[k]-x[i])) 
                 return false;
             return true;
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

# 图的m着色问题

给定无向连通图G=(V, E)和正整数m，判断能否用m种颜色对G中的顶点着色，使得任意两个相邻顶点着色不同。
设数组color[n]表示顶点的着色情况，回溯法求解m着色问题的算法如下：

  1.将数组color[n]初始化为0；
  2.k=1;
  3.while (k>=1)
    3.1 依次考察每一种颜色，若顶点k的着色与其他顶点的着色不发生冲突，则转步骤3.2；否则，搜索下一个颜色；
    3.2 若顶点已全部着色，则输出数组color[n]，返回；
    3.3 否则，
      3.3.1 若顶点k是一个合法着色，则k=k+1，转步骤3处理下一个顶点;  
      3.3.2 否则，重置顶点k的着色情况，k=k-1，转步骤3回溯；
      
  void GraphColor(int n, int c[ ][ ], int m)  
    //所有数组下标从1开始
  { 
       for (i=1; i<=n; i++ )     //将数组color[n]初始化为0
         color[i]=0;
       k=1;
       while (k>=1)
       {
          color[k]=color[k]+1;
          while (color[k]<=m)
            if Ok(k) break;   //判断顶点k的着色是否发生冲突
            else color[k]=color[k]+1;   //搜索下一个颜色
          if (color[k]<=m && k= =n) //求解完毕，输出解
          {
               for (i=1; i<=n; i++)
                   输出color[i];
               return; 
          }
           else if (color[k]<=m && k<n) 
                  k=k+1;             //处理下一个顶点
              else {
                   color[k]=0;
                   k=k-1;    //回溯
              }
       }
  }

   bool Ok(int k)   //判断顶点k的着色是否发生冲突
  {
       for (i=1; i<k; i++) 
          if (c[k][i]= =1 && color[i]= =color[k])
               return false;
      return true;
  }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

# 旅行售货员问题（TSP）（backtrack算法）（排列树）

某售货员要到若干城市去推销商品，已知各城市之间的路程，他要选定一条从驻地出发，经过每个城市一遍，最后回到住地的路线，使总的路程最短。
时间复杂度：O(n!)

private static void backtrack(int i) {
      if (i == n) {
         if (a[x[n - 1]][x[n]] < Float.MAX_VALUE && a[x[n]][1] < Float.MAX_VALUE &&
        (bestc == Float.MAX_VALUE || cc+a[x[n - 1]][x[n]]+a[x[n]][1]<bestc))  {
            for (int j = 1; j <= n; j++)  bestx[j] = x[j];
            bestc = cc+a[x[n - 1]][x[n]]+a[x[n]][1];
         }
      }  else  {
         for (int j = i; j <= n; j++)
            // 是否可进入x[j]子树?
            if (a[x[i - 1]][x[j]] < Float.MAX_VALUE &&
            (bestc == Float.MAX_VALUE ||  cc+a[x[i - 1]][x[j]]<bestc))  {// 搜索子树
               MyMath.swap(x, i, j);
               cc+=a[x[i - 1]][x[i]];
               backtrack(i + 1);
               cc-=a[x[i - 1]][x[i]];
               MyMath.swap(x, i, j);
            }
   }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# 哈密尔顿回路问题

题目：
时间复杂度：

   1．将顶点数组x[n]初始化为0，标志数组visited[n]初始化为0；
   2．k=1; visited[1]=1; x[0]=1;从顶点1出发构造哈密顿回路；
   3．while (k>=1)
         3.1 x[k]=x[k]+1，搜索下一个顶点;
         3.2 若(n个顶点没有被穷举) 执行下列操作
                3.2.1 若(顶点x[k]不在哈密顿回路上&&(x[k-1],x[k])∈E)，
                          转步骤3.3;
                3.2.2 否则，x[k]=x[k]+1，搜索下一个顶点；
         3.3 若数组x[n]已形成哈密顿路径，则输出数组x[n]，算法结束；
         3.4 否则，
                3.4.1 若数组x[n]构成哈密顿路径的部分解，
                          则k=k+1，转步骤3；
                3.4.2 否则，重置x[k]，k=k-1，取消顶点x[k]的访问标志，
                         转步骤3；
                         
  void Hamiton(int n, int x[ ], int c[ ][ ])
   //所有数组下标从1开始
  {
     for (i=1; i<=n; i++)   //初始化顶点数组和标志数组
     {
        x[i]=0;
        visited[i]=0;
     }
     visited[1]=1; x[0]=1;  //从顶点1出发
     k=1; 
     while (k>=1)
    {
       x[k]=x[k]+1;   //搜索下一顶点
       while (x[k]<=n)
       if (visited[x[k]]= =0 && c[x[k-1]][x[k]]= =1) 
           break;
       else x[k]=x[k]+1;
       
       if (x[k]<=n && k= =n && c[x[k]][1]= =1) {
             for (k=1; k<=n; k++ )  
                 cout<<x[k];
             return;
       }
      else if (x[k]<=n && k<n ) {
                  visited[x[k]]=1; 
                  k=k+1;
      }
      else {            //回溯
         x[k]=0; 
         visited[x[k]]=0;    
         k=k-1;   
      }
    }
  }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

# 批处理作业调度问题

题目：n个作业{1, 2, …, n}要在两台机器上处理，每个作业必须先由机器1处理，然后再由机器2 处理，机器1处理作业i所需时间为ai，机器2处理作业i所需时间为bi（1≤i≤n），批处理作业调度问题要求确定这n个作业的最优处理顺序，使得从第1个作业在机器1上处理开始，到最后一个作业在机器2上处理结束所需时间最少。

  void BatchJob(int n, int a[ ], int b[ ], int &bestTime)  
  {  //数组x存储具体的作业调度，下标从1开始；
     //数组sum1存储机器1上完成作业所需的时间，
     //sum2存储机器2上完成作业所需的时间，下标从0开始
    //a[n]存储作业在机器1上的处理时间，已知
    //b[n]存储作业在机器2上的处理时间，已知 
      for (i=1; i<=n; i++)
     {
        x[i]=0;      sum1[i]=0;      sum2[i]=0;
     }
     sum1[0]=0; sum2[0]=0;    //初始迭代使用
     k=1; bestTime=1000; //从第1个任务开始处理
      while (k>=1){
         x[k]=x[k]+1;
         while (x[k]<=n){
           if (Ok(k)) {  //如果任务k还没被处理过
              sum1[k]=sum1[k-1]+a[x[k]];
              sum2[k]=max(sum1[k], sum2[k-1])+b[x[k]];
              if (sum2[k]<bestTime) break;
              else x[k]=x[k]+1;   
           }
           else x[k]=x[k]+1;   
         }
         if (x[k]<=n && k<n) 
             k=k+1;         //安排下一个作业
         else {
             if (x[k]<=n && k= =n)       //得到一个作业安排
                 if (bestTime>sum2[k])
                    bestTime=sum2[k];
             x[k]=0;         //重置x[k]，回溯
             k=k-1;
         }
      }
  }
  bool Ok(int k)     //作业k与其他作业是否发生冲突（重复）
  {
     for (i=1; i<k; i++)
        if (x[i]= =x[k]) return false;
     return true;
  }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

# 第六章分支限界法

# 概念

分支限界与回溯的不同：
- 求解目标不同
- 搜索方式不同（广度优先or最小耗费优先）
以最小耗费（最大效益）或者广度优先的方式搜索问题的解空间树。
- 队列式分支限界（FIFO）
- 优先队列分支限界
确定目标函数的界，以广度优先遍历问题的解空间树。
分支限界法的一般过程：

  1．根据限界函数确定目标函数的界[down, up]；
  2．将待处理结点表PT初始化为空；
  3．对根结点的每个孩子结点x执行下列操作
        3.1 估算结点x的目标函数值value;
        3.2 若(value>=down)，则将结点x加入表PT中；
  4．循环直到某个叶子结点的目标函数值在表PT中最大
        4.1  i=表PT中值最大的结点；
        4.2 对结点i的每个孩子结点x执行下列操作
             4.2.1 估算结点x的目标函数值value;
             4.2.2 若(value>=down)，则将结点x加入表PT中；
             4.2.3 若(结点x是叶子结点且结点x的value值在表PT中最大)，
                      则将结点x对应的解输出，算法结束；
             4.2.4 若(结点x是叶子结点但结点x的value值在表PT中不是最大)，
                      则令down=value，并且将表PT中所有小于value的结点删除；

1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 01背包问题

空间复杂度：指数阶

  // 上界函数
  while (i <= n && w[i] <= cleft)       // n表示物品总数，cleft为剩余空间
        {
           cleft -= w[i];                            //w[i]表示i所占空间
           b += p[i];                                 //p[i]表示i的价值
           i++;
        }
  if (i <= n) b += p[i] / w[i] * cleft;    // 装填剩余容量装满背包
  return b;                                       //b为上界函数
  
   while (i != n + 1)
   {// 非叶结点
           double wt = cw + w[i];
           if (wt <= c)
           {// 左儿子结点为可行结点
              if (cp + p[i] > bestp)         bestp = cp + p[i];
              addLiveNode(up,cp + p[i],cw + w[i],i + 1, enode, true);
           }
           up = bound(i + 1);
           if (up >= bestp)   //检查右儿子节点
           addLiveNode(up,cp,cw,i + 1, enode, false);
           //   取下一个扩展节点（略）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# TSP问题（旅行售货员）

    1．根据限界函数计算目标函数的下界down；采用贪心法得到上界up；
    2．将待处理结点表PT初始化为空；
    3．for (i=1; i<=n; i++)
             x[i]=0;
    4．k=1; x[1]=1;  //从顶点1出发求解TSP问题
    5．while (k>=1)
          5.1 i=k+1;
          5.2 x[i]=1;
          5.3 while (x[i]<=n)
               5.3.1 如果路径上顶点不重复，则
                       5.3.1.1 根据式9.2计算目标函数值lb；
                       5.3.1.2 if (lb<=up) 将路径上的顶点和lb值存储在表PT中；
               5.3.2 x[i]=x[i]+1;
         5.4 若i=n且叶子结点的目标函数值在表PT中最小
               则将该叶子结点对应的最优解输出；
         5.5否则，若i=n，则在表PT中取叶子结点的目标函数值最小的结点lb，
               令up=lb，将表PT中目标函数值lb超出up的结点删除；
         5.6 k=表PT中lb最小的路径上顶点个数；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

yuiyake

算法-基础

算法-基础

# 第一章 算法引论

# 算法与程序

# 复杂性分析

# 第二章 递归与分治

# 递归概念

# 分治

# 第三章 动态规划

# 求解步骤

# 基本要素

# 满足DP求解问题的特征：

# 最长公共子序列

# 0-1背包问题

# 最优二叉搜索树

# 图中的动态规划

# 第四章 贪心算法

# （普通）01背包[算法knapsack]

# 最优装载（loading算法）

# 哈夫曼编码

# Dijk最短路径

# 最小生成树（Prim & Kruskal）

# 多机调度问题

# 第五章 回溯

# 概念

# 子集树与排列树

# 01背包（子集树）

# 八皇后问题（n后）

# 图的m着色问题

# 旅行售货员问题（TSP）（backtrack算法）（排列树）

# 哈密尔顿回路问题

# 批处理作业调度问题

# 第六章 分支限界法

# 概念

# 01背包问题

# TSP问题（旅行售货员）

# 第一章算法引论

# 第二章递归与分治

# 第三章动态规划

# 第四章贪心算法

# 第五章回溯

# 第六章分支限界法