题目

学校放寒假时，信息学竞赛辅导老师有A，B，C，D，E五本书，要分给参加培训的张、王、刘、孙、李五位同学，每人只能选一本书。老师事先让每个人将自己喜欢的书填写在如下的表格中。然后根据他们填写的表来分配书本，希望设计一个程序帮助老师求出所有可能的分配方案，使每个学生都满意。

	A	B	C	D	E
张同学	-	-	Y	Y	-
王同学	Y	Y	-	-	Y
刘同学	-	Y	Y	-	-
孙同学	-	-	-	Y	-
李同学	-	Y	-	-	Y

简析

套模版练习题，和系列十五工作效率问题是类似的。定义数据如下：

• data[6][6]: 保存每个人喜欢的书
• flag[6]: 保存每本书的被选状态，选中或还没被选
• book[k]: 保存第K个人选了哪本书

1 for循环范围

可选范围为1～5，五本书都可以尝试选

    for(int i=1;i<=5;i++)

2 可选条件

如果这本书还没被选，并且这个人喜欢这本书

if(!flag[i]&&data[k][i])

3 选中后的变化

• 这本书设置为不可选
• 结果数组book[k]设为这本书编号

flag[i]=1;
book[k]=i;

4 结束条件

如果k为5，说明五个人都选到了。

if(k==5) print();
else go(k+1);

回溯

选中状态去掉即可

flag[i]=0;

代码

#include <iostream>
using namespace std;
int data[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 flag[6]={0};
int book[6];
int total;
void print(){
    total++;
    for(int i=1;i<=5;i++){
        char ch=book[i]+64;
        cout<<ch<<" ";
    }
    cout<<endl;
}
void go(int k){
    for(int i=1;i<=5;i++){
        if(!flag[i]&&data[k][i]){//可选并且这个人喜欢
            flag[i]=1;
            book[k]=i;
            if(k==5) print();
            else go(k+1);
            flag[i]=0;
        }
    }
}
int main(){
    go(1);
    cout<<total;
}