当前位置：首页 > news >正文

算法整理合集

news 来源：原创 2024/5/9 21:55:33

1、冒泡排序

2、堆排序

3、快速排序

4、哈希查找

5、折半查找

6、棋盘覆盖

7、递归：二分查找

8、递归：阶乘

9、大整数乘法

10、递归-Strassen矩阵乘法

11、斐波那契数列递归

12、n后问题

13、Hanoi塔问题

14、半数单集

15、整数因子分解问题

16、C语言-生成随机数

17、无和集问题

18、多处最优服务次序问题

19、最优装载

20、装载问题

21、最大子段和

22、最优二叉搜索树

23、最长公共子序列

24、作业调度

25、循环赛日程表

26、旅行售货员

27、流水作业调度-动态规划

28、快速排序2

29、递归：有重复元素的排列问题

30、递归：整数划分

31、动态规划01背包

32、动态规划-矩阵连乘

33、动态规划：最长公共子序列

34、多级调度（贪心）

35、分支限界-装载问题

36、活动安排

37、矩阵乘积标准式

1、冒泡排序

将待排序的n个记录看作按纵向排列，每趟排序时自下至上对排序范围中每对相邻元素进行比较，若次序不符合要求就交换。每趟排序都能使待排序范围内关键字最小的元素像气泡一样“冒”到待排序范围最上端

#include<stdio.h>
void Bubble(int *a,int n);
void Bubble2(int *p,int n);
int main()
{int a[]={38,20,46,38,74,12};Bubble(a,6);printf("\n");Bubble2(a,6);return 0;
}
void Bubble(int *a,int n)//这个n就是数组元素个数 
{int i,j;int t;for(i=0;i<n-1;i++){for(j=i+1;j<n;j++){if(a[j]<a[i]){t=a[j];a[j]=a[i];a[i]=t;}}}for(i=0;i<n;i++){printf("%d ",a[i]);}
}
void  Bubble2(int *p,int n)
{int i,j;int t;for(i=0;i<n-1;i++){for(j=i+1;j<n;j++){if(p[j]>p[i]){t=p[i];p[i]=p[j];p[j]=t;}}}for(i=0;i<n;i++){printf("%d ",p[i]);}
}

2、堆排序

#include<stdio.h>
#define MAXSIZE 100 
typedef struct
{int key;
}DataType;
typedef struct
{DataType list[MAXSIZE];int length;
}SeqList;
void HeapAdjust(SeqList *L,int low,int high) 
{ int i, j;i=low; j=2*i; L->list[0]=L->list[i]; for(;j<=high;j*=2) { if(j<high&&L->list[j].key<L->list[j+1].key)j++;if(L->list[0].key>=L->list[j].key) break; else { L->list[i]=L->list[j];i=j; }}L->list[i]=L->list[0]; 
}
void HeapCreate(SeqList *L) 
{ int i, n;n=L->length;for(i=n/2;i>0;i--)HeapAdjust(L,i,n);
}
void HeapSort(SeqList *L)
{ int i, n=L->length;HeapCreate(L);for(i=n;i>1;i--){ L->list[0]=L->list[1];L->list[1]=L->list[i]; L->list[i]= L->list[0];HeapAdjust(L,1,i-1);}
}
int main()
{SeqList L={{0,18,27,10,8,18,38,4,17,21},10};HeapCreate(&L);HeapSort(&L);int i;for(i=1;i<=10;i++){printf("%d ",L.list[i].key);} return 0;	
}

3、快速排序

#include<stdio.h>
#define MAXSIZE 100
typedef struct
{int key;
}DataType;
typedef struct
{DataType list[MAXSIZE];int length;
}SeqList;
int QuickPass(SeqList *L,int low,int high) 
{ int i,j;i=low;j=high; L->list[0]=L->list[i];while(i!=j){ while((L->list[j].key>=L->list[0].key)&&(i<j)) j--;if(i<j){ L->list[i]=L->list[j]; i++; }while((L->list[i].key<=L->list[0].key)&&(i<j)) i++;if(i<j) { L->list[j]=L->list[i]; j--; }}L->list[i]=L->list[0]; return i;
}
void QuickSort(SeqList *L,int s,int t) 
{ int i;if(s<t){i=QuickPass(L,s,t);QuickSort(L,s,i-1);QuickSort(L,i+1,t);}
}
int main()
{SeqList L={{0,18,27,10,8,19,38,4,17,21},10};QuickSort(&L,1,10);int i;for(i=1;i<=10;i++){printf("%d ",L.list[i].key);}return 0;	
}

4、哈希查找

