实验五回溯法一、实验目的进一步理解回溯算法的基本思想，学会根据具体问题确定相应的解空间树（子集树或排列树），并使用回溯法求解。

二、实验要求1、上机前的准备工作根据实验内容中所给题目，利用所学回溯法的基本设计思想设计算法并编写好上机程序，以提高上机效率；2、独立上机，输入、调试所编程序；3、上机结束后，写出实验报告。

4、上机时间：2学时三、实验内容1、算法分析题5-1#include <iostream>using namespace std;int n=4; //集装箱数int w[5]={0,8,6,2,3}; //集装箱重量数组int c=12; //第一艘轮船的载重量int cw; //当前载重量int bestw; //当前最优载重量int r; //剩余集装箱重量void backtrack(int i);void main(){int i;cw=0;bestw=0;for(i=1;i<=n;i++)r+=w[i];backtrack(1);cout<<"最优载重量为:"<<bestw<<endl;cout<<endl;}void backtrack(int i){int j;if(i>n && cw>bestw){bestw=cw;return;}r-=w[i];if(cw+w[i]<=c){cw+=w[i];backtrack(i+1);cw-=w[i];}if(cw+r>bestw){backtrack(i+1);}r+=w[i];}运行结果：2、5-3#include<iostream>using namespace std;const int N=100;const int M=100;int n;//部件数int m;//供应商int w[N][M];int p[N][M];int bestx[N];//最优解int x[N];int bestw=9999;//当前最优重量int cw;//当前重量int cp;//当前价值int d;//价格允许的最大值void Backtrack(int t);void main(){cout<<"请输入部件的个数：";cin>>n;cout<<"请输入供应商的个数：";cin>>m;cout<<"请输入价格的最大值：";cin>>d;cout<<"请依次输入重量："<<endl;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>w[i][j];cout<<"请依次输入价格："<<endl;for(int k=1;k<=n;k++)for(int t=1;t<=m;t++)cin>>w[k][t];Backtrack(1);cout<<"最小重量为："<<bestw<<endl; for(int t=1;t<=m;t++)cout<<bestx[t]<<" ";cout<<endl;}void Backtrack(int t){if(t>n){for(int j=1;j<=n;j++)bestx[j]=x[j];bestw=cw;}else{for(int i=1;i<=m;i++){x[t]=i;cw+=w[t][i];cp+=p[t][i];if(cp<=d&&cw<bestw)Backtrack(t+1);cw-=w[t][i];cp-=p[t][i];}}}运行结果：3、5-4#include<iostream>using namespace std;const int N=100;int n;//男（女）运动员个数int r[N+1];int p[N+1][N+1];int q[N+1][N+1];int bestr[N+1];int best;//当前最优值void swap(int &a,int &b);void Backtrack(int t);void main(){cout<<"请输入男（女）运动员个数：";cin>>n;for(int a=1;a<=n;a++)r[a]=a;cout<<"请依次输入男i女j混合双打的竞赛优势："<<endl;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cin>>p[i][j];cout<<"请依次输入女i男j混合双打的竞赛优势："<<endl;for(int k=1;k<=n;k++)for(int t=1;t<=n;t++)cin>>q[k][t];Backtrack(1);cout<<"竞赛优势最优为："<<best<<endl;for(int t=1;t<=n;t++)cout<<bestr[t]<<" ";cout<<endl;}void swap(int &a,int &b){int temp;temp=a;a=b;b=temp;}void Backtrack(int t){if(t>n){ int sum=0;for(int j=1;j<=n;j++)sum+=p[j][r[j]]*q[r[j]][j];if(sum>best){best=sum;for(int k=1;k<=n;k++)bestr[k]=r[k];}}else{for(int i=t;i<=n;i++){swap(r[i],r[t]);Backtrack(t+1);swap(r[i],r[t]);}}}运行结果：4、5-13#include<iostream>using namespace std;const int N=100;int n;int r[N+1];int p[N+1][N+1];int bestr[N+1];int best=9999;void swap(int &a,int &b);void Backtrack(int t);void main(){cout<<"请输入工作件数（人数）：";cin>>n;for(int j=1;j<=n;j++)r[j]=j;cout<<"请输入工作费用："<<endl;for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)cin>>p[k][i];Backtrack(1);cout<<"最优费用为："<<best<<endl;for(int t=1;t<=n;t++)cout<<bestr[t]<<" ";cout<<endl;}void swap(int &a,int &b){int temp;temp=a;a=b;b=temp;}void Backtrack(int t){if(t>n){ int sum=0;for(int j=1;j<=n;j++)sum+=p[j][r[j]];if(sum<best){best=sum;for(int k=1;k<=n;k++)bestr[k]=r[k];}}else{for(int i=t;i<=n;i++){swap(r[i],r[t]);Backtrack(t+1);swap(r[i],r[t]);}}}运行结果：5、5-15#include <iostream>using namespace std;const int N=100;const int K=100;int best=9999;int n; //任务数int k; //机器数int len[K];int t[N];int x[N];int bestx[N];void backtrack(int a);void main(){cout<<"请输入任务的个数：";cin>>n;cout<<"请输入机器的个数：";cin>>k;cout<<"请依次输入各个任务的时间：";for(int i=1;i<=n;i++)cin>>t[i];backtrack(1);cout<<"最优时间为："<<best<<endl;for(int j=1;j<=n;j++)cout<<"第"<<j<<"个任务在"<<bestx[j]<<"号机器上"<<endl; }void backtrack(int a){if(a>n){for(int j=1;j<=n;j++)bestx[j]=x[j];int time=0;//for循环内求完成任务的时间for(int i=1;i<=k;i++){if(len[i]>time)time=len[i];}if(time<best)best=time;}else{for(int i=1;i<=k;i++){len[i]+=t[a];x[a]=i;if(len[i]<best)backtrack(a+1);len[i]-=t[a];}}}运行结果：。