题解 P1657 【选书】

· · 题解

【算法分析】

可用穷举法，先不考虑“每人都满意” 这一条件，这样只剩“每人选一本且只能选一本”这一条件。在这个条件下，可行解就是五本书的所有全排列，一共有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×××一类的分法在产生前就删去了。又减少了一部分运算量。

【参考程序】

#include<cstdio>
#include<iostream>
#include<cstdlib>
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;  //输出分书的方案
}

输出结果： zhang: C

wang: A

liu: B sun: D li: E