第十四章 算法

1.回溯法(搜索算法)

深度优先

n皇后问题：
在棋盘上摆放n个皇后
任意两个皇后不在同一行，同一列，同一斜线

非递归求解N皇后

/*
按行摆放
判断同一列：Qₓ列 == Qᵧ列
判断同一斜线：|Qₓ行 - Qᵧ行| == |Qₓ列 - Qᵧ列|
方案1：2，4，1，3
方案2：3，1，4，2
*/
#include <stdio.h>
#include <math.h>#define N 4//4皇后

int q[N + 1];//存储皇后的序号

int check(int j) { 
  //检查第j个皇后的位置是否合法    
  int i;    
  for(i = 1; i < j; i++) {         
    if(q[i] == q[j] || abs(i - j) == abs(q[i] - q[j])) {            
      //判断皇后是否在同一行，同一斜线上            
      //q[i]表示第i个皇后在第i行上的第q[i]列上            
      //i行，q[i]列            
      return 0;        
    }    
  }    
  return 1;
}

void queen() { //求解N皇后方案    
  int i;    
  for(i = 1; i < N; i++) {        
    q[i] = 0;//表示皇后还没有摆放在棋盘上    
  }    
  int answer = 0;//方案数    
  
  int j = 1;//开始摆放第j个皇后    
  while(j >= 1) {        
    q[j] = q[j] + 1;
    //让第j个皇后向后摆放一列   
         
    while(q[j] <= N && !check(j)) { 
      //判断第j个皇后的位置是否合法            
      q[j] = q[j] + 1;
      //不合法就向后一个摆放        
    }        
    
    if(q[j] <= N) { //位置合法            
      if(j == N) { //找到了一组解                 
        answer = answer + 1;                
        printf("方案%d：",answer);                
        for(i = 1; i <= N; i++) {                    
          printf("%d",q[i]);                
        }                
        printf("\n");            
      } else {                
        j = j + 1;//继续摆放下一个皇后            
      }        
    } else { //找不到合法的位置            
      q[j] = 0;//还原第j个皇后的位置            
      j = j - 1;//回溯到上一个皇后的位置        
    }    
  }
}

int main() {    
  queen();   
   
  return 0;
}

递归求解N皇后(栈)

#include <stdio.h>
#include <math.h>

#define N 4

int answer = 0;
int q[N + 1];

int check(int j) { //检查第j个皇后的位置是否合法    
  int i;    
  for(i = 1; i < j; i++) {        
    if(q[i] == q[j] || abs(i - j) == abs(q[i] - q[j])) {            
      //判断皇后是否在同一行，同一斜线上            
      //q[i]表示第i个皇后在第i行上的第q[i]列上            
      //i行，q[i]列            
      return 0;        
    }    
  }    
  return 1;
}

void queen(int j){    
  int i;    
  //当i超出N时，跳出循环，回到上一个皇后    
  for(i = 1;i <= N;i++){        
    q[j] = i;      
      
    //皇后位置不合法时，不进入循环，执行i++，将皇后往后放                
    if(check(j)){
      //皇后摆放位置合法            
      if(j == N){//找到一组解                
        answer = answer + 1;                
        printf("方案%d：",answer);   
                                   
        for(i = 1;i <= N;i++){                    
          printf("%d",q[i]);                
        }                
        printf("\n");            
      }else{                
        queen(j + 1);
        //递归摆放下一个皇后的位置            
      }        
    }    
  }
}

int main(){    
  queen(1);     
     
  return 0;
}

2.分治法

1.递归：
直接调用或间接调用自己
两个要素：边界条件(递归出口)，递归要素(递归体)

2.分治法：
把大问题转化为规模较小的相同问题
分治在每一层递归上都有3个步骤
分解，求解，合并

归并排序

#include <stdio.h>
#include<limits.h>

void Merge(int A[],int p,int q,int r) {    
  //p左边界，q中间值，r右边界    
  int i,j,k;    
  int L[50],R[50];//两个辅助数组    
  int n1 = q - p + 1;//左半部分数组长度    
  int n2 = r - q;//右半部分数组长度  
    
  for(i = 0; i < n1; i++) {        
    //遍历左半部分备份到数组L中        
    L[i] = A[p + i];    
  }    
  
  for(j = 0; j < n2; j++) {        
    //遍历右半部分备份到数组R中        
    R[j] = A[q + j + 1];    
  }    
  
  L[n1] = INT_MAX;    
  R[n2] = INT_MAX;    //存储最大值  
    
  i = 0;    
  j = 0;    
  for(k = p; k < r + 1; k++) {        
    //把子序列进行归并        
    if(L[i] < R[j]) {            
      //左半部分的 < 右半部分            
      A[k] = L[i];//把左半部分的数赋给数组            
      i++;        
    } else {            
      A[k] = R[j];//把右半部分的数赋给数组            
      j++;        
    }    
  }
}

