一道看似简单毫无头绪的问题 -_-||
题目：有编号分别为 1…n 的 n 本书，准备分给 n 个人，每个人阅读兴趣用一个二维数组加以描述，
1：喜欢这本书 0: 不喜欢这本书
like[i][j] = 1 , i 喜欢书 j
like[i][j] = 0 , i 不喜欢书 j
求解如何分书让所有人都满意
n个人n本书。。。。
分析：根据书上的解答，可以这么理解：
如：
6
1 0 0 0 0 0 （喜欢第一本书，不喜欢第2，3，4，5，6本书）
0 1 1 1 1 1
1 1 0 0 0 0
0 0 0 0 1 0
1 1 0 0 1 1
1 0 1 0 0 0
- 第一个人：我选第一本书，剩下的你们自己分配，可以人手一本吗？（递归层1）
- 第二个人：我选第二本书，剩下的你们自己分配，可以人手一本吗？（递归层2）
- 第三个人：不行！我只喜欢第一本和第二本，递归失败，返回递归层2（递归层3）
- 第二个人：那我选第三本，剩下的你们自己分配，可以人手一本吗？（递归层2）
- 第三个人：我选第二本书，剩下的你们自己分配，可以人手一本吗？（递归层3）
- 第四个人：我选第五本书，剩下的你们自己分配，可以人手一本吗？（递归层4）
- 第五个人：我选第六本书，剩下的你们自己分配，可以人手一本吗？（递归层5）
- 第六个人：不行，我没喜欢的书了（递归层6）
- 第五个人：不行，这样无法分配（递归层5）
- 第四个人：不行，这样无法分配（递归层4）
- 第三个人：不行，这样无法分配（递归层3）
- 第二个人：那我选第四本，剩下的你们自己分配，可以人手一本吗？（递归层2）
- 第三个人：我选第二本书，剩下的你们自己分配，可以人手一本吗？（递归层3）
- 第四个人：我选第五本书，剩下的你们自己分配，可以人手一本吗？（递归层4）
- 第五个人：我选第六本书，剩下的你们自己分配，可以人手一本吗？（递归层5）
- 第六个人：我选第三本书，这样可以人手一本，递归结束（递归层6）
虽然理解倒是不难，但是写起代码来真要命…… 因为我的逻辑感真的不强。
代码勉强写完，勉强弄明白，还需要回头多看看啊。。 真是为自己的未来担忧。。
代码如下：（写下作为记录，抽空找个大佬给我捋一捋。。。）
#include <iostream>
using namespace std;
#define N 550
int like[N][N]; // like[i][j]=1 第i个人喜欢第j本书(0表示不喜欢)
int answer[N],n; // answer[m]=i 记录第m个人选择了第i本书
bool selected[N]; // selected[i]=1 第i本书已经被选(0表示没被选)
bool search(int m){
if( m == n){
return true;
}
for(int i=0; i<n; i++){
if( !selected[i] && like[m][i]){
answer[m] = i+1; //第m个人选择了第i本书；
selected[i] = 1;
if(search(m+1))
return true; //第m+1个人没有喜欢的书了，退还第i本书
selected[i] = 0;
}
}
return false;
}
int main(){
cout<<"-----选书开始----"<<endl;
cout<<"请输入本次一共多少人："<<endl;
while(scanf("%d",&n)!=EOF){
memset(selected,0,sizeof(selected));
memset(answer,0,sizeof(answer));
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
printf("第%d个人是否喜欢第%d本书，喜欢1，不喜欢0:",i+1,j+1);
scanf("%d",&like[i][j]);
if(search(0)){
printf("第%d个人选择了第%d本书
",1,answer[0]);
for(int i=1; i<n; i++){
printf("第%d个人选择了第%d本书",i+1,answer[i]);
printf("
");
}
}
}
}
cout<<"-----本轮结束-----"<<endl;
}
return 0;
}