主要内容 #
- 问题描述
- 计算方法
- 参考代码
1. 问题描述 #
学校放寒假时，信息学竞赛辅导老师有A，B，C，D，E五本书，要分给参加培训的张、王、刘、孙、李五位同学，每人只能选一本书。老师事先让每个人将自己喜欢的书填写在如下的表格中。然后根据他们填写的表来分配书本，希望设计一个程序帮助老师求出所有可能的分配方案，使每个学生都满意。
2. 计算方法 #
穷举法
可用穷举法，先不考虑“每人都满意” 这一条件，这样只剩“每人选一本且只能选一本”这一条件。在这个条件下，可行解就是五本书的所有全排列，一共有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 个数;
}
}
}
3. 参考代码 #
#include < iostream >
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}};
void search(int);
void print();
int main()
{
for (int i=1;i<=5;i++) flag[i]=1; //将所有书都设置为可选的
search(1); //从第1个开始选书，递归。
}
void 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;
}
}
void print()
{
c++; //方案数累加1
cout <<"answer " <<c<<":\n";
for (int i=1;i<=5;i++)
cout <<i <<": " <<char(64+book[i]) <<endl; //输出分书的方案
}