#include <stdio.h>
#include <stdlib.h>
#define NULLKEY 0
#define DELKEY -1
typedef struct 
{int key;
}Haxi;
int Hash(int k)
{ int i;i=k%97;return i;
}
int InsertHash(Haxi ht[],int m,int k)
{int h0,hi,di;h0=Hash(k);hi=h0;di=1;while(ht[hi].key!=NULLKEY&&ht[hi].key!=DELKEY&&ht[hi].key!=k&&di<m){hi=(h0+di)%m;di++;}if(ht[hi].key!=k&&di<m){ht[hi].key=k;return 1;}else{if(ht[hi].key==k)printf("元素%d已经存在\n",k);elseprintf("哈希表已满\n");return 0;  }
}
void CreateHash(Haxi ht[],int m)
{int endflag=-99999;int i,x;for(i=0;i<m;i++){ht[i].key=NULLKEY;}printf("请输入哈希表中各个元素的值，以endflag=-99999结束：\n");scanf("%d",&x);while(x!=endflag){InsertHash(ht,m,x);scanf("%d",&x);}
}
int SearchHash(Haxi ht[],int m,int k)
{int h0,hi,di;h0=Hash(k);hi=h0;di=1;while(ht[hi].key!=NULLKEY&&ht[hi].key!=k&&di<m){hi=(h0+di)%m;di++;}if(ht[hi].key==k)return hi;elsereturn -1;
}
int DeleteHash(Haxi ht[],int m,int k)
{int i;i=SearchHash(ht,m,k);if(i!=-1){ht[i].key=DELKEY;return 1;}elsereturn 0;
}
int main()
{Haxi ht[100];int i,j;int huanhang=0;CreateHash(ht,100);int number;int q;do{printf("请输入你想进行的操作:\n1.查看哈希表\n2.查找哈希表中的元素\n3.删除哈希表中的元素\n0.退出\n");scanf("%d",&q);switch(q){case 1:	printf("下面是建立的哈希表：\n\n");for(i=0;i<=99;i++){printf("%d    ",ht[i].key);huanhang++;if(huanhang%10==0){printf("\n");}}break;case 2: printf("请输入你想查找的元素:\n");scanf("%d",&number);j=SearchHash(ht,100,number);if(j==-1){printf("查找失败，该元素不存在!\n\n");}elseprintf("元素%d在第%d个位置上",number,j);  break;case 3: printf("请输入你想删除的元素:");int delnumber;int sign;scanf("%d",&delnumber);sign=DeleteHash(ht,100,delnumber);if(sign==1){printf("删除成功，该元素所在位置置为0\n");}elseprintf("查找失败！该元素不存在\n");break;}}while(q);return 0;
}
//测试数据:62 30 18 45 21 78 66 32 54 48 -99999

5、折半查找

#include<stdio.h>
#define MAXSIZE 100
#define KeyType int
typedef struct STUDENTS
{char name[10]; int grade;    
}stu;typedef struct  
{stu data[MAXSIZE+1];int length;
}SeqList;int Binsearch(SeqList *L,KeyType x)
{ int low,mid,high;low=1; high=L->length;while(low<=high){ mid=(low+high)/2;if(L->data[mid].grade==x)return mid;elseif(L->data[mid].grade<x)low=mid+1;elsehigh=mid-1;}return 0;
}
int main()
{SeqList m={{{"",0},{"张三",60},{"李四",70},{"王五",80},{"老六",90}},4};int searchgrade;int location;printf("请输入你想要查找的成绩:\n");scanf("%d",&searchgrade);location=Binsearch(&m,searchgrade);if(location!=0){printf("%s",m.data[location].name);}else{printf("查无此人");	}return 0;		 
}

6、棋盘覆盖

#include<iostream>
using namespace std;
int tile;
int Board[100][100];
void ChessBoard(int tr,int tc,int dr,int dc,int size);
int main()
{int dr,dc,size;cout<<"请输入棋盘的行列大小:";cin>>size;cout<<"请输入特殊方格的行列号:";cin>>dr>>dc;Board[dr][dc]=-1;ChessBoard(0,0,dr,dc,size);for(int i=0;i<size;i++){for(int j=0;j<size;j++)cout<<" "<<Board[i][j];cout<<endl;}return 0;
}
void ChessBoard(int tr,int tc,int dr,int dc,int size)//tr tc分别是棋盘左上角方格的行号和列号 
{if(size==1) return ;int t=tile++;//覆盖数值 int s=size/2;//分割棋盘 //覆盖左上角子棋盘 if(dr<tr+s&&dc<tc+s)//特殊方格在此棋盘中 ChessBoard(tr,tc,dr,dc,s);else //特殊棋盘不在此棋盘 {Board[tr+s-1][tc+s-1]=t;//用t数值来覆盖右下角 ChessBoard(tr,tc,tr+s-1,tc+s-1,s);//覆盖其余方格 }//覆盖右上角子棋盘 if(dr<tr+s&&dc>=tc+s)//特殊方格在此棋盘中ChessBoard(tr,tc+s,dr,dc,s);else{Board[tr+s-1][tc+s]=t;//t覆盖左下角 ChessBoard(tr,tc+s,tr+s-1,tc+s,s);//覆盖其余方格 }//覆盖左下角子棋盘 if(dr>=tr+s&&dc<tc+s)//特殊方格在此棋盘中ChessBoard(tr+s,tc,dr,dc,s);else{Board[tr+s][tc+s-1]=t;//t覆盖右上角 ChessBoard(tr+s,tc,tr+s,tc+s-1,s);//覆盖其余方格 }//覆盖右下角子棋盘 if(dr>=tr+s&&dc>=tc+s)//特殊方格在此棋盘中ChessBoard(tr+s,tc+s,dr,dc,s);else{Board[tr+s][tc+s]=t;//t覆盖左上角 ChessBoard(tr+s,tc+s,tr+s,tc+s,s);//覆盖其余方格 }
}

7、递归：二分查找

#include<iostream>
using namespace std;
int BinSearch(int *data,int key,int low,int high)
{int  mid=(low+high)/2;if(low>high) return -1;    if(key==data[mid]) return mid;if(key<data[mid]) return BinSearch(data,key,low,mid-1);else          return BinSearch(data,key,mid+1,high);
}
int main()
{int data[10]={1,3,5,6,34,56,67,77,78,90};int number;cout<<"请输入查找的数字:";cin>>number;int location=BinSearch(data,number,0,9);cout<<"location="<<location+1;return 0; 
}

8、递归：阶乘

#include<stdio.h>
int factorial(int n)
{if(n==0)return 1;return n*factorial(n-1);
}
int main()
{printf("%d",factorial(3));
}