void MergeSort(int A[],int p,int r) {    
  int q;    
  if(p < r) { 
    //数组中不只有一个元素        
    q = (p + r) / 2;
    //q是中间值        
    MergeSort(A,p,q);//左半部分        
    MergeSort(A,q + 1,r);//右半部分        
    Merge(A,p,q,r);    
  }
}

int main() {    
  int A[] = {5,78,3,1,80,11};    
  MergeSort(A,0,5);    
  int i;    
  for(i = 0; i < 5; i++) {        
    printf("%d ",A[i]);    
  }    
  return 0;
}

2T(n/2)+O(n)
T(n)=O(nlogn)

2.1最大子段和问题

子问题是相同的
连续的，当数据全为负数时，最大子段和为0

情形1：左边最大子段和
情形2：右边最大子段和
情形3：左边最大到右边最大连续相加

#include <stdio.h>
#include <stdlib.h>

int MaxSubSum(int *Array,int left,int right) {    
  int sum = 0;    
  int i;    
  
  if(left == right) {        
    //分解到单个整数，不可继续分解        
    //只有一个数的情况        
    if(Array[left] > 0) {            
      //左边值>0            
      sum = Array[left];            
      //把>0的数赋给sum        
    } else {            
      sum = 0;        
    }    
  } else {        
    int center = (left + right) / 2;        
    int leftSum = MaxSubSum(Array,left,center);
    //情形1，左边最大子段和        
    int rightSum = MaxSubSum(Array,center + 1,right);
    //情形2，右边最大字段和    
        
    int s1 = 0;//左边最大和        
    int lefts = 0;//辅助        
    for(i = center; i >= left; i--) {            
      //从后往前找            
      lefts += Array[i];            
      if(lefts > s1) {                
        //不成立就继续往前找                
        //成立就更新s1                
        s1 = lefts;            
      }        
    }        
    
    int s2 = 0;//右边最大和        
    int rights = 0;//辅助    
        
    for(i = center + 1; i <= right; i++) {            
      //从前往后找            
      rights += Array[i];            
      if(rights > s2) {                
        s2 = rights;            
      }        
    }        
    
    sum = s1 + s2;//情形3     
       
    if(sum < leftSum) {            
      sum = leftSum;//情形1        
    }        
    
    if(sum < rightSum) {            
      sum = rightSum;//情形2        
    }    
  }    
  return sum;//情形3
}

int main() {    
  int *Array = (int *)malloc(6 * sizeof(int));    
  Array[0] = -2;    
  Array[1] = 11;    
  Array[2] = -4;    
  Array[3] = 13;    
  Array[4] = -5;    
  Array[5] = -2;    
  
  int result = MaxSubSum(Array,0,5);    
  printf("%d",result);    
  return 0;
}

T(n)=O(nlogn)

2.2动态规划

子问题不是相同的

性质：
1.最优子结构：一个问题的最优解包含其子问题的最优解
2.重叠子问题：反复解同一个子问题

0-1背包问题

/*
i物品个数，j背包容量
v[i]第i个物品的价值，w[i]第i个物品的重量
f[i][j]结果

从前i的物品中选，背包容量为j时的最大价值
当选第i个物品时，要考虑选第i个物品和不选第i个物品两种情况的较大值，作为f[i][j]的最优解
=不选第i个物品和选第i个物品，两者的最大值
=f[i][j]=max(f[i-1][j]，v[i]+f[i-1][j-w[i]])

不选第i个物品
＝从前i-1个物品中选，背包容量为j时的最大价值
=f[i][j]=f[i-1][j]

选第i个物品
前提条件：背包容量j＞=第i个物品的重量才能选
if(j>=w[i])

=第i个物品的价值+从前i-1个物品中选
背包容量为(j-第i个物品的重量)时的最大价值
=f[i][j]=v[i]+f[i-1][j-w[i]]
*/

#include <stdio.h>

#define N 4//物品数量
#define W 5//背包容量

int max(int a,int b) {    
  return a > b ? a : b;
}

int main() {    
  int v[] = {0,2,4,5,6};//物品价值数组    
  int w[] = {0,1,2,3,4};//物品重量数组 
    
  int f[N + 1][W + 1] = {};
  //子问题数组，从1开始    
  
  int i,j;//i物品个数，j背包容量    
  for(i = 1; i <= N; i++) {        
    for(j = 1; j <= W; j++) {            
      /*            
      f[i][j] = f[i - 1][j];            
      //默认不选第i个物品                        
      if(j >= w[i]){                
        f[i][j] = max(f[i][j],f[i - 1][j - w[i]]+ v[i]);            
      }            
      */            
      if(j >= w[i]) {                
        //选第i个物品                
        f[i][j] = max(f[i][j],f[i - 1][j - w[i]]+ v[i]);                
        //不选第i个物品和选第i个物品的较大值            
      } else {                
        //不选第i个物品                
        f[i][j] = f[i - 1][j];                
        //从前i-1个物品中选，背包容量为j时的最大价值            
      }        
    }    
  }    
  printf("%d ",f[N][W]);  
    
  for(i = 0; i <= N; i++) {        
    for(j = 0; j <= W; j++) {            
      printf("%d ",f[i][j]);        
    }        
    printf("\n");    
  }    
  return 0;
}

