目录
每日一诗
红豆生南国,春来发几枝。
愿君多采撷,此物最相思。
Red beans grow in the south.In spring, how many branches sprout?
I hope you pick many.This thing evokes the most yearning.
先言
今天讲解搜索与回溯算法的第二期,会着重讲解剩下的部分例题,还会留下小练习作为作业
正文
例题六
题目描述
设有A,B,C,D,E五人从事J1,J2,J3,J4,J5五项工作,每人只能从事一项,他们的效益如下。
每人选择五项工作中的一项,在各种选择的组合中,找到效益最高的的一种组合输出。
算法分析
⒈用数组f储存工作选择的方案;数组g存放最优的工作选择方案;数组p用于表示某项工作有没有被选择了。
⒉(1)选择p(i)=0的第i项工作;
(2)判断效益是否高于max已记录的效益,若高于则更新g数组及max的值。
⒊搜索策略: 回溯法(深度优先搜索dfs)。
标准程序
#include<bits/stdc++.h>
using namespace std;
int data[6][6]={{0,0,0,0,0,0},{0,13,11,10,4,7},{0,13,10,10,8,5},{0,5,9,7,7,4},
{0,15,12,10,11,5},{0,10,11,8,8,4}};
int max1=0,g[10],f[10];
bool p[6]={0};
int go(int step,int t) // step是第几个人,t是之前已得的效益
{
for (int i=1;i<=5;i++)
if (!p[i]) //判断第i项工作没人选择
{
f[step]=i; //第step个人,就选第i项工作
p[i]=1; //标记第i项工作被人安排了
t+=data[step][i]; //计算效益值
if (step<5) go(step+1,t);
else if (t>max1) //保存最佳效益值
{
max1=t;
for (int j=1;j<=5;j++)
g[j]=f[j]; //保存最优效益下的工作选择方案
}
t-=data[step][i]; //回溯
p[i]=0;
}
}
int main()
{
go(1,0); //从第1个人,总效益为0开始
for (int i=1;i<=5;i++)
cout<<char(64+i)<<":J"<<g[i]<<setw(3); //输出各项工作安排情况
cout<<endl;
cout<<"supply:"<<max1<<endl; //输出最佳效益值
}
例题七:选书
题目描述
学校放寒假时,信息学竞赛辅导老师有A,B,C,D,E五本书,要分给参加培训的张、王、刘、孙、李五位同学,每人只能选一本书。老师事先让每个人将自己喜欢的书填写在如下的表格中。然后根据他们填写的表来分配书本,希望设计一个程序帮助老师求出所有可能的分配方案,使每个学生都满意。
算法分析
可用穷举法,先不考虑“每人都满意” 这一条件,这样只剩“每人选一本且只能选一本”这一条件。在这个条件下,可行解就是五本书的所有全排列,一共有5!=120种。然后在120种可行解中一一删去不符合“每人都满意”的解,留下的就是本题的解答。
为了编程方便,设1,2,3,4,5分别表示这五本书。这五个数的一种全排列就是五本书的一种分法。例如54321就表示第5本书(即E)分给张,第4本书(即D)分给王,……,第1本书(即A)分给李。“喜爱书表”可以用二维数组来表示,1表示喜爱,0表示不喜爱。
算法设计:S1:产生5个数字的一个全排列;
S2:检查是否符合“喜爱书表”的条件,如果符合就打印出来;
S3:检查是否所有的排列都产生了,如果没有产生完,则返回S1;
S4:结束。
上述算法有可以改进的地方。比如产生了一个全排列12345,从表中可以看出,选第一本书即给张同学的书,1是不可能的,因为张只喜欢第3、4本书。这就是说,1××××一类的分法都不符合条件。由此想到,如果选定第一本书后,就立即检查一下是否符合条件,发现1是不符合的,后面的四个数字就不必选了,这样就减少了运算量。换句话说,第一个数字只在3、4中选择,这样就可以减少3/5的运算量。同理,选定了第一个数字后,也不应该把其他4个数字一次选定,而是选择了第二个数字后,就立即检查是否符合条件。例如,第一个数选3,第二个数选4后,立即检查,发现不符合条件,就应另选第二个数。这样就把34×××一类的分法在产生前就删去了。又减少了一部分运算量。
综上所述,改进后的算法应该是:在产生排列时,每增加一个数,就检查该数是否符合条件,不符合,就立刻换一个,符合条件后,再产生下一个数。因为从第I本书到第I+1本书的寻找过程是相同的,所以可以用回溯算法。算法设计如下(不是标准程序,只是思路):
int Search(i)
{
for (j=1;j<=5;j++)
{
if (第i个同学分给第j本书符合条件)
{
记录第i个数
if (i==5) 打印一个解;
else Search(i+1);
删去第i 个数
}
}
}
标准程序
#include<bits/stdc++.h>
using namespace std;
int book[6],c;
bool flag[6],like[6][6]={{0,0,0,0,0,0},{0,0,0,1,1,0},{0,1,1,0,0,1},
{0,0,1,1,0,0},{0,0,0,0,1,0},{0,0,1,0,0,1}};;
int search(int);
int print();
int main()
{
for (int i=1;i<=5;i++) flag[i]=1;
search(1); //从第1个开始选书,递归。
}
int search(int i) //递归函数
{
for (int j=1;j<=5; j++) //每个人都有5本书可选
if (flag[j]&&like[i][j]) //满足分书的条件
{
flag[j]=0; //把被选中的书放入集合flag中,避免重复被选
book[i]=j; //保存第i个人选中的第j本书
if (i==5) print(); //i=5时,所有的人都分到书,输出结果
else search(i+1); //i<5时,继续递归分书
flag[j]=1; //回溯:把选中的书放回,产生其他分书的方案
book[i]=0;
}
}
int print()
{
c++; //方案数累加1
cout <<"answer " <<c <<":\n";
for (int i=1;i<=5;i++)
cout <<i <<": " <<char(64+book[i]) <<endl; //输出分书的方案
}
输出
answer 1
1: C
2: A
3: B
4: D
5: E
例题八:跳马问题
题目描述
在5*5格的棋盘上,有一只中国象棋的马,从(1,1)点出发,按日字跳马,它可以朝8个方向跳,但不允许出界或跳到已跳过的格子上,要求在跳遍整个棋盘。
输出前5个方案及总方案数。
输出格式示例:
1 16 21 10 25
20 11 24 15 22
17 2 19 6 9
12 7 4 23 14
3 18 13 8 5
标准程序
#include<bits/stdc++.h>
using namespace std;
int u[8]={1,2,2,1,-1,-2,-2,-1}, //8个方向上的x,y增量
v[8]={-2,-1,1,2,2,1,-1,-2};
int a[100][100]={0},num=0; //记每一步走在棋盘的哪一格和棋盘的每一格有没有被走过
bool b[100][100]={0};
int search(int,int,int); //以每一格为阶段,在每一阶段中试遍8个方向
int print(); //打印方案
int search(int i,int j,int n)
{
int k,x,y; //这三个变量一定要定义局部变量
if (n>25) { print(); return 0; } //达到最大规模打印、统计方案
for (k=0;k<=7;k++) //试遍8个方向
{
x=i+u[k];y=j+v[k]; //走此方向,得到的新坐标
if (x<=5&&x>=1&&y<=5&&y>=1&&(!b[x][y]))
{ //如果新坐标在棋盘上,并且这一格可以走
b[x][y]=1;
a[x][y]=n;
search(x,y,n+1); //从(x,y)去搜下一步该如何走
b[x][y]=0;
a[x][y]=0;
}
}
}
int print()
{
num++; //统计总方案
if (num<=5) //打印出前5种方案
{
for (int k=1;k<=5;k++) //打印本次方案
{
for (int kk=1;kk<=5;kk++)
cout<<setw(5)<<a[k][kk];
cout<<endl;
}
}
}
小练习
因为OJ题库出了点问题,导致无法放置太多题目,这里给大家一个最简单的题目
题目描述
斐波那契数列0,1,1,2,3,5,8,13,21,34,55……从第三项起,每一项都是紧挨着的前两项的和。写出计算斐波那契数列任意一个数据项的递归程序。
输入
所求项数
输出
数据项的值
样例输入 复制
10
样例输出 复制
34
标签:本书,10,题目,int,编程,C++,算法,回溯,例题
From: https://blog.csdn.net/weixin_68261272/article/details/141969199