9、大整数乘法

#include<iostream>
#include<math.h>
#include<algorithm>
using namespace std;
int Sign(int x)
{if(x>0)return 1;else if (x<0)return -1;return 0;
}
int divideConquer(int X, int Y, int n)
{int sign=Sign(X)*Sign(Y);int x=abs(X);int y=abs(Y);if (x==0||y==0)return 0;else if(n==1)return sign*x*y;else{int A=x/pow(10,n/2);int B=x-A*pow(10,n/2);int C=y/pow(10,n/2);int D=y-C*pow(10,n/2);int AC=divideConquer(A,C,n/2);int BD=divideConquer(B,D,n/2);int ABDC=divideConquer((A-B),(D-C),n/2)+AC+BD;return sign*(AC*pow(10,n)+ABDC*pow(10,(int)(n/2))+BD);}
}
int main()
{int x,y;int n;cout<<"请分别输入两个十进制的数字以及位数（注：位数须是偶数）"<<endl;cin>>x>>y>>n;cout<<divideConquer(x,y,n);return 0;
}

10、递归-Strassen矩阵乘法

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define N 2   //矩阵阶数 
void add(int n,int A[N][N],int B[N][N],int C[N][N])
{int i,j;for(i=0;i<n;i++)for(j=0;j<n;j++)C[i][j]=A[i][j]+B[i][j]; 
}
void sub(int n,int A[N][N],int B[N][N],int C[N][N])
{int i,j;for(i=0;i<n;i++)for(j=0;j<n;j++)C[i][j]=A[i][j]-B[i][j]; 
}
void Strassen(int n,int A[N][N],int B[N][N],int C[N][N])
{int A11[N][N],A12[N][N],A21[N][N],A22[N][N];int B11[N][N],B12[N][N],B21[N][N],B22[N][N];int C11[N][N],C12[N][N],C21[N][N],C22[N][N];int M1[N][N],M2[N][N],M3[N][N],M4[N][N],M5[N][N],M6[N][N],M7[N][N];int T1[N][N],T2[N][N];int i,j;if(n==2){for(i=0;i<2;i++){for(j=0;j<2;j++){C[i][j]=0;for(int t=0;t<2;t++){C[i][j]+=A[i][t]*B[t][j];}}}return ;}for(i=0;i<n/2;i++){//划分A,Bfor(j=0;j<n/2;j++){A11[i][j]=A[i][j];A12[i][j]=A[i][j+n/2];A21[i][j]=A[i+n/2][j];A22[i][j]=A[i+n/2][j+n/2];B11[i][j]=B[i][j];B12[i][j]=B[i][j+n/2];B21[i][j]=B[i+n/2][j];B22[i][j]=B[i+n/2][j+n/2];}}sub(n/2,B12,B22,T1);Strassen(n/2,A11,T1,M1);//M1=A11(B12-B22)add(n/2,A11,A12,T1);Strassen(n/2,T1,B22,M2);//M2=(A11+A12)B22add(n/2,A21,A22,T1);Strassen(n/2,T1,B11,M3);//M3=(A21+A22)B11sub(n/2,B21,B11,T1);Strassen(n/2,A22,T1,M4);//M4=A22(B21-B11)add(n/2,A11,A22,T1);add(n/2,B11,B22,T2);//M5=(A11+A22)(B11+B22)Strassen(n/2,T1,T2,M5);sub(n/2,A12,A22,T1);add(n/2,B21,B22,T2);Strassen(n/2,T1,T2,M6);//M6=(A12-A22)(B21+B22)sub(n/2,A11,A21,T1);add(n/2,B11,B12,T2);Strassen(n/2,T1,T2,M7);//M7=(A11-A21)(B11+B12)add(n/2,M5,M4,T1);sub(n/2,T1,M2,T2);add(n/2,T2,M6,C11);//C11=M5+M4-M2+M6add(n/2,M1,M2,C12);//C12=M1+M2add(n/2,M3,M4,C21);//C21=M3+M4 add(n/2,M5,M1,T1);//C22=M5+M1-M3-M7sub(n/2,T1,M3,T2);sub(n/2,T2,M7,C22);for(i=0;i<n/2;i++){//合并到Cfor(j=0;j<n/2;j++){C[i][j]=C11[i][j];C[i+n/2][j]=C21[i][j];C[i][j+n/2]=C12[i][j];C[i+n/2][j+n/2]=C22[i][j];}}
}
int main()
{int n,i,j;int A[N][N],B[N][N],C[N][N];printf("please input matrix A\n");for(i=0;i<N;i++)for(j=0;j<N;j++)scanf("%d",&A[i][j]);printf("please input matrix B\n");		for(i=0;i<N;i++)for(j=0;j<N;j++)scanf("%d",&B[i][j]);	Strassen(N,A,B,C);printf("matrix C\n\n");for(i=0;i<N;i++){for(j=0;j<N;j++){printf("%d ",C[i][j]);}printf("\n");}return 0;
}

11、斐波那契数列递归

#include<iostream>
using namespace std;
int fibonacci(int n)
{if(n<=1)return 1;return fibonacci(n-1)+fibonacci(n-2);
}
int main()
{int n;cin>>n;for(int i=0;i<5;i++)cout<<fibonacci(i)<<" ";
}

12、n后问题

#include<iostream>
#include<math.h> 
using namespace std;
class Queen{friend int nQueen(int);
private:bool Place(int k);void Backtrack();int n;//皇后个数 int *x;//当前解 long sum;//当前已找到的可行方案数 
};
bool Queen::Place(int k)
{for(int j=1;j<k;j++)if((abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k]))return false;return true;
}
void Queen::Backtrack()
{x[1]=0;int k=1;while(k>0){x[k]+=1;while(x[k]<=n&&!(Place(k)))//第k个分量选取合适的值 x[k]++;if(x[k]<=n)//选取到了合适的值 {if(k==n)//到达叶子结点数，方案数++ {sum++;cout<<"可行解有：";for(int i=1;i<=n;i++){ cout<<x[i]<<" ";}cout<<endl;}else{k++;//下一个分量 x[k]=0;//初始化为0 }}else//找不到合适的值，回溯 k--;}
}
int nQueen(int n)
{Queen X;X.n=n;X.sum=0;int *p=new int[n+1];for(int i=0;i<=n;i++)p[i]=0;X.x=p;X.Backtrack();delete[] p;return X.sum;
}
int main()
{int n=4;int sum=nQueen(n);cout<<sum;return 0;
}

13、Hanoi塔问题

#include<iostream>
using namespace std;
int sum;//总共需要走的步数sum 
void move(char X,int N,char Y)
{cout<<N<<"从"<<X<<"->"<<Y<<endl;sum++;//每移动一次sum加一 
}
void hanoi(int n,char x,char y,char z)
{if(n==1)move(x,1,z);//直接从x移到z上 else {hanoi(n-1,x,z,y);// 把上面的n-1个圆盘，从A经过C移动到Bmove(x,n,z);// 把第n个圆盘从A移动到Chanoi(n-1,y,x,z);// 把那n-1块个圆盘，从B经过A移动到C}
}int main(){int n=0;char A,B,C;cout<<"请输入A上的圆盘数n："; cin>>n;hanoi(n,'A','B','C');//实参盘子数n 柱子A,B,C cout<<"总共需要走的步数为："<<sum; return 0;
}

14、半数单集

#include<iostream>
#include<fstream>
using namespace std;
int a[600];
long comp(int n)
{long ans=1;if(a[n]>0)return a[n];for(int i=1;i<=n/2;i++){ans+=comp(i);if((i>10)&&(2*(i/10)<=i%10))ans-=a[i/10];}a[n]=ans;return ans;
}
int main()
{int n;a[1]=1;ifstream in("input2-4.txt");if(in){in>>n;in.close(); }int sum;ofstream out("output2-4.txt");if(out){out<<comp(n);out.close();}return 0;
}

15、整数因子分解问题

#include<iostream>
#include<fstream>
using namespace std;
int total;
void solve(int n)
{if(n==1)total++;else{for(int i=2;i<=n;i++){if(n%i==0)solve(n/i);}}
}
int main()
{int n;ifstream in("input2-11.txt");if(in){in>>n;in.close(); }solve(n);ofstream out("output2-11.txt");if(out){out<<total;out.close();}return 0;
}

16、C语言-生成随机数

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
int *getRandom()
{ static int r[10] ; // static类型 int i ;srand((unsigned)time(NULL)); for(i=0;i<10;++i)r[i]=rand()%100;return r ; // 返回数组首地址
}
int main() 
{ int *p,i; p=getRandom();for(i=0;i<10;i++)printf("*(p+[%d]):%d\n",i,*(p+i));return 0;
}

17、无和集问题

#include<iostream>
#include<fstream>
using namespace std;
const int N = 100;
int a[N][N]; //存储当前解的数组，其中a[n][0]表示第n个子集的元素个数，a[n][1]到a[n][a[n][0]]为这个子集的所有元素
int num=1;   //设置初始结果为1（最后要减1，所以初始值为0） 
int best;    //最优值 
int e[N][N]; //最优解,其中的结构和a[n][n]一样 
bool h[N][N];//判定数组,h[i][j]表示第i个子集中是否有j这个元素 
int n;       //表示最多只可以有n个子集
void dfs(int m)
{                               //判断当前num是否能插入第m个子集if(m==n){                           //n个子集的下标是0到n-1,所以当m等于n时表示当前num不能插入所有子集if(num<=best)return;             //如果当前num不如当前最优值best，就返回best=num;               //如果比最优值好，更新最优值和最优解for(int i=0;i<n;i++){for(int j=0;j<=a[i][0];j++)e[i][j]=a[i][j];}return;}else{                          //判断num能否插入第m个子集bool flag=true;           for(int i=1;i<=a[m][0];i++){   //遍历子集,如果num减当前元素在子集中,表示新加的这个y可能存在与原集中的a[m][i]相加后的数还在这个子集中，无法构成无和集 //且num这个要判断的数不是迭代过程中a[m][i]的两倍,因为不可能出现两个相同的a[m][i]，例如1,2,4,8就是合理的那么flag就为false,表示num不能插入这个子集if(h[m][num-a[m][i]]&&num!=2*a[m][i])flag = false;}if(!flag)             //不能插入，判断num能不能插入第m+1个子集  dfs(m+1);         else{                 //可以插入，分两种情况，一种是插入，一种是不插入此子集//插入a[m][++a[m][0]]=num;  //第i个子集个数加一，把元素记入子集h[m][num++]=true;     //把此元素标记为在此子集中dfs(0);               //判断下一个数是否能插入第0个子集//不插入，--a[m][0];            //把子集元素个数减1h[m][--num]=false;    //再把当前元素标记为不在此子集中dfs(m+1);             //判断这个数是否能插入下一个子集}   }
}
int main()
{ifstream in("input5-6.txt");if(in){in>>n;in.close(); }dfs(0);ofstream out("output5-6.txt");if(out){out<<--best<<endl; //记录的是最优值加一，这里减去一并输出for(int i=0;i<n;i++){for(int j=1;j<=e[i][0];j++)out<<e[i][j]<<" ";     //输出最优解out<<endl;}out.close();}return 0;
}

18、多处最优服务次序问题

#include<stdio.h>
#include<algorithm>
#include<iostream>
#define Maxsize 100
using namespace std;
void Greedy(int a[],int n,int s)
{int sumservice[Maxsize]={0};//一共s个服务点，每个服务点的总服务时间 int sumwait[Maxsize]={0};//每个服务点顾客的总等待时间 double sumtime=0;//所有人的等待服务时间 int j=1;for(int i=0;i<n;i++){printf("服务台正在服务顾客,该顾客所需的服务时间=%d\n",a[i]);sumservice[j]+=a[i];sumwait[j]+=sumservice[j];if(j<s)j++;else if(j==s)j=1;}for(j=1;j<=s;j++){sumtime+=sumwait[j];}printf("一共服务了%d位顾客",n);printf("\n等待服务时间=%lf\n",sumtime);double result = sumtime/n;printf("平均等待时间=%lf\n",result);
}
int main() 
{int n;int s;freopen("input4-7.txt","r",stdin);freopen("output4-7.txt","w",stdout);scanf("%d%d",&n,&s);int a[n];for(int i=0;i<n;i++){scanf("%d",&a[i]);}sort(a,a+n);Greedy(a,n,s);return 0;
}

19、最优装载

#include<iostream>
#include<algorithm>
using namespace std;
void Sort(int *w,int n)
{for(int i=0;i<n-1;i++){for(int j=i+1;j<n;j++){if(w[j]<w[i]){int temp=w[i];w[i]=w[j];w[j]=temp;}}}
}
void Biaoji(int w[],int t[],int w1[])
{for(int i=0;i<6;i++){for(int j=0;j<6;j++){if(w1[i]==w[j])t[i]=j; }}
}
void Loading(int x[],int w[],int c,int n)
{int t[6];int w1[6];for(int i=0;i<6;i++)w1[i]=w[i];Sort(w,n);Biaoji(w,t,w1);int weight=0;cout<<"t: ";for(int i=0;i<n;i++){cout<<t[i]<<" ";}cout<<endl;cout<<"w1:";for(int i=0;i<n;i++)cout<<w1[i]<<" ";cout<<endl;for(int i=0;i<n;i++)x[i]=0;for(int i=0;i<n&&w[i]<=c;i++){x[i]=1;c-=w[i];}
}
int main()
{int w[]={12,33,4,2,5,6};int x[6];int c=30;int n=6;Loading(x,w,c,n);cout<<"w: ";for(int i=0;i<6;i++)cout<<w[i]<<" ";cout<<endl; cout<<"x: ";for(int i=0;i<6;i++)cout<<x[i]<<" ";
}

20、装载问题

#include<iostream>
using namespace std;
class Loading{friend int MaxLoading(int [],int,int[]);
public:void Backtrack(int i);int n,*x,*bestx,*w,c,cw,bestw,r;
};
void Loading::Backtrack(int i)
{if(i>n){if(cw>bestw){for(int j=1;j<=n;j++)bestx[j]=x[j];bestw=cw;}return ;}r-=w[i];if(cw+w[i]<=c){x[i]=1;cw+=w[i];Backtrack(i+1);cw-=w[i];}if(cw+r>bestw){x[i]=0;Backtrack(i+1);}r+=w[i];
}
int MaxLoading(int w[],int c,int n,int bestx[])
{Loading X;X.x=new int[n+1];X.w=w;X.c=c;X.n=n;X.bestx=bestx;X.bestw=0;X.cw=0;X.r=0;for(int i=1;i<=n;i++)X.r+=w[i];X.Backtrack(1);delete[] X.x;return X.bestw;
}
int main()
{int w[]={8,6,2,3};int n=4;int c=12;int bestx[4];int bestw=MaxLoading(w,c,n,bestx);cout<<bestw;return 0;
}

21、最大子段和

#include<iostream>
using namespace std;
int MaxSum(int n,int *a)
{int sum=0;int b=0;for(int i=0;i<n;i++){if(b>0)b+=a[i];elseb=a[i];if(b>sum)sum=b;}return sum;
} 
int main()
{int a[]={-2,11,-4,13,-5,-2};cout<<"max="<<MaxSum(6,a);return 0;
}

22、最优二叉搜索树

#include<iostream>
#include<cstdio>
using namespace std;
void OptimalBinarySearchTree(int n, double* p, double* q, double** root, double** w, double** e);
void printBintree(double** root, int i, int j);int main()
{cout << "最优二叉搜索树 自底向上非递归的动态规划算法\n\n";int n;			// 根节点数double* p;		// 查找 关键字 的概率double* q;		// 查找 虚拟键 的概率double** root;	// 根节点double** w;		// 子树概率总和double** e;		// 子树期望cout << "请输入节点数目 n：";cin >> n;p = new double[n + 1];q = new double[n + 1];root = new double* [n + 2];w = new double* [n + 2];e = new double* [n + 2];for (int i = 0; i < n + 2; i++){root[i] = new double[n + 1];w[i] = new double[n + 1];e[i] = new double[n + 1];//memset(w[i], 0, sizeof(double) * (n + 1));//memset(e[i], 0, sizeof(double) * (n + 1));}cout << "请输入节点查找成功的概率(n个)：";for (int i = 1; i <= n; i++)cin >> p[i];cout << "请输入节点查找失败的概率(n+1个)：";for (int i = 0; i <= n; i++)cin >> q[i];// 构造最优二叉搜索树OptimalBinarySearchTree(n, p, q, root, w, e);// 输出二叉树printBintree(root, 1, n);for (int i = 0; i < n + 2; i++){for (int j = 0; j < n + 1; j++){cout << e[i][j] << "\t";}cout << endl;}// 删除指针delete[] p;delete[] q;for (int i = 0; i < n + 2; i++){delete[] root[i];delete[] w[i];delete[] e[i];}delete[] root;delete[] w;delete[] e;
}void OptimalBinarySearchTree(int n, double* p, double* q, double** root, double** w, double** e)
{// 处理w[i,j]和e[i,j]中i=j+1的情况，这种情况都是q[i-1]for (int i = 1; i <= n + 1; i++) {w[i][i - 1] = q[i - 1];e[i][i - 1] = 0;}int i = 0;		// 子问题起始节点的下标int j = 0;		// 子问题最后节点的下标int r = 0;		// 子问题根节点的下标double temp = 0;	// 存放计算得到的临时期望// 子问题中节点数量(ki~kj的长度)，从0到n-1for (int len = 1; len <= n; len++){// 循环所有节点数为len的子问题for (i = 1; i <= n - len+1; i++){j = len + i-1;e[i][j] = INT_MAX;w[i][j] = w[i][j - 1] + p[j] + q[j];for (r = i ; r <= j; r++){temp = e[i][r - 1] + e[r + 1][j] + w[i][j];// 保存最优解if (temp < e[i][j]){e[i][j] = temp;root[i][j] = r;}}}}
}void printBintree(double** root, int i, int j)
{if (i < j){int r = root[i][j];cout << "S" << r << "是根\n";if (root[i][r - 1] > 0)cout << "S" << r << "的左孩子是S" << root[i][r - 1] << endl;if (root[r + 1][j] > 0)cout << "S" << r << "的右孩子是S" << root[r + 1][j] << endl;printBintree(root, i, r - 1);printBintree(root, r + 1, j);}
}

23、最长公共子序列

#include<stdio.h>
#include<iostream>
using namespace std;
#define Length 7
#define MAXSIZE 100
char x[MAXSIZE];
char y[MAXSIZE];
int  c[MAXSIZE][MAXSIZE];
int  b[MAXSIZE][MAXSIZE];
void LCS(int i,int j)
{if(i==0||j==0)return;if(b[i][j]==1){LCS(i-1,j-1);cout<<x[i];}else if(b[i][j]==2)LCS(i-1,j);elseLCS(i,j-1);
}
int main()
{cin>>x+1>>y+1;int i,j;for(i=0;i<=Length;i++)c[i][0]=0;for(i=0;i<=Length;i++)c[0][i]=0;for(i=1;i<=Length;i++){for(j=1;j<=Length;j++){if(x[i]==y[j]){c[i][j]==c[i-1][j-1]+1;b[i][j]=1;}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;}}}LCS(Length,Length);return 0;
}

24、作业调度

#include<limits.h>
#include<iostream>
using namespace std;
class Flowshop{friend Flow(int**,int,int[]);
private:void Backtrack(int i);int **M,    //各作业所需的处理时间 *x,    //当前作业调度 *bestx,//当前最优作业调度 *f2,   //机器2完成处理时间 f1,    //机器1完成处理时间 f,     //完成时间和 bestf, //当前最优值 n;     //作业数 
};
void Swap(int &a,int& b)
{int temp=a;a=b;b=temp;
}
void Flowshop::Backtrack(int i)
{if(i>n){if(f<bestf){for(int j=1;j<=n;j++)bestx[j]=x[j];bestf=f;}}else{for(int j=i;j<=n;j++){f1+=M[x[j]][1];f2[i]=((f2[i-1]>f1)?f2[i-1]:f1)+M[x[j]][2];f+=f2[i];if(f<bestf){Swap(x[i],x[j]);Backtrack(i+1);Swap(x[i],x[j]);}f1-=M[x[j]][1];f-=f2[i];}}
}
int Flow(int **M,int n,int bestx[])
{Flowshop X;X.x=new int[n+1];X.f2=new int[n+1];X.M=M;X.n=n;X.bestx=bestx;X.bestf=1000000;X.f1=0;X.f=0;for(int i=0;i<=n;i++){X.f2[i]=0;X.x[i]=i;}X.Backtrack(1);delete[] X.x;delete[] X.f2;return X.bestf;
}int main()
{int **M;int n=3;M=new int*[n+1];int *bestx=new int[n+1];for(int i=0;i<=n;i++){M[i]=new int[n];}M[1][1]=2,M[1][2]=1,M[2][1]=3,M[2][2]=1,M[3][1]=2,M[3][2]=3;int sum=Flow(M,n,bestx);cout<<"最优作业调度:";for(int i=1;i<=n;i++){cout<<bestx[i]<<" ";}cout<<"\n最优值:"<<sum;return 0;
}

25、循环赛日程表

#include<iostream>
using namespace std;
void Table(int k,int** a)
{int n=1;int m=1;for(int i=1;i<=k;i++)n*=2; for(int i=1;i<=n;i++)a[1][i]=i;for(int s=1;s<=k;s++){n/=2;for(int t=1;t<=n;t++)for(int i=m+1;i<=2*m;i++)for(int j=m+1;j<=2*m;j++){a[i][j+(t-1)*m*2]=a[i-m][j+(t-1)*m*2-m];a[i][j+(t-1)*m*2-m]=a[i-m][j+(t-1)*m*2];}m*=2;}
}
int main()
{int k=9;int** a;a=new int*[9];for(int i=0;i<9;i++)a[i]=new int[9];Table(k,a);for(int i=0;i<9;i++){for(int j=0;j<9;j++){cout<<a[i][j]<<" ";}cout<<endl;
}
}

26、旅行售货员

#include<iostream>
using namespace std;
class Traveling{friend int TSP(int**,int[],int,int);
public:void Backtrack(int i);int  n,*x,*bestx;**a,cc,bestc,NoEdge;
};
void Traveling::Backtrack(int i)
{if (i == n) {if(a[x[n-1]][x[n]]<MAX_VALUE&&a[x[n]][1]<MAX_VALUE&&(bestc == 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]] < MAX_VALUE &&(bestc == MAX_VALUE ||  cc+a[x[i - 1]][x[j]]<bestc))  {// 搜索子树swap(x, i, j);cc+=a[x[i - 1]][x[i]];backtrack(i + 1);cc-=a[x[i - 1]][x[i]];swap(x, i, j);}}

27、流水作业调度-动态规划

#include<iostream>
#include<algorithm>
using namespace std;
class Jobtype{public:int operator < (Jobtype &a) const{return (key<a.key);}int key;int index;bool job;};
int FlowShop(int n,int a[],int b[],int c[])
{Jobtype *d=new Jobtype[n];for(int i=0;i<n;i++){d[i].key=a[i]>b[i]?b[i]:a[i];d[i].job=a[i]<=b[i];d[i].index=i;}sort(d,d+n);int j=0;int k=n-1;for(int i=0;i<n;i++){if(d[i].job)c[j++]=d[i].index;elsec[k--]=d[i].index;}j=a[c[0]];k=j+b[c[0]];for(int i=1;i<n;i++){j+=a[c[i]];k=j<k?k+b[c[i]]:j+b[c[i]];}delete d;return k;
}
int main()
{int a[] = {2,4,3,6,1};int b[] = {5,2,3,1,7};int n=5;int c[n];int minTime = FlowShop(n,a,b,c);cout<<"作业在机器1上的运行时间为："<<endl;for(int i=0; i<n; i++)cout<<a[i]<<" ";cout<<endl;cout<<"作业在机器2上的运行时间为："<<endl;for(int i=0; i<n; i++)cout<<b[i]<<" ";cout<<endl;cout<<"完成作业的最短时间为："<<minTime<<endl;cout<<"编号从0开始，作业调度的顺序为："<<endl;for(int i=0; i<n; i++)cout<<c[i]<<" ";return 0;
}

28、快速排序2

#include<iostream>
#include<algorithm>
using namespace std;
int Partition(int a[],int p,int r)
{int i=p;int j=r+1;int x=a[p];while(true){while(a[++i]<x&&i<r) ;while(a[--j]>x) ;if(i>=j)break;swap(a[i],a[j]); }a[p]=a[j];a[j]=x;return j;
}
void QuickSort(int a[],int p,int r)
{if(p<r){int q=Partition(a,p,r);QuickSort(a,p,q-1);QuickSort(a,q+1,r); }
}
int main()
{int a[]={1,22,34,5,7,3,7};QuickSort(a,0,6);for(int i=0;i<7;i++)cout<<a[i]<<" ";
}

29、递归：有重复元素的排列问题

#include<iostream>
#include<algorithm>
using namespace std;
char ch[10];
int cnt=0;
int findsame(int k,int m) 
{for(int i=k;i<m;i++) {if(ch[i]==ch[m])return 1;}return 0;
}
void perm(int k,int m)
{if(k==m) {for(int i=0;i<=m;i++) cout<<ch[i];cout<<endl;cnt++;return ;}for(int i=k;i<=m;i++) {if(findsame(k,i))continue;swap(ch[k],ch[i]);perm(k+1,m);swap(ch[k],ch[i]);}
}
int main() 
{int n;cout<<"请输入元素个数:"<<endl;cin>>n;cout<<"请输入"<<n<<"个元素："<<endl;for(int i=0;i<n;i++)cin>>ch[i];perm(0,n-1);cout<<"count="<<cnt;return 0;
}

30、递归：整数划分

#include<stdio.h>
int q(int n,int m);
void result(int n,int k);
int a[100];
int main()
{int i;scanf("%d",&i);printf("%d",q(i,i));printf("\n");result(i ,0);return 0;
}
int q(int n,int m)
{if((n<1)||(m<1))return 0;if((n==1)||(m==1))return 1;if(n<m)return (n,n);if(n==m)return q(n,m-1)+1;elsereturn q(n,m-1)+q(n-m,m);
}
void result(int n,int k)//输出划分结果
{int i;if(n==0)//出口：分解完成，输出结果{for(i=0;i<k-1;i++){printf("%d+",a[i]);}printf("%d\n",a[i]);}else{for(i=n;i>0;i--)//从第一层开始{if(k==0||i<=a[k-1])//划分条件：a[k]>a[k+1]{a[k]=i;result(n-i,k+1);//递归}}}
}

31、动态规划01背包

#include<iostream>
using namespace std; 
int m[5][10];
int min(int i,int j)
{return i>j?j:i;
}
int max(int i,int j)
{return i>j?i:j;
}
void Knapsack(int* v,int* w,int c,int n)
{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][j],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(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;
}
void PrintValue(int x[],int v[])
{int sum=0;for(int i=0;i<=5;i++){if(x[i]==1)sum+=v[i];}cout<<"The value of the package="<<sum; 
}
int main()
{int n=5;int c=10;int w[]={0,2,2,6,5,4};int v[]={0,6,3,5,4,6};int x[]={0,0,0,0,0,0};Knapsack(v,w,c,n);Traceback(w,c,n,x);cout<<"物品重量：";for(int i=1;i<=5;i++)cout<<w[i]<<" ";cout<<endl;cout<<"物品价值: ";for(int i=1;i<=5;i++)cout<<v[i]<<" ";cout<<endl;cout<<"选择结果: ";for(int i=1;i<=5;i++)cout<<x[i]<<" ";cout<<endl;PrintValue(x,v);return 0;
}

32、动态规划-矩阵连乘

#include<iostream>
using namespace std;
#define Row 2
#define Col 2
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++){for(int i=1;i<=n-r+1;i++){int j=i+r-1;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;}}}}
}
int main()
{int a[2][2]={{1,1},{1,1}};int b[2][2]={{2,2},{2,2}};int c[2][2];int i=1;return 0;
}

