美文网首页
选书(深搜)

选书(深搜)

作者: 番薯夹islandfsj | 来源:发表于2018-09-17 23:21 被阅读0次

    问题描述

    n个同学分n本书,每个人都有自己喜欢的书(即a[i][j]==1),求出所有的分配方案

    #include<iostream> 
    #include<string>
    
    using namespace std;
    
    string name[25];//n个学生的名字 ,用于读入 
    int c,n;//c记录可能的情况的个数,用于输出 
    int flag[25],book[25],a[25][25];//flag记录第i本书是否被分,book记录第i个学生分到的书,a数组如题
    
    void printx(){
        cout<<"answer"<<c<<":"<<endl;
        for (int i=1;i<n;i++){
            char ch=64+book[i]; 
            cout<<name[i]<<":"<<ch<<endl;
        }
    }//输出第c种可能的情况 
    
    void tried(int step){
        if (step==n+1){
            printx();
            return;
        }//所有人都分配过了就输出这种情况 
        for(int i=1;i<=n;i++){
            if(a[step][i]==1&&flag[i]==0){//第step个人对第i本书有兴趣,且第i本书没被分 
                flag[i]=1;
                book[step]=i;//记录
                tried(step+1);//递归
                flag[i]=0;
                book[step]=0;//回溯 
            }
        }
    }
    
    int main(){
        cin>>n;
        for(int i=1;i<=n;i++)
          flag[i]=0;//初始化flag数组,要养成这个习惯
        for(int i=1;i<=n;i++)
          cin>>name[i];//输入学生姓名 
        for(int i=1;i<=n;i++)
          for(int j=1;j<=n;j++)
            cin>>a[i][j];
        tried(1);//从第一个学生开始分书
        return 0; 
    }
    

    相关文章

      网友评论

          本文标题:选书(深搜)

          本文链接:https://www.haomeiwen.com/subject/zkgdnftx.html