算法

• 分治算法
  对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。

• 合并算法

• 动态规划
  将待求解的问题分解为若干个子问题，先求解子问题，然后从子问题得到原问题的解；
  与分治法最大的差别是：适合于用动态规划法求解的问题，经分解后得到的子问题往往不是互相独立的

• 贪心算法
  从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。
  回溯法

• 分支界限法

合并排序：

Void sortIt(s,first,mid,last,temp) {
    int i = first; int  j = mid + 1; int m = mid; int n = last;
    int k = 0;
    while (i <= m && j <= n){
        if(s[i] < s[j]) {temp[k++] = s[i++];}
        else temp[k++] = s[j++];
    }
    while (i <= m){ temp[k++] = s[i++];}
    while (j <= n) { temp[k++] = s[j++]; }
    for(i = 0; i < k; i++)
    {a[i+first] = temp[i];//将排好顺序的部分放在数组a中}
}
Void mergeSort(a,first,last,temp){
 if(first < last) {
        Int mid =(first + last) / 2 ;　
        mergeSort(a,first,mid,temp);　//使左边有序
        mergeSort(a,mid + 1, last,temp);//使右边有序
        sortIt(a,first,mid,last,temp);//合并两个有序的}
}
数组换位置：
sort(a,0,k-1);
    sort(a,k,num-1);
    sort(a,0,num-1);
void sort(int a[], int low, int high){
    int temp;
    while(low < high)
    {
        temp = a[low];
        a[low++] = a[high];
        a[high--] = temp;
    }
}

最长公共子序列：

最长公共子序列

最大子段和问题：

 for(i=1; i<count; i++)
    { if(b[i-1]>0)
            b[i]=b[i-1]+a[i];
        else
            b[i]=a[i];
        if(b[i]>max)
    
        max=b[i];
}

编辑距离问题：

int edit(char *A,char *B)
{int i,j,t,temp,lenA = strlen(A),lenB = strlen(B),k,z;
    for(i=0;i<=lenA;i++)    {
        for(j=0;j<=lenB;j++)    {
            if(i==0 && j==0){D[i][j] = 0;}
            else if(i==0 && j>0){
                D[i][j] = j;}
            else if(i>0 && j==0)
            {D[i][j] = i;}
            else{
                if(A[i-1] == B[j-1]){
                    t=0;}
                else    {
                    t=1;}
                temp = min(D[i-1][j]+1,D[i][j-1]+1);
                D[i][j] = min(temp,D[i-1][j-1]+t);}}}
    return  D[--i][--j];}

最优分解

int BestMul(int n)
{
    int i,j,mul=1;
    int num; int a[MAX] = {0};
    a[0]=2; num=n-2;
     for(i=0;num>a[i];i++){a[i+1]=a[i]+1; num-=a[i+1]; }
       j=i+1;
    while(num!=0)
    { a[i]++; num-=1; i=(i-1+j)%j;}
     for(i=0;i<j;i++){ mul*=a[i];}
    printf("\n最大乘积为%d\n",mul);
}  

0-1背包问题（动态规划）

int max(int a, int b){
    if (a >= b)   return a;
    else  return b;
}
int KnapSack(int n, int w[], int v[], int x[], int C){   
 int i, j;
    for (i = 0; i <= n; i++)
        V[i][0] = 0;
    for (j = 0; j <= C; j++)
        V[0][j] = 0;
    for (i = 0; i < n; i++){
        for (j = 0; j < C+1; 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 - 1; i >= 0; i--)
    {
        if (V[i][j]>V[i - 1][j])
        { x[i] = 1;j = j - w[i];}
        else
            x[i] = 0;
    }
    printf("选中的物品是:\n");
    for (i = 0; i<n; i++)
        printf("%d ", x[i]);
    printf("\n");
    for (i = 0; i < n; i++){
        for ( j = 0; j < C+1; j++){
            printf("%d\t ", V[i][j]);
            if (j == C){
                printf("\n");}}}
       return V[n - 1][C];}

最优装载问题（贪心算法）

Void Loding(int x[], int w[],int c,int n){
Int *t = new int[n+1];
Sort(w,t,n);
For(i = 1; i <= n; i++) x[i] = 0;
for(i = 1; i <= n && w[t[i]] <= c; i++)
    {
        x[t[i]] = 1;
        c -= w[t[i]];
    }
}

多处最优服务次序

int greedy(int A[],int n,int s)  {  
    int i= 0 ,t = 0,j = 0;  
    while(i < n)  {  
        B[j] += A[i];  
        C[j] += B[j];      //C[i] 存储每个顾客的等待时间  
        i++;  j++;  
        if(j == s) {          //安排s个服务点的活动  
            j = 0;  
        }   }  
    for(i = 0;i < s;i++)  
        t += C[i];      //每个服务点的等待时间累加  
    return  t/=n;  
} 

删数问题

while(n>0) {//直到要删除的位数为0
        i=0; //每次开始将i初始化为0，表示重新开始检测下降点 
        while(i<strlen(a) && a[i]<a[i+1]) //在位数范围内，到了递减区间，就跳出循环
            i++;  
        for(j=i;j<strlen(a);j++) //后面往前挤一位，实现删除i位。
            a[j]=a[j+1];
          n--;
 }

多机调度问题

#define N 7 //作业数
#define M 3 //机器数 
int s[M] = {0,0,0};//每台机器当前已分配的作业总耗时 
int main(void) 
{   int time[N] = {16,14,6,5,4,3,2};//处理时间按从大到小排序 
    int maxtime = 0;
      maxtime = setwork2(time,N);
    printf("最多耗费时间%d。",maxtime);} 
//机器数小于待分配作业数 
int setwork2(int t[],int n)
{   int i;
    int mi = 0;
    for(i=0;i<n;i++)
    { mi = min(M);
      printf("%d,时间和最小的机器号为%d.时间和为%d：\n",i,mi,s[mi]);
      s[mi] = s[mi]+t[i]; }
    int ma = max(s,M);
    return ma;
}
 //求出目前处理作业的时间和 最小的机器号
int min(int m)
{   int min = 0;  int i;
    for(i=1;i<m;i++)
    { if(s[min] > s[i])
           min = i;}       
    return min;}
//求最终结果（最长处理时间）
int max(int s[],int num){ 
 int max = s[0]; int i;
    for(i=1;i<num;i++)
{ if(max < s[i])
           max = s[i];}
       return max;}

n后排列树，删除子集数中的x[j] == x[k],更改后面else代码

else
    {for(i=k;i<=n;i++)
        {   swap(data[k],data[i]);
            if(k==1 || Legal(data,k))
                Backtrack(data,k+1,n);
            swap(data[k],data[i]);}}

n后问题子集树

int x[20];int n,count;
int Place(int k){   int j;
    for(j=1;j<k;j++)
        if((abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k]))
            return 0;
    return 1;}
void Backtrack(int t){
    int i;
    if(t>n) 
    {for(i=1;i<=n;i++)printf("%d ",x[i]);
        printf("\n");
        count++;    }
    else
    for(i=1;i<=n;i++) 
    {x[t]=i;   if(Place(t))   Backtrack(t+1); }}