33、动态规划：最长公共子序列

#include<iostream>
using namespace std;
#define Max 100
#define size 7
int b[Max][Max];
int c[Max][Max];
char x[Max];
char y[Max];
void LCSLength(int m,int n)
{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[j]){c[i][j]=c[i-1][j-1]+1;b[i][j]=1;}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)
{if(i==0||j==0)return;if(b[i][j]==1){LCS(i-1,j-1);cout<<x[i];}else if(b[i][j]==2)LCS(i-1,j);elseLCS(i,j-1);    
}
int main()
{cout<<"please input the sequence of x and y:"<<endl; cin>>x+1>>y+1;LCSLength(size,size);cout<<"The longest common subsequence="<<endl;LCS(size,size);
}

34、多级调度（贪心）

#include<stdio.h>
#define MAXLENGTH 10
int d[MAXLENGTH];
int S[MAXLENGTH][MAXLENGTH];
struct work{int hour;int number;
};
work t[MAXLENGTH];
void bubble_sort(work a[], int n){int i, j;work temp;for (j = 0; j < n - 1; j++){for ( i = 0; i < n-1-j; i++){if (a[i].hour<a[i+1].hour){temp = a[i];a[i] = a[i + 1];a[i + 1] = temp;}}}
}
void MultiMachine(work t[], int n, int d[], int m);
int main(){int n;int m;int i;printf("请输入待处理的作业个数:");scanf("%d", &n);printf("请输入作业需要处理的时间:");for ( i = 0; i <n; i++){scanf("%d", &t[i].hour);t[i].number = i + 1;}bubble_sort(t, n);printf("请输入机器的个数:");scanf("%d", &m);for ( i = 0; i < m; i++){d[i] = 0;}MultiMachine(t, n, d, m);getchar();getchar();getchar();
}void MultiMachine(work t[], int n, int d[], int m){int rear[MAXLENGTH];int i, j, k;for ( i = 0; i < m; i++){S[i][0] = t[i].number;rear[i] = 0;d[i] = t[i].hour;}for ( i = m; i < n; i++){for (j = 0, k = 1; k < m; k++){if (d[k]<d[j]){j = k;}}rear[j]++;S[j][rear[j]] = t[i].number;d[j] += t[i].hour;}for ( i = 0; i < m; i++){printf("机器%d处理:", i + 1);for ( j = 0; S[i][j]>0; j++){printf("作业%d\t", S[i][j]);}printf("处理时间:%d\n",d[i]);printf("\n");}
}

