广东外语外贸大学算法题之回溯篇
程序员文章站
2022-07-13 16:54:44
...
子集和问题 (25分)
设集合S={x1,x2,…,xn}是一个正整数集合，c是一个正整数，子集和问题判定是否存在S的一个子集S1，使S1中的元素之和为c。试设计一个解子集和问题的回溯法，并输出利用回溯法在搜索树（按输入顺序建立）中找到的第一个解。
输入格式:
输入数据第1行有2个正整数n和c，n表示S的大小，c是子集和的目标值。接下来的1行中，有n个正整数，表示集合S中的元素。 是子集和的目标值。接下来的1 行中，有n个正整数，表示集合S中的元素。
输出格式:
输出利用回溯法找到的第一个解，以空格分隔，最后一个输出的后面有空格。当问题无解时，输出“No Solution!”。
输入样例:
在这里给出一组输入。例如：
5 10
2 2 6 5 4
输出样例:
在这里给出相应的输出。例如：
2 2 6
#include<iostream>
using namespace std;
int n,c; //n和c的意义如题，n表示S的大小，c是子集和的目标值
int sum=0; //定义一个累加器sum
int result[100000]; //用于存储各元素的选择结果，1表示被选，0表示不选
int w[100000]; //用于存储输入的元素
int temTotal; //在当前的选择结果下的元素和
int solution=0; //用于判断是否有解，0表示无解，当找到一个解后变为1，表示有解。
void Backtrack(int depth){
// cout<<"depth: "<<depth<<endl;
if(depth > n || solution || temTotal>c){ //当找到叶子节点，或者已经有解的情况，或者当前元素和大于目标值c则直接return
return;
}
if(temTotal + w[depth] <= c){ // temTotal + w[depth] <= c表示当前这个元素可以选，令result=1，进入右子树
temTotal += w[depth];
result[depth]=1;
if(temTotal == c){ //判断是否达到目标值c
for(int i =1 ;i<=n;i++) //如果达到目标值则输出结果，并停止寻找
if(result[i]) cout<<w[i]<<" ";
solution=1; //找到了解，则solution变为1，表示有解
return;
}
Backtrack(depth+1); //寻找下一层
temTotal -= w[depth]; //回溯，temTotal和result的值都要回溯
result[depth]=0;
}
if(!solution) Backtrack(depth+1); //寻找下一层
}
int main(){
cin>>n>>c;
for(int i = 1 ; i<=n;i++){
cin>>w[i];
sum+=w[i];
}
if(sum < c){ //累加器sum，把所有元素加一起，如果sum的值比目标值小，则表示肯定不可能找到解
cout<<"No Solution"<<endl;
return 0;
}
Backtrack(1);
if(!solution) cout<<"No Solution"<<endl; //此时solution为0，则！solution为1，此时表示无解
}
最佳调度问题 (25分)
假设有n（n<=20）个任务由k（k<=20）个可并行工作的机器完成。完成任务i需要的时间为ti。 试设计一个算法，对任意给定的整数n和k，以及完成任务i 需要的时间为ti ，i=1~n。计算完成这n个任务的最佳调度，使得完成全部任务的时间最早。
输入格式:
输入数据的第一行有2 个正整数n和k。第2 行的n个正整数是完成n个任务需要的时间。
输出格式:
将计算出的完成全部任务的最早时间输出到屏幕。
输入样例:
在这里给出一组输入。例如：
7 3
2 14 4 16 6 5 3
输出样例:
在这里给出相应的输出。例如：
17
#include <iostream>
using namespace std;
int n; // n个等待分配的任务
int k; // k个机器
int best=1000000; //初始化最佳调度（最短时间），初始化为一个很大的数
int work[30]; // 完成任务i所需要的时间为 work[i]
int total[30]={0}; // 分配完任务后，第i个容器完成任务所需要的时间总和为 total【i】,初始化为 0
int depth=0; // 深度，tmie【dep】表示第dep个任务需要的时间,
// 每次分配完 dep+1 , 当 dep == n 时可以得到一个分配方案, 并得到该方案所需要的时间
int ways[30];
void search(int depth) //第dep个任务的分配
{
if ( depth > n ) // 深度遍历到了叶子节点，得到一个分配方案，更新 best
{
// int Total_Time = GetTime();
int Total_Time=0;
for(int i=1;i<=k;i++)
{
Total_Time = max(total[i],Total_Time); //该分配方案所需要的时间 = 最后完成任务的那个容器所需要的时间
}
best=min(best,Total_Time);
return ;
}
for(int i=1;i<=k;i++)
{
total[i]=total[i]+work[depth]; // 将任务dep分给机器i
// 如果机器i完成任务所需要的时间 > best ， 那就没有继续往下搜索的必要了
if( total[i]<best ){
search(depth+1);
} // 继续分配第 dep+1 个任务
total[i]=total[i]-work[depth]; // 回溯，任务dep不分给机器i
//i++ , 继续讨论 任务dep分配给机器i+1的情况
}
return ;
}
int main()
{
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>work[i];
}
search(1); // 从第一层（也就是第一个任务）开始寻找
cout<<best<<endl;
return 0;
}
部落卫队问题 (25分)
原始部落byteland中的居民们为了争抢有限的资源，经常发生冲突。几乎每个居民都有它的仇敌。部落酋长为了组织一支保卫部落的队伍，希望从部落的居民中选出最多的居民入伍，并保证队伍中任何两个人都不是仇敌。
输入格式:
第一行两个正整数n和m，表示byteland部落中有n个居民，居民间有m个仇敌关系， 0<n<200, 0<m<6000。居民编号为1,2,…,n。接下来输入m行中，每行正整数u和v，表示居民u和居民v是仇敌。
输出格式:
输出部落卫队最佳组建方案中包含的居民人数。之后逐个输出卫队组成xi, 1<=i<=n, xi=0表示居民i不在卫队中，xi=1表示居民i在卫队中。
输入样例:
7 10
1 2
1 4
2 4
2 3
2 5
2 6
3 5
3 6
4 5
5 6
输出样例:
3
1 0 1 0 0 0 1
#include<iostream>
using namespace std;
int n,m; //部落中n个居民，居民间有m个仇敌关系
int enemy[300][300]; //定义一个数组，用来存仇敌关系
int tem_result[300]; //用来存储每个村民是否被选到，1表示选择，0表示不选
int result[300]; //最佳选择
int sum=0; //累加器
int max_sum=0; //最大人数
bool canIn(int k){ //该函数用于判断第k个村民是否能被选入
for(int i=1;i<=n;i++){ //遍历一遍所有村民，如果村民i被选上，并且村民i和村民k是仇敌，则k不能再选入
if(tem_result[i]&&enemy[k][i])
return false ;
}
return true;
}
//int sum_all(int tem_result[300]){
// int total=0;
// for(int i =1 ;i<=n;i++)
// if(tem_result[i]) total++;
// return total;
//}
void Backtrack(int depth){
if(depth>n){ //到达叶子结点
// sum=sum_all(tem_result);
if(sum>max_sum){ //此时判断一下当前的选择情况是否比最佳选择情况更好 ，是的话就更新最佳选择情况
for(int i = 1;i<=n;i++){
result[i]=tem_result[i];
}
max_sum=sum;
}
return ;
}
if(canIn(depth)){ //利用函数canIn(depth)判断一下的depth个村民能不能被选入
tem_result[depth]=1; //置1表示选入
// sum=sum_all(tem_result);
sum++; //累加器加1
if(sum+n-depth>max_sum) Backtrack(depth+1); //sum表示当前已经选入的人数，n-depth表示还有多少人没被选，如果sum+n-depth小于max_sum则没有必要再去往下查找了
tem_result[depth]=0; //回溯，tem_result置0 ，并且人数减1
sum--;
}
Backtrack(depth+1); //第depth村民不选入的情况，继续向下查询
}
int main(){
int x,y;
cin>>n>>m;
for(int i=0;i<m;i++){
cin>>x>>y;
enemy[x][y]=1;
enemy[y][x]=1;
}
Backtrack(1);
cout<<max_sum<<endl;
for(int i=1;i<=n;i++)
cout<<result[i]<<" ";
}
最小重量机器设计问题 (25分)
设某一机器由n个部件组成，每一种部件都可以从m个不同的供应商处购得。设w
ij
是从供应商j 处购得的部件i的重量，c
ij
是相应的价格。 试设计一个算法，给出总价格不超过d的最小重量机器设计。
输入格式:
第一行有3 个正整数n ，m和d， 0<n<30, 0<m<30, 接下来的2n 行，每行n个数。前n行是c，后n行是w。
输出格式:
输出计算出的最小重量，以及每个部件的供应商
输入样例:
3 3 4
1 2 3
3 2 1
2 2 2
1 2 3
3 2 1
2 2 2
输出样例:
在这里给出相应的输出。例如：
4
1 3 1
#include<iostream>
using namespace std;
int n,m,d; // n个部件 ,m个不同的供应商处,最大总价格d
int weight[40][40]; // weight[i][j] 表示j商家 提供的 i部件的重量
int price[40][40]; // price[i][j] 表示 商家j 提供的 部件i 的价格
int min_weight=999999;
int result[40]; //最好路径，哪个部件用了哪些商家的货
int tem_result[40]; // 当前方案所选择的路径 , tem_result[i]表示第i个部件选的商家
int total_price = 0; // 当前总价格
int total_weight = 0; // 当前总重量
void Backtrack(int depth){
if(depth>n){ //寻找到叶节点
if(total_weight<min_weight){ //如果当前这个选择的部件总重量比最佳的总重量还小，则更新最佳选择
for(int i = 1;i<=n;i++)
result[i]=tem_result[i];
min_weight=total_weight;
}
return;
}
for(int i = 1 ;i<=m;i++){ //m个商店，对应就是n层的m个分叉的树
tem_result[depth]=i;
total_price += price[depth][i] ;
total_weight += weight[depth][i];
if(total_price <= d && total_weight <min_weight){ //当前选择方案的部件总重量不超过最优总重量并且总价钱没有超过规定的d，则可以选择，并向下查找
Backtrack(depth+1);
}
tem_result[depth]=0; //回溯，更新信息
total_price -= price[depth][i] ;
total_weight -= weight[depth][i];
}
}
int main()
{
cin>>n>>m>>d;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>price[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>weight[i][j];
}
}
Backtrack(1);
cout<<min_weight<<endl;
for(int i=1;i<=n;i++)
{
cout<<result[i]<<" ";
}
return 0;
}
喜欢的朋友们记得点点赞哦
推荐阅读