算法作业-白红宇

算法作业

阅读量：6704 次

发布时间：2019-06-25

本文共 23325 字，大约阅读时间需要 77 分钟。

第二章

1、整数划分

#include
     
      #include 
      
       #include 
       
        using namespace std;int m[10];int n;void Divid(int now,int k,int pr) { int i; if(now > n) return; if(now == n) { for(i = 0; i < k-1; i++) printf("%d+",m[i]); printf("%d\n",m[i]); } else { for(i = pr; i > 0; i--) { m[k]=i; now+=i; Divid(now,k+1,i); now-=i; } } } int main() { scanf("%d",&n); Divid(0,0,n); return 0; }

2、大整数乘法

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 using namespace std; 5  6 int stringToInt(string s) 7 { 8     int sum=0; 9     int flag=1;10     for(int i=0;i
        
         0 && b>0) ) 26 flag=1; 27 else 28 flag=-1; 29 30 a=abs(a); 31 b=abs(b); 32 33 if(a==0 && b==0) 34  { 35 return 0; 36  } 37 if(n==1) 38  { 39 return flag*a*b; 40  } 41 42 int a1=a/pow(10,n/2); 43 int a2=a-a1*pow(10,n/2); 44 int b1=b/pow(10,n/2); 45 int b2=b-b1*pow(10,n/2); 46 int ac=mul(a1, b1, n/2); 47 int bd=mul(a2, b2, n/2); 48 int ab=mul(a1-a2,b2-b1,n/2)+ac+bd; 49 return flag*(ac*pow(10, n)+ab*pow(10, n/2)+bd); 50 51 } 52 53 int main() 54 { 55 string s1,s2; 56 int a,b; 57 cin>>s1>>s2; 58 int len; 59 60 int len1=s1.size(); 61 int len2=s2.size(); 62 if(s1[0]=='-') 63 len1--; 64 if(s2[0]=='-') 65 len2--; 66 67 if(len1!=len2) 68  { 69 cout<<"输入错误！"<

3、合并排序

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 using namespace std; 5  6 const int MAX=1000; 7 int a[MAX]; 8 int b[MAX]; 9 10 void mymerge(int a[],int b[],int left,int mid,int right)11 { 12 int i=left,j=mid+1,k=0; 13 while(i<=mid && j<=right) 14  { 15 if(a[i]
        
         mid) 26  { 27 for(int q=j;q<=right;q++) 28 b[k++]=a[q]; 29  } 30 else 31  { 32 for(int q=i;q<=mid;q++) 33 b[k++]=a[q]; 34  } 35 36 } 37 38 void mycopy(int a[],int b[],int left,int right) 39 { 40 for(int i=left,j=0;i<=right ;i++,j++) 41 a[i]=b[j]; 42 43 } 44 45 void mergeSort(int a[],int left,int right) 46 { 47 if(left
         
          >n; 71 for(int i=0;i

4、循环赛日程表

1 #include 
     
       2 using namespace std; 3 void odd_table ( int **a , int n) 4 { 5     int i,j; 6     int *b;        //指向对阵关系数组 7  8     //建立初始对阵关系（,n-1,2,n-2,...,i,n-i） 9     b=new int [n];        //0下标不用10     for(i=1;i<=n/2;i++)11  { 12 b[2*i-1]=i; 13 b[2*i]=n-i; 14  } 15 16 for(i=1;i<=n;i++)//i控制天数变化 17  { 18 a[i][i]=0; //n为奇数时在第i天第i号运动员轮空 19 for(j=1;j<=(n-1);j+=2) 20  { 21 //第i天m1与m2对阵 22 int m1=((b[j]+i)<=n)?(b[j]+i):(b[j]+i)%n; 23 int m2=((b[j+1]+i)<=n)?(b[j+1]+i):(b[j+1]+i)%n; 24 a[m1][i]=m2; 25 a[m2][i]=m1; 26  } 27  } 28 } 29 30 int main() 31 { 32 int i,j; //循环控制变量 33 int days; //比赛天数 34 int n; //参赛队数 35 int **a; //日程表 36 37 cout<<"请输入运动员人数："; 38 cin >> n; 39 40 if (n<=1) cout<<"数据非法"; 41 else 42  { 43 a=new int* [n+1]; //行表示运动员 44 days = n%2==0?n-1:n; //比赛天数，n是偶数时,n-1天。n是奇数时,n天. 45 for(int i=1;i<=(n+1);i++) 46 a[i] = new int [days+1]; 47  } 48 49 if(n%2!=0) 50  odd_table(a,n); 51 else 52  { 53 odd_table(a,n-1); 54 //加入第n个运动员的比赛日程，只需将其加入到前n-1个运动员日程中轮空位置即可 55 for(i=1;i<=n;i++) //i控制天数变化 56  { 57 a[i][i]=n; 58 a[n][i]=i; 59  } 60  } 61 62 //输出表头 63 cout<<"\n\t"; 64 for(j=1;j<=days;j++) 65 cout<<"第"<
      
       <<"天 "; 66 cout<

5、快速幂

代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std; double po(double a,int b) { int flag=0; if (b<0) { flag=1; b=-b; } double ans=1; while (b!=0) { if((b&1)==1) ans*=a; a*=a; b>>=1; } if (flag) return 1/ans; return ans; } int main() { int a,b; cin>>a>>b; cout<
           
            <

输入示例：

3 4

输出示例：

6、二分递归版

代码：

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 using namespace std; 8 9 int bsearch(int* num,int l,int r,int n)10 {11 int mid=(l+r)/2;12 if(l>r)13 return -1; 14 if (num[mid]==n) 15 return mid; 16 else if(num[mid]>n) 17 return bsearch(num, l, mid-1, n); 18 else 19 return bsearch(num, mid+1, r, n); 20 } 21 22 23 int main() 24 { 25 int num[11]; 26 for(int i=1;i<11;i++) 27 num[i]=i; 28 int n; 29 cin>>n; 30 cout<
           
            <

输入示例：

输出示例：

第三章 DP

DP之矩阵连乘

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 using namespace std; 6  7 const int maxn=100; 8  9 void MinNum(int n,int p[],int m[maxn][maxn],int s[maxn][maxn])10 {11     for(int i=1;i<=n;i++)12         for(int j=1;j<=n;j++) 13 m[i][j]=0x3f3f3f3f; 14 for(int i=1;i<=n;i++) m[i][i]=0; 15 for(int len=1;len
         
          >n; 47 for(int i=0;i<=n;i++) 48 cin>>p[i]; 49 int m[maxn][maxn],s[maxn][maxn]; 50 51  MinNum(n,p,m,s); 52 cout<<"最少乘法次数为："<
          
           <

 DP之最长公共子序列

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 using namespace std; 6  7 const int maxn=1000; 8  9 void f(int nm,int nn,char p[],char q[],int m[maxn][maxn],int s[maxn][maxn])10 {11     for(int i=0;i<=nm;i++) m[0][i]=0;12     for(int i=0;i<=nn;i++) m[i][0]=0; 13 for(int i=1;i<=nm;i++) 14  { 15 for(int j=1;j<=nn;j++) 16  { 17 if(p[i-1]==q[j-1]) 18  { 19 //cout<
         
          <<"jj"<
          
           =m[i][j-1]) 24 { 25 m[i][j]=m[i-1][j]; 26 s[i][j]=2; 27 } 28 else 29 { 30 m[i][j]=m[i][j-1]; 31 s[i][j]=3; 32 } 33 34 } 35 } 36 cout<<"最长公共子序列长度为："<
           
            <
            
             >s1>>s2; 62 char c1[maxn],c2[maxn]; 63 int num1=s1.length(); 64 int num2=s2.length(); 65 strcpy(c1,s1.c_str()); 66 strcpy(c2,s2.c_str()); 67 int m[maxn][maxn],s[maxn][maxn]; 68 f(num1,num2,c1,c2,m,s); 69 cout<<"最长公共子序列为："; 70 show(num1,num2,c1,s); 71 cout<

DP之01背包问题

代码：

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 using namespace std; 6 const int N=100; 7 int main() 8 { 9     int v[N]={0,8,10,6,3,7,2};10     int w[N]={0,4,6,2,2,5,1}; 11 12 int m[N][N]; 13 int n=6,c=12; 14 memset(m,0,sizeof(m)); 15 for(int i=1;i<=n;i++) 16  { 17 for(int j=1;j<=c;j++) 18  { 19 if(j>=w[i]) 20 m[i][j]=max(m[i-1][j],m[i-1][j-w[i]]+v[i]); 21 else 22 m[i][j]=m[i-1][j]; 23  } 24  } 25 26 for(int i=1;i<=n;i++) 27  { 28 for(int j=1;j<=c;j++) 29  { 30 cout<
         
          <<' '; 31  } 32 cout<

输出：

0 0 0 8 8 8 8 8 8 8 8 8

0 0 0 8 8 10 10 10 10 18 18 18

0 6 6 8 8 14 14 16 16 18 18 24

0 6 6 9 9 14 14 17 17 19 19 24

0 6 6 9 9 14 14 17 17 19 21 24

2 6 8 9 11 14 16 17 19 19 21 24

DP之大币找零钱

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 using namespace std; 6 const int N=100; 7 void show(int m,int *v,int *b,int *ans) 8 { 9     if(m==0) return ;10     ans[b[m]]++; 11 show(m-v[b[m]],v,b,ans); 12 } 13 14 int main() 15 { 16 int v[N]={1,2,5}; 17 int n=3; 18 int m=23; 19 int dp[N]; 20 int b[N]; 21 for(int i=0;i<=m;i++) dp[i]=i; 22 int min=0x3f3f3f3f; 23 for(int i=1;i<=m;i++) 24  { 25 min=0x3f3f3f3f; 26 for(int j=0;j
         
          =v[j] && dp[i-v[j]]+1

DP之石子合并

代码：

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 using namespace std; 6  7 const int maxn=100; 8  9 void MinNum(int n,int p[],int m[maxn][maxn],int s[maxn][maxn])10 {11     for(int i=2;i<=n;i++)12         p[i]=p[i]+p[i-1]; 13 for(int i=1;i<=n;i++) m[i][i]=0; 14 for(int len=1;len
         
          m[i][j]) 51  { 52 m[i][j]=t; 53 s[i][j]=k; 54  } 55  } 56 m[i][j]=m[i][j]+p[j]-p[i-1]; 57  } 58  } 59 } 60 61 62 void show(int i,int j,int s[maxn][maxn]) 63 { 64 if(i==j) return; 65  show(i,s[i][j],s); 66 show(s[i][j]+1,j,s); 67 cout<<"A"<
          <<"+"<<"A"<
           
            <<" "; 68 cout<<"A"<
            
             <<"+"<<"A"<
             
              <
              
               >n; 76 n=4; 77 78 //for(int i=1;i<=n;i++) 79 // cin>>p[i]; 80 int m[maxn][maxn],s[maxn][maxn]; 81 82 MinNum(n,p,m,s); 83 cout<
               
                <

输入示例：

4 4 5 9

输出示例：

A1+A1 A2+A2

A1+A2 A3+A3

A1+A3 A4+A4

A3+A3 A4+A4

A2+A2 A3+A4

A1+A1 A2+A4

第四章贪心

贪心之最优装载

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 using namespace std; 8 9 const int maxn=100;10 11 struct node12 {13 int w;14 int num; 15 }nodes[maxn]; 16 bool cmp(node m,node n) 17 { 18 return m.w

输入示例：

4 5 3 2 6

输出示例：

The ans is

The 3th The 2th The 0th

贪心之多处最优服务次序

代码：

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 using namespace std; 7  8 const int maxn=100; 9 10 int x[maxn];11 int st[maxn];12 int su[maxn];13 14 int main() 15 { 16 int n; 17 int s; 18 cin>>n>>s; 19 int sum=0; 20 for(int i=0;i
          
           >x[i]; 23 } 24 sort(x,x+n); 25 int i=0,j=0; 26 while(i

贪心之最优服务次序

代码：

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 using namespace std; 7  8 const int maxn=100; 9 10 int x[maxn];11 12 int main()13 {14     int n; 15 cin>>n; 16 int sum=0; 17 for(int i=0;i
          
           >x[i]; 20 } 21 sort(x,x+n); 22 for(int i=1;i

贪心之汽车加油问题

问题描述：

　　一辆汽车加满油后可行驶n公里。旅途中有若干个加油站。设计一个有效算法，指出应在哪些加油站停靠加油，使沿途加油次数最少。对于给定的n(n <= 5000)和k(k <= 1000)个加油站位置，编程计算最少加油次数。并证明算法能产生一个最优解。

代码：

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 using namespace std; 5 const int maxn=100; 6 int   x[maxn]; 7 int main() 8 { 9     int n,k; 10 cin>>n>>k; 11 for(int i = 0;i <=k;i++){ 12 cin>>x[i]; 13 if(x[i]>n) 14  { 15 cout<<"No Solution!"<
        
         n) 24  { 25 ans++; 26 sum=x[i]; 27  } 28  } 29 cout<
         
          <

输入示例：

7 7

1 2 3 4 5 1 6 6

输出示例：

贪心之Dijkstra

代码：

1 #include 
     
        2 #include 
      
         3 #include 
       
          4 #include 
        
           5 #include 
         
            6 #include 
          
            7 #include 
           
             8 using namespace std; 9 10 const int maxn=100; 11 int dis[maxn]; 12 const int INF=0x3f3f3f3f; 13 int c[maxn][maxn]; 14 int pre[maxn]; 15 int n,m; 16 17 void init() 18 { 19 for(int i=1;i<=n;i++) 20 for(int j=1;j<=n;j++) 21 c[i][j]=INF; 22 for(int i=1;i<=n;i++) 23 { 24 dis[i]=INF; 25 c[i][i]=0; 26 } 27 } 28 void findpath(int t) 29 { 30 31 cout<
            
             >n>>m; 102 int a,b,cc; 103 init(); 104 for(int i=0;i
             
              >a>>b>>cc; 107 c[a][b]=cc; 108 } 109 dijkstra(1); 110 show(); 111 return 0; 112 }

输入示例：

5 7

1 2 10

1 5 100

2 3 50

4 5 60

4 3 20

1 4 30

3 5 10

输出示例：

dis[1]=0

path:1

dis[2]=10

path:2<-1

dis[3]=50

path:3<-4<-1

dis[4]=30

path:4<-1

dis[5]=60

path:5<-3<-4<-1

贪心之prim

代码：

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 #include 
           
             8 using namespace std; 9 10 const int maxn=100;11 int dis[maxn];12 const int INF=0x3f3f3f3f;13 int c[maxn][maxn];14 int close[maxn]; 15 int n,m; 16 17 void init() 18 { 19 for(int i=1;i<=n;i++) 20 for(int j=1;j<=n;j++) 21 c[i][j]=INF; 22 for(int i=1;i<=n;i++) 23 { 24 dis[i]=INF; 25 c[i][i]=0; 26 } 27 } 28 29 30 void prim(int v) 31 { 32 int vis[maxn]; 33 memset(vis,0,sizeof(vis)); 34 for(int i=1;i<=n;i++) 35 { 36 dis[i]=c[v][i]; 37 close[i]=v; 38 } 39 40 vis[v]=1; 41 for(int len=1;len
            
             >n>>m; 72 int a,b,cc; 73 init(); 74 for(int i=0;i
             
              >a>>b>>cc; 77 c[a][b]=cc; 78 c[b][a]=cc; 79 } 80 prim(1); 81 return 0; 82 }

示例输入：

5 7

1 2 10

1 5 100

2 3 50

4 5 60

4 3 20

1 4 30

3 5 10

示例输出：

2-1

4-1

3-4

5-3

贪心之kruskal

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 #include 
           
             8 using namespace std; 9 10 const int maxn=100;11 int parent[maxn];12 int n,m;13 int i,j;14 15 struct edge 16 { 17 int u,v,w; 18 }edges[maxn]; 19 20 int find(int i){ 21 int temp; 22 for(temp = i; parent[temp] >= 0; temp = parent[temp]); 23 while(temp != i){ 24 int t = parent[i]; 25 parent[i] = temp; 26 i = t; 27 } 28 return temp; 29 } 30 31 void merge(int a,int b){ 32 int r1 = find(a); 33 int r2 = find(b); 34 parent[r1]=r2; 35 } 36 37 void kruskal(){ 38 int sumWeight = 0; 39 int num = 0; 40 int u,v; 41 for(i=1; i<=n; i++) parent[i] = -1; for(int i=0; i
            
             >n>>m; 62 for(i=0; i
             
              >edges[i].u>>edges[i].v>>edges[i].w; 64 } 65 sort(edges,edges+m,cmp); 66 kruskal(); 67 68 69 return 0; 70 } 71 /* 72 测试数据： 73 7 9 74 1 2 28 75 1 6 10 76 2 3 16 77 2 7 14 78 3 4 12 79 4 5 22 80 4 7 18 81 5 6 25 82 5 7 24 83 输出： 84 1-6 85 3-4 86 2-7 87 2-3 88 4-5 89 5-6 90 weight of MST is 99 91 */

贪心之活动安排问题

问题描述：

　　设有n个活动的集合E={1,2，……，n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi，且si<fi。如果选择了活动i，则它在时间区间[si,fi]内占用资源。若区间[si,fi]与区间[sj,fj]不相交，则称活动i与活动j是相容的。也就是说，当si>=fj或者sj>=fi时，活动i与活动j相容。活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合。

代码：

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 using namespace std; 8 9 const int maxn=100;10 int vis[maxn];11 struct node12 {13 int num; 14 int s; 15 int e; 16 /* 17 bool operator<(node b) 18 { 19 if(this->e==b.e) 20 return this->s
           
            e < b.e; 22 } 23 */ 24 }nodes[maxn]; 25 bool cmp(node a,node b) 26 { 27 if(a.e
            
             =nodes[t].e) 41 { 42 vis[i]=1; 43 t=i; 44 } 45 } 46 } 47 int main() 48 { 49 int n; 50 cin>>n; 51 queue
             
               st; 52 for(int i=0;i
              
               >nodes[i].s>>nodes[i].e; 55 nodes[i].num=i; 56 } 57 sort(nodes,nodes+n,cmp); 58 memset(vis, 0, sizeof(vis)); 59 f(nodes,n); 60 for(int i=0;i

Input：

第一行输入活动的数量n。

第二行输入2*n个整数，依次表示活动的开始时间和结束时间。

Output：

　　输出要被安排的活动的编号，编号按照输入顺序从0开始编号。

输入示例：

1 3 2 4 3 5

输出示例：

　　0 2

贪心之程序存储问题

问题描述：

　　设有n 个程序{1,2,…, n }要存放在长度为L的磁带上。程序i存放在磁带上的长度是 li，1≤i≤n。程序存储问题要求确定这n 个程序在磁带上的一个存储方案，使得能够在磁带上存储尽可能多的程序。对于给定的n个程序存放在磁带上的长度，计算磁带上最多可以存储的程序数。

代码：

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 using namespace std; 5 const int maxn=100; 6 int   x[maxn]; 7  8  9 int main()10 {11     int n,l; 12 cin>>n>>l; 13 for(int i = 0;i < n;i++){ 14 cin>>x[i]; 15  } 16 int sum=0,ans=0; 17 sort(x, x+n,less
        
         ()); 18 for(int i=0;i

输入示例：

6 50

2 3 13 8 80 20

输出示例：

贪心之磁盘文件最优存储问题

问题描述：

　　设磁盘上有n个文件，f1,f2,…,fn，，每个文件占磁盘上1个磁道。这n个文件的检索概率分别是p1,p2,…,pn,且p1+p2+…+pn =1。磁头从当前磁道移到被检信息磁道所需的时间可用这2个磁道之间的径向距离来度量。如果文件pi存放在第i道上,1<i<n ，则检索这n 个文件的期望时间是 ∑（Pi*Pj*d（i，j）) ,其中 d（i，j）是第i道与第j道之间的径向距离|i-j|。

代码：

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 using namespace std; 5 const int maxn=100; 6 int   A[maxn]; 7 int   B[maxn]; 8  9 double f(int n)10 { 11 double sum = 0,t = 0; 12 int k = (n-1)/2; 13 sort(A,A+n); 14 B[k] = A[n-1]; 15 16 for(int i = k+1;i < n;i++) 17  { 18 B[i] = A[n-2*(i-k)]; 19  } 20 for(int i = k-1;i >= 0;i--) 21  { 22 B[i] = A[n-2*(k-i)-1]; 23  } 24 for (int i = 0;i < n;i++) 25  { 26 sum += A[i]; 27 for(int j = i+1; j < n;j++) 28 t += B[i]*B[j]*(j-i); 29  } 30 return t/sum/sum; 31 } 32 33 int main() 34 { 35 int i ,n; 36 cin>>n; 37 for(i = 0;i < n;i++){ 38 cin>>A[i]; 39  } 40 double ans=f(n); 41 cout<
        
         <

输入示例：

33 55 22 11 9

输出示例：

0.547396

贪心之磁带最优存储问题

问题描述：

　　设有n 个程序{1,2,…, n }要存放在长度为L的磁带上。程序i存放在磁带上的长度是Li， 1<= i<= n。这n 个程序的读取概率分别是p1,p2,...,pn,且pi+p2+...+pn = 1。如果将这n 个程序按 i1,i2,....,in 的次序存放，则读取程序ir 所需的时间tr=c*(Pi1*Li2+Pi2*Li2+...+Pir*Lir)。这n 个程序的平均读取时间为t1+t2+...+tn。磁带最优存储问题要求确定这n 个程序在磁带上的一个存储次序，使平均读取时间达到最小。

代码：

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 using namespace std; 5 const int maxn=100; 6 struct node 7 { 8     double p,l,mul; 9 }nodes[maxn]; 10 11 bool cmp(node a,node b) 12 { 13 return a.mul
        
         >n; 19 double sum=0; 20 for(int i=1;i<=n;i++) 21  { 22 cin>>nodes[i].l>>nodes[i].p; 23 sum+=nodes[i].p; 24  } 25 for(int i=1;i<=n;i++) 26  { 27 nodes[i].p=nodes[i].p/sum; 28 nodes[i].mul=nodes[i].l*nodes[i].p; 29  } 30 sort(nodes+1,nodes+n+1,cmp); 31 double t=0,ans=0; 32 for(int i=1;i<=n;i++) 33  { 34 t+=nodes[i].mul; 35 ans+=t; 36  } 37 cout<
         
          <

输入示例：

71 872

46 452

9 265

73 120

35 85

输出示例：

85.6193

贪心之会场安排问题

问题描述：

　　假设要在足够多的会场里安排一批活动，并希望使用尽可能少的会场。设计一个有效的贪心算法进行安排（这个问题实际上是著名的图着色问题。若将每一个活动作为图的一个顶点，不相容活动间用边相连。使相邻顶点着有不同颜色的最小着色数，相应于要找的最小会场数）。

代码：

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 using namespace std; 5  6 struct node 7 { 8     int data; 9     int flag;10 }; 11 12 bool cmp(node a,node b) 13 { 14 return a.data
        
          v) 18 { 19 int now=0,max=0; 20 vector
         
          ::iterator iter=v.begin(); 21 for(;iter
          
           flag==1) 24 { 25 now++; 26 if(now>max) 27 max=now; 28 } 29 else 30 { 31 now--; 32 } 33 } 34 return max; 35 } 36 37 int main() 38 { 39 int n; 40 vector
           
             vec; 41 node t; 42 int x; 43 cin>>n; 44 for(int i=1;i<=2*n;i++) 45 { 46 cin>>x; 47 t.data=x; 48 t.flag=i%2; 49 vec.push_back(t); 50 } 51 52 sort(vec.begin(),vec.end(),cmp); 53 int ans=f(vec); 54 cout<
            
             <

输入示例：

1 23

12 28

25 35

27 80

36 50

输出示例：

第五六章

分支限界法之01背包队列版

代码：

1 #include 
     
        2 #include 
      
         3 #include 
       
          4 #include 
        
           5 #include 
         
            6 using namespace std;  7   8 const int maxn=1000;  9  10 class node 11 { 12 public: 13     int id,w,p; 14 double average; 15 bool operator < (const node &a)const 16  { 17 return average>a.average; 18  }; 19 }ths[maxn]; 20 21 class bbnode 22 { 23 public: 24 bbnode *parent; 25 bool lchild; 26 bbnode(bbnode *b,bool f) 27  { 28 parent=b; 29 lchild=f; 30  }; 31 bbnode(const bbnode &a) 32  { 33 parent=a.parent; 34 lchild=a.lchild; 35  }; 36 }; 37 38 class headnode 39 { 40 public: 41 double up; 42 int cp,cw; 43 int level; 44 bbnode *bb; 45 headnode(double u,int p,int w,int l,bbnode b) 46  { 47 up=u; 48 cp=p; 49 cw=w; 50 level=l; 51 bbnode *yy=new bbnode(b.parent,b.lchild); 52 bb=yy; 53  } 54 }; 55 56 int n; 57 int c; 58 int cw; 59 int cp; 60 int bestp; 61 int best[maxn]; 62 63 bool cmpp(node a,node b) 64 { 65 return a.id
          
            que; 95 bbnode *E; 96 bbnode *beste; 97 E=0; 98 beste=0; 99 int i=1; 100 int t=bound(1); 101 while(i<=n) 102 { 103 if(cw+ths[i].w<=c) 104 { 105 if(cp+ths[i].p>bestp) 106 { 107 bestp=cp+ths[i].p; 108 beste=E; 109 } 110 que.push(headnode(t,cp+ths[i].p,cw+ths[i].w,i+1,bbnode(E,true))); 111 } 112 t=bound(i+1); 113 if(t>=bestp) 114 que.push(headnode(t,cp,cw,i+1,bbnode(E,false))); 115 headnode now=que.front(); 116 que.pop(); 117 cp=now.cp; 118 cw=now.cw; 119 i=now.level; 120 t=now.up; 121 E=now.bb; 122 } 123 if(bestp>=cp) 124 beste=E; 125 for(int j=n;j>0;j--) 126 { 127 best[j]= beste->lchild; 128 beste=beste->parent; 129 } 130 return bestp; 131 } 132 133 int main() 134 { 135 cin>>n>>c; 136 for(int i=1;i<=n;i++) 137 { 138 cin>>ths[i].p; 139 ths[i].id=i; 140 } 141 for(int i=1;i<=n;i++) 142 { 143 cin>>ths[i].w; 144 ths[i].id=i; 145 ths[i].average=1.0*ths[i].p/ths[i].w; 146 } 147 sort(ths+1,ths+n+1); 148 init(); 149 cout<
           
            <
            
              v; 151 for(int i=1;i<=n;i++) 152 if(best[i]) 153 v.push_back(ths[i]); 154 sort(v.begin(),v.end(),cmpp); 155 for(int i=0;i

输入示例1：

4 7

9 10 7 4

3 5 2 1

输出示例1：

The 1th : p=9 w=3

The 3th : p=7 w=2

The 4th : p=4 w=1

输入示例2：

6 12

8 10 6 3 7 2

4 6 2 2 5 1

输出示例2：

The 1th : p=8 w=4

The 2th : p=10 w=6

The 3th : p=6 w=2

分支限界法之01背包优先队列版

代码：

1 #include 
     
        2 #include 
      
         3 #include 
       
          4 #include 
        
           5 #include 
         
            6 using namespace std;  7   8 const int maxn=100;  9  10 class node 11 { 12 public: 13     int id,w,p; 14 double average; 15 bool operator < (const node &a)const 16  { 17 return average>a.average; 18  }; 19 }ths[maxn]; 20 21 class bbnode 22 { 23 public: 24 bbnode *parent; 25 bool lchild; 26 bbnode(bbnode *b,bool f) 27  { 28 parent=b; 29 lchild=f; 30  }; 31 }; 32 33 class headnode 34 { 35 public: 36 double up; 37 int cp,cw; 38 int level; 39 bbnode *bb; 40 headnode(double u,int p,int w,int l,bbnode b) 41  { 42 up=u; 43 cp=p; 44 cw=w; 45 level=l; 46 bbnode *yy=new bbnode(b.parent,b.lchild); 47 bb=yy; 48  } 49 bool operator < (const headnode &a)const 50  { 51 return up
          
            que; 94 bbnode *E; 95 E=0; 96 int i=1; 97 int t=bound(1); 98 while(i<=n) 99 { 100 if(cw+ths[i].w<=c) 101 { 102 if(cp+ths[i].p>bestp) 103 bestp=cp+ths[i].p; 104 que.push(headnode(t,cp+ths[i].p,cw+ths[i].w,i+1,bbnode(E,true))); 105 } 106 t=bound(i+1); 107 if(t>=bestp) 108 que.push(headnode(t,cp,cw,i+1,bbnode(E,false))); 109 headnode now=que.top(); 110 que.pop(); 111 cp=now.cp; 112 cw=now.cw; 113 i=now.level; 114 t=now.up; 115 E=now.bb; 116 } 117 for(int j=n;j>0;j--) 118 { 119 best[j]=E->lchild; 120 E=E->parent; 121 } 122 return cp; 123 } 124 125 int main() 126 { 127 cin>>n>>c; 128 for(int i=1;i<=n;i++) 129 { 130 cin>>ths[i].p; 131 ths[i].id=i; 132 } 133 for(int i=1;i<=n;i++) 134 { 135 cin>>ths[i].w; 136 ths[i].id=i; 137 ths[i].average=1.0*ths[i].p/ths[i].w; 138 } 139 sort(ths+1,ths+n+1); 140 init(); 141 cout<
           
            <
            
              v; 143 for(int i=1;i<=n;i++) 144 if(best[i]) 145 v.push_back(ths[i]); 146 sort(v.begin(),v.end(),cmpp); 147 for(int i=0;i

输入示例1：

4 7

9 10 7 4

3 5 2 1

输出示例1：

The 1th : p=9 w=3

The 3th : p=7 w=2

The 4th : p=4 w=1

输入示例2：

6 12

8 10 6 3 7 2

4 6 2 2 5 1

输出示例2：

The 1th : p=8 w=4

The 2th : p=10 w=6

The 3th : p=6 w=2

回溯法之01背包

代码：

1 #include 
     
        2 #include 
      
         3 #include 
       
          4 #include 
        
           5 #include 
         
            6 using namespace std;  7   8 const int maxn=10;  9 struct node 10 { 11     int id,w,p; 12     double average; 13 }ths[maxn]; 14 15 bool cmp(const struct node one,const struct node other) 16 { 17 return one.average>other.average; 18 } 19 bool cmpp(const struct node one,const struct node other) 20 { 21 return one.id
          
           n) 51 { 52 if(bestp
           
            bestp) 70 { 71 flag[num]=0; 72 dfs(num+1); 73 } 74 75 } 76 77 void init() 78 { 79 cw=0; 80 cp=0; 81 bestp=0; 82 memset(flag, -1, sizeof(flag)); 83 memset(bestf, -1, sizeof(bestf)); 84 } 85 86 int main() 87 { 88 cin>>n>>c; 89 for(int i=1;i<=n;i++) 90 { 91 cin>>ths[i].p; 92 ths[i].id=i; 93 } 94 for(int i=1;i<=n;i++) 95 { 96 cin>>ths[i].w; 97 ths[i].id=i; 98 ths[i].average=1.0*ths[i].p/ths[i].w; 99 } 100 sort(ths+1,ths+n+1,cmp); 101 init(); 102 dfs(1); 103 vector
            
              v; 104 cout<
             
              <

输入示例：

4 7

9 10 7 4

3 5 2 1

输出示例：

The 1th :p=9 w=3

The 3th :p=7 w=2

The 4th :p=4 w=1

回溯法之最小重量机器设计问题

问题描述：

　　设某一机器由n个部件组成，每一种部件都可以从m个不同的供应商处购得。设 w_ij 是从供应商j 处购得的部件i的重量，c_ij 是相应的价格。试设计一个回溯算法，对于给定的机器部件重量和机器部件价格，计算总价格不超过c的最小重量机器设计。

代码：

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 using namespace std; 5 const int maxn=100; 6  7 int w[maxn][maxn]; 8 int c[maxn][maxn]; 9 int best[maxn];10 int b[maxn]; 11 int n,m,d; 12 int mi=0x3f3f3f3f; 13 int cost=0; 14 int wei=0; 15 16 void f(int num) 17 { 18 if(n==num) 19  { 20 if(wei
        
         >n>>m>>d; 45 for(int i=0;i
         
          >c[i][j]; 48 for(int i=0;i
          
           >w[i][j]; 51 f(0); 52 cout<
           
            <