35、分支限界-装载问题

void EnQueue(Queue<Type>&Q,int wt,int& bestw,inti,int n)
{if(i==n){if(wt>bestw)bestw=wt;}elseQ.Add(wt);
}
template<class Type>
Type MaxLoading(Type w[],Type c,int n)
{Queue<Type> Q;Q.Add(-1);int i =1;Type Ew=0;Type bestw=0;while(true){if(Ew+w[i]<=c)//x[i]=1EnQueue(Q,Ew+w[i],bestw,i,n);EnQueue(Q,Ew,bestw,i,n);//x[i]=0Q.Delete(Ew);if(Ew==-1){if(Q.IsEmpty())return bestw;Q.Add(-1);Q.Delete(Ew);i++;}}
}

36、活动安排

#include<iostream>
using namespace std;
void GreedySelector(int n,int s[],int f[],bool A[])
{A[1]=true;//该算法一开始选择活动1 int j=1;//变量j用以记录最近一次加入到A中的活动 for(int i=2;i<=n;i++){if(s[i]>=f[j])//开始时间不早于最近加入集合A中的活动j的结束时间 {A[i]=true;j=i;}elseA[i]=false;}
}
int main()
{int start[]={0,1,3,0,5,3,5,6,8,8,2,12};//活动开始时间 int end  []={0,4,5,6,7,8,9,10,11,12,13,14};//活动结束时间（非减序排列） bool A   []={0,0,0,0,0,0,0,0,0,0,0,0};//存储所选择的活动 GreedySelector(11,start,end,A);cout<<"结果:";  for(int i=1;i<=11;i++){if(A[i]==1){cout<<i<<" ";} }
}

37、矩阵乘积标准式

#include<iostream>
using namespace std;
#define Row 2
#define Col 2
void matrixMultiply(int a[Row][Col],int b[Row][Col],int c[Row][Col],int ra,int ca,int rb,int cb)
{if(ca!=rb){printf("矩阵不可乘");exit(1);}else{for(int i=0;i<ra;i++){for(int j=0;j<cb;j++){c[i][j]=0;for(int k=0;k<ca;k++){c[i][j]+=a[i][k]*b[k][j];}}}}
}
void Show(int m[Row][Col])
{for(int i=0;i<Row;i++){for(int j=0;j<Col;j++){printf("%d ",m[i][j]);}printf("\n");}
}
int main()
{int a[2][2]={{1,1},{1,1}};int b[2][2]={{2,2},{2,2}};int c[2][2];matrixMultiply(a,b,c,2,2,2,2);Show(c);return 0;
}