題目描述如下：
ABCDE五人安排工作日程，每人每星期工作5天休息2天
1) 必須有3天所有人都要上班
2) 每個人連續(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é)題思路：
題目的每個解是一個5*7的01矩陣，枚舉每一個矩陣，然后用題目所給的條件判定即可，時間復(fù)雜度為O(2^35)，明顯超時。結(jié)合題目條件“每人每星期工作5天休息2天”，我們可以完成初步剪枝：對每個人的工作表，可以看成在五個1中插入兩個0，0的具體位置可以看成一個組合問題，既是在6個位置中選擇兩個位置（這里已經(jīng)排除兩個0相鄰的情況，因為條件2）。這樣，題目的復(fù)雜度為O((C26)^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}
/**//*
* 每個員工使用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，當(dāng)前員工（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;
}
}
posted on 2013-07-06 15:43
小鼠標(biāo) 閱讀(220)
評論(0) 編輯 收藏 引用 所屬分類:
Java基礎(chǔ)練習(xí)