題目描述如下：

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

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

2)        每個(gè)人連續(xù)上班不超過3天，周日到周一是連續(xù)工作

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

結(jié)題思路：

題目的每個(gè)解是一個(gè)5*7的01矩陣，枚舉每一個(gè)矩陣，然后用題目所給的條件判定即可，時(shí)間復(fù)雜度為O(2^35)，明顯超時(shí)。結(jié)合題目條件“每人每星期工作5天休息2天”，我們可以完成初步剪枝：對(duì)每個(gè)人的工作表，可以看成在五個(gè)1中插入兩個(gè)0，0的具體位置可以看成一個(gè)組合問題，既是在6個(gè)位置中選擇兩個(gè)位置（這里已經(jīng)排除兩個(gè)0相鄰的情況，因?yàn)闂l件2）。這樣，題目的復(fù)雜度為O((C²₆)^5)，相當(dāng)小啦。除了條件1，其余的條件判斷均可在排列過程中進(jìn)行，作為剪枝只用。

 代碼如下：

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}    
        /**//*
         * 每個(gè)員工使用num[][]的一行完成組合，
         * 避免別的員工組合計(jì)算時(shí)的殘留值
         */
    };
    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，當(dāng)前員工（0,1,2,3,4）
         * nowp,left用于計(jì)算組合
         */
        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;
    }
}