时间和空间复杂度：O(NW)

矩阵连乘的的时间复杂度：O(n³)
空间复杂度：O(n²)

蛮力法时间复杂度O(n2ⁿ)

2.3贪心法

性质
1.最优子结构
2.贪心选择性质：全局最优可以通过局部最优得到

部分背包问题(单位重量价值最大优先)
时间复杂度：O(nlogn)

#include <stdio.h>

#define N 5//物品数量
#define W 100//背包容量

//临时数组
int v_temp[N + 1],w_temp[N + 1];
double vw_temp[N + 1];

double answer [N + 1];//解决方案数组

//归并排序
void merge_sort(int v[], int w[], double vw[], int l, int r) {    
  if (l >= r) return;    
  
  int mid =l + r >> 1;    
  merge_sort(v, w, vw, l, mid), 
  merge_sort(v, w, vw, mid + 1, r);   
   
  int i=1, 
  j= mid +1, k =1;    
  while (i <= mid &&j<= r) {        
    if (vw[i] >= vw[j]) {            
      // 按照物品单位重量价值数组从大到小的顺序排序            
      vw_temp[k]= vw[i];            
      v_temp[k] = v[i];            
      w_temp[k] = w[i];    
            
      k++,i++;        
    } else {            
      vw_temp[k] = vw[j];            
      v_temp[k] = v[j];            
      w_temp[k] = w[j];   
               
      k++,j++;        
    }    
  }    
  
  while (i <= mid) {        
    vw_temp[k] = vw[i];        
    v_temp[k] = v[i];        
    w_temp[k] = w[i];    
        
    k++,i++;    
  }    
  
  while (j <= r) {        
    vw_temp[k] = vw[j];        
    v_temp[k] = v[j];        
    w_temp[k]= w[j];   
         
    k++,j++;    
  }    
  
  for (i =1, j=1; i<=r; i++,j++) {        
    vw[i] = vw_temp[j];        
    v[i] = v_temp[j];        
    w[i] = w_temp[j];    
  }
}

//显示物品的价值，重量，单位重量价值数组
void show(int v[],int w[], double vw[]) {    
  int i;    
  printf("物品价值数组：");  
  for(i = 1; i <= N; i++) {        
    printf("%d ",v[i]);    
  }    
  printf("\n");    
    
  printf("物品重量数组：");    
  for(i = 1; i <= N; i++) {        
    printf("%d ",w[i]);    
  }    
  printf("\n");    
    
  printf("物品单位重量价值数组：");    
  for(i = 1; i <= N; i++) {        
    printf("%.1lf ",vw[i]);    
  }    
  printf("\n");
}
//求解部分背包问题最优解
double Max_Value(int v[],int w[],int vw[]) {    
  double result = 0.0;//当前背包放入的物品    
  int i;    
  int W_temp = W;//临时数组    
  for(i = 1; i <= N; i++) {        
    if(W_temp >= w[i]) {            
      //背包容量>物品重量，可以装            
      answer[i] = 1.0;            

      result = result + v[i];            
      //把物品装入背包            

      W_temp = W_temp - w[i];            
      //背包容量-当前装入背包的容量        
    } else {            
    //不可以装            
      break;        
    }    
  }    
  if(W_temp > 0 && i <= N) {        
    //背包有容量且还有可以选的物品        
    answer[i] = (double)W_temp / w[i]; 
           
    result = result + W_temp * vw[i];        
    //当前背包放入的物品+部分物品        
    //result = result +(double)W_temp / w[i] * v[i];    
  }    
  return result;
}

int main() {    
  int v[] = {0,60,65,40,30,20};
  //物品价值数组    
  int w[] = {0,50,30,40,20,10};
  //物品重量数组    
  double vw[N + 1];    
  //物品单位重量价值数组，下标从1开始    
  
  int i;    
  for(i = 1; i <= N; i++) {        
    vw[i] = (double)v[i] / w[i];    
  }    
  printf("排序前：\n");    
  show(v,w,vw);   
   
  merge_sort(v,w,vw,1,N);    
  printf("排序后：\n");    
  show(v,w,vw);  
    
  double result = Max_Value(v,w,vw);    
  printf("\nresult = %.2lf\n",result);    
  printf("\n");    
  
  printf("解决方案结果：");    
  for(i = 1; i <= N; i++) {        
    printf("%.1lf",answer[i]);    
  }    
  return 0;
}

2.4分支界限法

广度优先