题目描述如下：

ABCDE五人安排工作日程，每人每星期工作5天休息2天

1)        必须有3天所有人都要上班

2)        每个人连续上班不超过3天，周日到周一是连续工作

3)        A、C星期三必须上班

4)        B、D、E星期天都不上班

5)        A、C一星期至少见4次

6)        A、B、C、D中每天必须至少有2人上班

输出所有从星期一到星期天可能的情况，每种情况间用空行隔开，0代表不上班，1代表上班。

例：

1 0 1 1 1 0 1

1 1 0 1 1 1 0

1 0 1 1 1 0 1

1 1 0 1 1 1 0

1 1 0 1 1 1 0

结题思路：

题目的每个解是一个5*7的01矩阵，枚举每一个矩阵，然后用题目所给的条件判定即可，时间复杂度为O(2^35)，明显超时。结合题目条件“每人每星期工作5天休息2天”，我们可以完成初步剪枝：对每个人的工作表，可以看成在五个1中插入两个0，0的具体位置可以看成一个组合问题，既是在6个位置中选择两个位置（这里已经排除两个0相邻的情况，因为条件2）。这样，题目的复杂度为O((C²₆)^5)，相当小啦。除了条件1，其余的条件判断均可在排列过程中进行，作为剪枝只用。

 代码如下：

public class Main {
    
    
    static int mp[][] = new int[5][7];
    static int count;
    static int num[][] = {
        {0, 1, 2, 3, 4, 5},
        {0, 1, 2, 3, 4, 5},
        {0, 1, 2, 3, 4, 5},
        {0, 1, 2, 3, 4, 5},
        {0, 1, 2, 3, 4, 5}    
        /**//*
         * 每个员工使用num[][]的一行完成组合，
         * 避免别的员工组合计算时的残留值
         */
    };
    public static void main(String[] args) {
        count = 0;
        DFS(0, 0, 0);
        System.out.println("count=" + count);
        for(int i = 0; i < num.length; i++){
            for(int n : num[i])
                System.out.print(n + " ");
            System.out.print("\n");
        }
        
    }
    static void outmp(){
        System.out.println();
        for(int i = 0; i < 5; i++){
            for(int j = 0; j < 7; j++)
                System.out.print(mp[i][j] + " ");
            System.out.println();
        }
    }
    static void DFS(int c, int nowp, int left){
        /**//*
         * c，当前员工（0,1,2,3,4）
         * nowp,left用于计算组合
         */
        if(c >= 5){
            if(R1()){
                outmp();
                count++;
            }
            return;
        }
        if(nowp == 2){
            makemp(c, num[c][0], num[c][1]);
            if(!R2(c))//R2
                return;
            if(c == 0 && mp[0][2] != 1)//R3
                return;
            if(c == 2 && mp[2][2] != 1)
                return;
            if(c == 1 && mp[1][6] != 0)//R4
                return;
            if(c == 3 && mp[3][6] != 0)
                return;
            if(c == 4 && mp[4][6] != 0)
                return;
            if(c == 2 && !R5())//R5
                return;
            if(c == 3 && !R6())//R6
                return;
            
            DFS(c + 1, 0, 0);
        }
        else{
            for(int i = left; i < num[0].length; i++){
                swap(num[c], nowp, i);
                DFS(c, nowp + 1, i + 1);
                swap(num[c], nowp, i);
            }
        }
    }
    static void makemp(int c, int a, int b){
        for(int i = 0; i < a; i++)
            mp[c][i] = 1;
        mp[c][a] = 0;
        for(int i = a + 1; i <= b; i++)
            mp[c][i] = 1;
        mp[c][b + 1] = 0;
        for(int i = b + 2; i < 7; i++)
            mp[c][i] = 1;
    }
    static boolean R1(){
        int count = 0; 
        for(int i = 0; i < 7; i++){
            if(chechRol(i))
                count++;
        }
        if(count >= 3)
            return true;
        return false;
    }
    static boolean chechRol(int r){
        for(int i = 0; i < 5; i++)
            if(mp[i][r] != 1)
                return false;
        return true;
    }
    static boolean R2(int c){//one person
        int count = 0;
        boolean bg = false;
        for(int i = 0; i < 7; i++){
            if(mp[c][i] != 0){
                if(bg == false){
                    count = 1;
                    bg = true;
                }
                else{
                    count++;
                    if(count > 3)
                        return false;
                }
            }
            else{
                bg = false;
            }
        }
        return true;
    }
    static boolean R5(){
        int count = 0;
        for(int i = 0; i < 7; i++){
            if(mp[0][i] == 1 && mp[2][i] == 1)
                count++;
        }
        if(count >= 4)
            return true;
        return false;
    }
    static boolean R6(){
        int count = 0;
        for(int i = 0; i < 7; i++){
            count = 0;
            for(int j = 0; j < 5; j++)
                if(mp[j][i] == 1)
                    count++;
            if(count < 2)
                return false;
        }
        return true;
    }
    static void swap(int a[], int n, int m){
        int t = a[n];
        a[n] = a[m];
        a[m] = t;
    }
}