批处理作业调度

来源：https://www.xin3721.com/Articlenet/3096.html

问题描述

给定n个作业的集合J=（J1，J2，… ，Jn）。每一个作业Ji都有两项任务分别在2台机器上完成。每个作业必须先有机器1处理，然后再由机器2处理。作业Ji需要机器j的处理时间为tji。对于一个确定的作业调度，设Fji是作业i在机器j上完成处理时间。则所有作业在机器2上完成处理时间和f=F2i，称为该作业调度的完成时间和。

简单描述

对于给定的n个作业，指定最佳作业调度方案，使其完成时间和达到最小。

举例说明

tji 机器1 机器2
作业1 2 1
作业2 3 1
作业3 2 3

这3个作业的调度方案共有6种（即3个作业的全排列），分别是123,132,213,231,312,321，它们所相应的完成时间和分别是19,18,20,21,19,19。显而易见，最佳调度方案是132，其完成时间和为18。

算法设计

从n个作业中找出有最小完成时间和的作业调度，所以批处理作业调度问题的解空间是一棵排列树。按照回溯法搜索排列树的算法框架，设开始时x=[1,2, … , n]是所给的n个作业，则相应的排列树由x[1:n]的所有排列构成。

类Flowshop的数据成员记录解空间的结点信息，以便减少传给Backtrack的参数。二维数组M是输入作业的处理时间，bestf记录当前最小完成时间和，bestx记录相应的当前最佳作业调度。

在递归函数Backtrack中，

当i>n时，算法搜索至叶子结点，得到一个新的作业调度方案。此时算法适时更新当前最优值和相应的当前最佳调度。

当i<n时，当前扩展结点位于排列树的第（i-1）层，此时算法选择下一个要安排的作业，以深度优先方式递归的对相应的子树进行搜索，对不满足上界约束的结点，则剪去相应的子树。

算法描述：

注：1、区分作业i和当前第i个正在执行的作业

给x赋初值，即其中一种排列，如x=[1,3,2]；M[x[j]][i]代表当前作业调度x排列中的第j个作业在第i台机器上的处理时间；如M[x[2]][1]就意味着作业3在机器1上的处理时间。

2、bestf的初值

此问题是得到最佳作业调度方案以便使其完成时间和达到最小，所以当前最优值bestf应该赋值为较大的一个值。如9999

3、f1、f2的定义与计算

假定当前作业调度排列为：x=[1,2,3]；f1[i]即第i个作业在机器1上的处理时间，f2[j]即第j个作业在机器2上的处理时间；则：

f1[1]=M[1][1] , f2[1]=f1[1]+M[1][2]

f1[2]=f1[1]+M[2][1] , f2[2]=MAX(f2[1],f1[2])+M[2][2]　//f2[2]不光要等作业2自己在机器1上的处理时间，还要等作业1在机器2上的处理时间，选其大者。

f1[3]=f1[2]+M[3][1] , f2[3]=MAX(f2[2],f1[3])+M[3][2]

  • f1只有当前值有用，可以覆盖赋值，所以定义为int型变量即可，减少空间消耗；
  • f2需要记录每个作业的处理时间，所以定义为int *型，以便计算得完成时间和。

4、f2[0]的初值

f2[i]的计算都是基于上一个作业f2[i-1]进行的，所以要记得给f2平[0]赋值为0。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

class Flowshop
{
    friend Flow(int * *,int,int[]);
private:
    void Backtrack(int i);
    int * * M,　　　　　　//各作业所需的处理时间，根据上面的例子就是4*3的矩阵————M[j][i]代表第j个作业在第i台机器上的处理时间

        * x,　　　　　　　//当前作业调度————其中一种排列顺序
        * bestx,　　　　 //当前最优作业调度

        * f2,　　　　　　 //机器2完成处理时间————记录每个作业在机器2上的完成时间
        f1,　　　　　　　　//机器1完成处理时间————定义int型，减少空间消耗（因为只有当前的f1有用，所以可以覆盖赋值）
        f,　　　　　　　　//完成时间和

        bestf,　　　　　　//当前最优值

        n;　　　　　　　　//作业树

};
void Flowshop::Backtrack(int t)
{
    if(t>n)
    {
        for(int j=1;j<=n;j++)
            bestx[j] = x[j];
        if(bestf>f)
        	bestf = f;
    }
    else
    {
        //排列树中j从i开始————控制分支数
        for(int j=t;j<=n;j++)　　
        {
            //“假设”：在第1台机器上的完成处理时间————着重关注M矩阵的行标（代表当前执行的作业，是动态变化的）
            f1+=M[x[j]][t];　　
            //“假设”：在机器2上的完成处理时间，f2[0]初值赋为0
            ////f2[t]不光要等作业t自己在机器1上的处理时间，还要等作业t-1在机器2上的处理时间，选其大者。
            f2[t]=((f2[t-1]>f1)?f2[t-1]:f1)+M[x[j]][2];　　
            //“假设”：总的完成时间和
            f+=f2[t];　　
            //进入下一个任务
            if(f<bestf)　　
            {
                Swap(x[t],x[j]);
                //“递归”
                Backtrack(t+1);
                Swap(x[t],x[j]);
            }
            //“回溯消除”：改变机器完成时间计数————递归返回时间
            f1 -= M[x[j]][1];　　
            f -= f2[t];
        }
    }
}
int Flow(int * * M,int n,int bestx[])
{
    int ub = INT_AMX;
    Flowshop X;
    X.x = new int [n+1];
    X.f2 = new int [n+1];
    X.M = M;
    X.n = n;
    X.bestf = ub;
    X.bestx = bestx;
    X.f1 = 0;
    X.f = 0;
    for(int i=0;i<=n;i++)
    {
        X.f2[i] = 0;
        X.x[i] i;
    }
    X.Backtrack(1);
    delete [] X x;
    delete [] X f2;
    return X.bestf;
}

​

工作分配问题

与批处理作业调度类似

题目

设有n件工作分配给n个人。将工作i分配给第j个人所需的费用为c(i,j) 。 设计一个算法，对于给定的工作费用，为每一个人都分配1件不同的工作，并使总费用达到最小。

输入格式:

输入数据的第一行有1 个正整数n (1≤n≤20)。接下来的n行，每行n个数，表示给每个人的工作费用。

输出格式:

将计算出的最小总费用输出到屏幕。

输入

3
10 2 3
2 3 4
3 4 5

输出

最小费用

9

最优序列为【第1个任务给第二个人，第2个任务给第一个人；列表示任务，对应值表示人】

2 1 3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<iostream>
#include<climits>
using namespace std;
#define N 21
int cost[N][N];
//x是当前假定的工作安排序列
int x[N];
//cv是当前费用currentValue
int n,cv=0;
//bestv是最小费用(bestValue)
int bestv=INT_MAX;
//bestx是最好的工作安排序列
int bestx[100];
//传入第t任务
void backtrack(int t)
{
        if(t>n)
        {
            //只当当前费用cv确实小于bestv才变
			if(cv<bestv){
				bestv=cv;
                //更新最好的工作安排序列
				for(int i=1;i<=n;i++)
					bestx[i]=x[i];
			}
            return;
        }
        else
        {
            //对每个人遍历，指定任务为t
            for(int i=t;i<=n;i++)
            {
                //【先判断再假设】类型
                //当前【任务t】分配到【序列x】的【第i个人】，并花费更小时【和装载问题当前cw+w[i]<cap时很像】
                if(cv + cost[t][x[i]]< bestv){
                    //“假设”
                    cv+=cost[t][x[i]];
                    //交换【序列x】的次序，以产生不同序列
                    swap(x[t],x[i]);
                    backtrack(t+1);
                    //“回溯时还原”
                    swap(x[t],x[i]);
                    //“回溯时还原”
                    cv-= cost[t][x[i]];
                }
            }
        }
}
 
int main()
{
        int i,j;
        while(cin>>n)
        {
            //第i项目给第j个人的花费
			for(i=1;i<=n;i++)
					for(j=1;j<=n;j++)
							cin>>cost[i][j];
            //默认按第1个人被分配第1个工作
			for(i=1;i<=n;i++)
					x[i]=i;
			backtrack(1);
			cout<<bestv<<endl;
			for(int i=1;i<=n;i++)
				cout<<bestx[i]<<" ";
			cout<<endl;
        }
        return 0;
}

​

三角符号问题

问题

给定第一行的符号（只有+，-）数目n，每行比上一行数目少一（形成一个倒三角），2个相同符号下面为“+”号，2个不同符号下面为“-”号，要求有多少种情况使得两种符号数目相同。
第一行为7的符号三角形之一：

在这里插入图片描述

分析

我们发现
由于只有两种符号，所以我们可简化为0、1形式，+号用1表示，-号用0表示
①总符号数为n(n+1)/2,如果总数为奇数，那么一定不可能符号数相等
②当某一符号数大于总数的一半时，那么此情况不存在解

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<bits/stdc++.h>
using namespace std;
#define N 100
int n;
int cnt=0,sum=0;
int half;
int p[N][N]={0};

/*
    输入：t，表示t个符号形成的三角规模
*/

void backtrack(int t){
	int j,i;
	if(cnt>half||t*(t+1)/2-cnt>half) //某种符号数量大于一半时退出，减枝
		return;
	if(t>=n){//t大于n时，说明已经找到了一个(t-1)规模的+与-相同的子三角型
		sum++;
		return;
	} 
    //选择-/+两个符号【和下面的着色问题中m个颜色类似】
	for(i=0;i<2;i++){
        //“假设”：只需改变第一行，下面行的符号是确定的。t会不断增加，p[0][1],p[0][2],p[0][3]…………
		p[0][t]=i; 
        //“假设”：cnt可以看做：记录所有行的+号个数，+号用1表示，-号用0表示
		cnt+=p[0][t]; 
        //“假设”：从第二行开始，向下形成三角型
		for(j=1;j<=t;j++){
            //j行的第(t-j)符号是  第(j-1)层的(t-j)与第(j-1)层的(t-j+1)符号 【异或】结果
            //t-j说明是从这行的末尾【最后一列】开始向前
			p[j][t-j]=p[j-1][t-j]^p[j-1][t-j+1];
            //cnt记录j行的第(t-j)符号
			cnt+=p[j][t-j];
		}
        //“递归”“搜索t+1树
		backtrack(t+1);
        //“回溯时清除”：上次的赋值
		for(j=1;j<=t;j++){
			cnt-=p[j][t-j];
		}
		cnt-=p[0][t];
	}
}
int main()
{
    //输入第一行个数
	cin>>n;
	int total=n*(n+1)/2;//总的符号数 
	if(total%2==1) 
        cout<<0<<endl;
    half=total/2;//除以2才是真正的一半； 
    backtrack(0); 
    cout<<sum<<endl;
	return 0;
}

举例

比如：t=3时，让p[0][3]=0;

假如第一行为0 0 1 0

则j从1（第二行开始），并从t-j=2，第三列开始开始

第一行 0 0 1 0 p[0][3]
第二行 1
第二行 1 1
第二行 0 1 1

j再变成2，并从t-j=1，第二列开始……剩下的类似

最终产生

第1行 0 0 p[0][1] 1 p[0][2] 0 p[0][3]
第2行 0 1 1
第3行 1 0
第4行 1

此时，已经完成了t=3的(实际上是4个,t从0开始)规模的三角型，再进入backtrack(t+1);

进入backtrack(t+1)后，如果n=4，现在t=4，已经完成了目标，sum+1并return

返回上个递归，并进行清除之前的赋值，并重新让p[0][3]=1;

第1行 0 0 p[0][1] 1 p[0][2] 1 p[0][3]
第2行 0 1 0
第3行 1 1
第4行 0

此时，已经完成了t=3的规模的三角型，再进入backtrack(t+1);

同上面一样，如果n=4，t=4，也完成了目标，sum+1并return

​

返回上个递归，并进行清除之前的赋值，发现p[0][3]已经选择过0和1，for(i=0;i<2;i++)已经执行完成，则整个backtrack(3)执行完成。

则返回到backtrack(2)调用backtrack(3)的后面，清除之前的赋值，发现p[0][2]也已经选择过0和1，for(i=0;i<2;i++)已经执行完成，则整个backtrack(2)执行完成。

则返回到backtrack(1)调用backtrack(2)的后面，清除之前的赋值，并让p[0][1]=1 ; 再调用backtrack(2)并继续运算

​

​

n皇后问题

题目

N皇后的排列，每行一个不冲突；N<=13。

输入要求

一个数字N (6 <= N <= 13) 表示棋盘是N x N大小的。

输出要求

前三行为前三个解，每个解的两个数字之间用一个空格隔开。第四行只有一个数字，表示解的总数。

解的输出顺序为从上到下从左到右，小的优先输出

输入：

6

输出样例：

2 4 6 1 3 5

3 6 2 5 1 4

4 1 5 2 6 3

4

思路

整体思路：从第一列开始逐行遍历，如果i行j列可以放，则queue[i][j]位置设置为1，并开始遍历下一(i+1)行。如果不可以放，则设置queue[i][j]为0，并对(j+1）列开始逐行遍历。直到遍历到第八行时，将结果输出。输出的思路是，如果queue[i][j]为1则说明此位置有皇后，输出对应的j列号。

判断queue[i][j]是否可以放皇后的思路：

如果0~i-1行j列有皇后则不能放；

如果queue[i][j]的左上角有皇后则不可以放；

如果queue[i][j]的右上角有皇后则不可以放；

其它情况则可以放。

isSafe

We must check upper left diagonal , upper right diagonal and the same col .Because we place queens row by row, we can’t check lower left diagonal because all rows below “the current placing row” are empty and don’t have any queens yet.

On the other hand, checking the upper left and upper right diagonals is important because there may be queens in those diagonals that can attack the new position. That’s why you should check the same column, upper left diagonal and upper right diagonal when determining if it’s safe to place a new queen on the chessboard.

solveNQUtil

(solve N Queens Utility)
If not all queens have been placed yet, then the function enters a loop that iterates over all columns in the current(the given row) row.
For each column, it checks if it’s safe to place a new queen there using isSafe function. If it’s safe, then it places a queen in that position (board[row][i] = 1)and calls itself recursively for the next row (solveNQUtil(board,row+1)).After returning from the recursive call,it removes the queen from that position (board[row][i] = 0) and continues with the next column.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <iostream>
using namespace std;
#define N 4

/*
TIPS:
We must check upper left diagonal , upper right diagonal and the same col
Because we place queens row by row, we can't check lower left diagonal because 
all rows below "the current placing row" are empty and don't have any queens yet.

On the other hand, checking the upper left and upper right diagonals is important 
because there may be queens in those diagonals that can attack the new position. 
That’s why you should check the same column, upper left diagonal and upper right diagonal 
when determining if it’s safe to place a new queen on the chessboard.
*/
int isSafe(int board[N][N],int row,int col){
    //Chech if there is a queen in the same col
    for(int i=0;i<row;i++){
        if(board[i][col]==1){
            return 0;
        }
    }
    //Chech if there is a queen in the upper left diagonal
    for(int i=row,j=col;i>=0 && j>=0;i--,j--){
        if(board[i][j]==1){
            return 0;
        }
    }
    //Check if there is a queen in the upper right diagonal
    for(int i=row,j=col;i>=0&& j<N;i--,j++){
        if(board[i][j]==1){
            return 0;
        }
    }
    return 1;
}
void printBoard(int board[N][N]){
    for(int i =0;i<N;i++){
        for(int j=0;j<N;j++)
            cout<<board[i][j]<<" ";
        cout<<endl;
    }
    cout<<endl;
}


/*
solveNQUtil(solve N Queens Utility)
If not all queens have been placed yet, 
then the function enters a loop that iterates over all columns in the current row. 
For each column, it checks if it’s safe to place a new queen there using isSafe function. 
If it’s safe, then it places a queen in that position (board[row][i] = 1)
and calls itself recursively for the next row (solveNQUtil(board,row+1)).
After returning from the recursive call,
it removes the queen from that position (board[row][i] = 0) 
and continues with the next column.
*/
void solveNQUtil(int board[N][N], int row){
    //If all queens have been placed successfully, then prin the solution
    if(row==N){
        printBoard(board);
        return ;
    }
    //This loop try to place a queen in each colum of the given row
    for(int i=0;i<N;i++){
        if(isSafe(board,row,i)){
            board[row][i]=1;
            solveNQUtil(board,row+1);
            board[row][i]=0;
        }
    }
    return ;
}

//place queens row by row
void solveNQ(int board[N][N]){
    solveNQUtil(board,0);
}

int main(){
    int board[N][N]={{0}};
    solveNQ(board);
}

​

​

最大团问题

和装载问题相似

了解最大团问题（Maximum Clique Problem, MCP）之前需要明白几个概念。复习一下图论知识…

完全图：如果无向图中的任何一对顶点之间都有一条边，这种无向图称为完全图。

完全子图：给定无向图G=(V,E)。如果U⊆V，且对任意u，v⊆U 有(u，v) ⊆ E，则称U 是G 的完全子图。

团（最大完全子图）: U是G的团当且仅当U不包含在G 的更大的完全子图中

**最大团：**G 的最大团是指G中所含顶点数最多的团。

**空子图：**给定无向图G=(V,E)。如果U⊆V，且对任意u，v⊆U 有(u，v) ∉ E，则称U 是G 的空子图。G的空子图U是G的独立集当且仅当U不包含在G的更大空子图中。

**独立集：**对于给定无向图G=(V,E)。如果顶点集合V⊆V，若V中任何两个顶点均不相邻，则称V*为G的点独立集，或简称独立集。

**最大独立集：**G中所含顶点数最多的独立集。

例如：

a

b

c

d

图a是一个无向图，图b、c、d都是图a的团，且都是最大团。

补图：

img

图G的补图，通俗的来讲就是完全图Kn去除G的边集后得到的图Kn-G。在图论里面，一个图G的补图（complement）或者反面（inverse）是一个图有着跟G相同的点，而且这些点之间有边相连当且仅当在G里面他们没有边相连。

输入

5 7
1 2
1 4
1 5
2 5
2 3
3 5
4 5

输出

3
1 2 5

思路

首先假设最大团为一个空团，往其中加入一个顶点，然后依次考虑未加入到团的每个顶点，查看该顶点加入团之后是否仍然构成一个团？

  • 如果可以再构成团，考虑将该顶点加入团或者舍弃两种情况。
  • 如果不能再构成团，直接舍弃，然后递归判断下一顶点。

对于无连接或者直接舍弃两种情况，在递归前，可采用剪枝策略来避免无效搜索。

判断某个顶点加入团之后是否仍是一个团

  • 该顶点和团中所有的顶点是否都有连接

剪枝

程序中采用了一个比较简单的剪枝策略，即如果剩余未考虑的顶点数加上团中顶点数不大于当前最优解的顶点数，可停止继续深度搜索，

  • 因为最优解需要尽可能的大，未考虑的顶点+目前团中顶点 的总数 不可能再超过 当前最优解的顶点数，无需再进入子树

否则继续深度递归。

​

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include<bits/stdc++.h>
using namespace std;

const int maxnum=101;
int a[maxnum][maxnum];//图的邻接矩阵
int x[maxnum]; //当前解
int cn;//当前团的顶点数
int bestn;//当前的最优解
int n;//图G的顶点数
int e;//图G的边数
int isCapatable(int i){
    //当前要加入的结点为i
    for(int j=1; j<i; j++)
    {
        //x[j]==1表示，节点j在团内,a[j][i]==0表示节点i与某个点i无连接
        if(x[j]&&a[j][i]==0)
        {
            return 0;
        }
    }
    //表示i与当前团的所有点都有连接，i可以入团
    return 1;
}
//传入的i是节点个数
void backtrack(int i)
{
    int j;
    //到叶子节点
    if(i>n)
    {
        bestn=cn;
        cout<<bestn<<endl;
        for(j=1; j<=n; j++)
        {
            if(x[j])
            {
                cout<<j<<" ";
            }
        }
        return ;
    }
    //左子树
    //先判断节点i是否可以入团
    if(isCapatable(i))
    {
        //“假设”：将节点i加入到团内
        x[i]=1;
        cn++;
        //“递归”：
        backtrack(i+1);
        //“回溯时清除”：回收假设
        cn--;    
        x[i]=0;//可以不写，因为进入右子树时还会写
    }
    
    //右子树
    //右子树，对应“不入团”，本来无需判断，可以直接调用BackTrack(i + 1);
    //但这里做剪枝操作，当bestn>=cn+n-i时，丢弃右子树。因为右子树的产生最大团的数量，不可能超过bestn了
    //cn是当前团数量，n-i是剩下的节点；只有当cn+n-i大于bestn时，说明还有足够多的候选顶点，才有希望找到更大的团
    //这里如果设置r=n-i，那么和下面的装载问题一样
    if(cn+n-i>bestn)
    {
        //X[i]不入团，不用
        //x[i]=0;
        backtrack(i+1);
    }
}

int main()
{
    int i,u,v;
    memset(a,0,sizeof(a));
    memset(x,0,sizeof(x));
    //n个点，e个边
    cin>>n>>e;
    for(i=0; i<e; i++)
    {
        cin>>u>>v;
        a[u][v]=a[v][u]=1;
    }
    cn=bestn=0;
    backtrack(1);
    return 0;
}

​

​

图的m着色问题

着色问题与最大团、n皇后问题的判断-假设部分相似

题目

给定图G=(V, E)，需要为图G的各顶点着色，是否有一种着色法使G中相邻的两个顶点有不同的颜色?

输入要求

第一行是顶点的个数n（2≤n≤8），颜色数m（1≤m≤n）。

接下来是顶点之间的连接关系：a b；表示a和b相邻。顶点从1开始计。

当a，b同时为0时表示输入结束。

输出要求

输出着色方案总数和最少颜色数。如果无可行方案，颜色数为0。

输入：

5 8 4
1 2
1 3
1 4
2 3
2 4
2 5
3 4
4 5

输出样例：

48 4

思路

colorOf[n] 存储 n个顶点的着色方案，可以选择的颜色为1 到 m

x=1 对当前第x个顶点开始着色：

若x>n 则已求得一个解，输出着色方案即可

否则，依次对顶点x着色1到m，假设给点x着色为i

  • 若点x与其它相邻点无颜色冲突，则继续为下一顶点着色；
  • 若点x与其它相邻点有相同颜色，则返回假，尝试下一颜色。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include<bits/stdc++.h>
using namespace std;
int n=0,k=0,m=0,sum=0;
int ConnectOf[100][100],ColorOf[100];

bool isUsable(int x) { 
    //点x与其它点i相连，并且使用相同颜色，则返回假
    for(int i=1; i<=n; i++) {
        if((ConnectOf[x][i]==1)&&(ColorOf[i]==ColorOf[x]))
            return false;//返回假
    }
    return true;//否则真
}
bool isUsable(int x,int j) { 
    //点x与其它点i相连，并且使用相同颜色，则返回假
    for(int i=1; i<=n; i++) {
        if((ConnectOf[x][i]==1)&&(ColorOf[i]==j))
            return false;//返回假
    }
    return true;//否则真
}
void search(int x) { //他的情况不是能涂哪个节点，因为我们就是从第一个开始涂色的，而是有m个颜色可涂；
    if(x>n){
        sum++;
        return ;
    }
    else
        //每一个点有1~m种颜色可以涂【像前面三角符号问题，每个符号有+/-两种可选】
        for(int i=1; i<=m; i++) { 
            //两种写法，对应的isUsable不同
            //先判断后假设，先判断第x个能否涂第i种颜色
            if(isUsable(x,i)) { 
                //再假设将x这个点涂成i色
                ColorOf[x]=i;
                //如果可以涂色，则继续搜索
                search(x+1);
                //回收假设，并尝试下一种颜色
                ColorOf[x]=0;
            }
            /*
            //先假设再判断，先假设第x个涂第i种颜色
            ColorOf[x]=i;
            //再判断第x个能否涂第i种颜色，所以isUsable无需传入要涂的颜色i
            if(isUsable(x)) { 
                //如果可以涂色，则继续搜索
                search(x+1);
            }
            //回收假设，并尝试下一种颜色
            ColorOf[x]=0;
            */
        }
    
}
int main() {
    memset(ConnectOf,100,0);
    memset(ColorOf,100,0);
    int x,y;
    cin>>n>>k>>m;
    for(int i=1; i<=k; i++) {
        cin>>x>>y;
        //点x与点y相连
        ConnectOf[x][y]=ConnectOf[y][x]=1;
    }
    search(1);
    cout<<sum<<endl;
    return 0;
}


​

​

装载问题

问题描述

有n个集装箱要装上2艘载重量分别为c1和c2的轮船，其中集装箱i的重量为wi，且∑wi <= c1 + c2。

问是否有一个合理的装载方案,可将这n个集装箱装上这2艘轮船。如果有，找出一种装载方案。

问题分析

如果一个给定装载问题有解，则采用下面的策略可得到最优装载方案。
(1)首先将第一艘轮船尽可能装满；
(2)将剩余的集装箱装上第二艘轮船。

将第一艘轮船尽可能装满等价于选取全体集装箱的一个子集，使该子集中集装箱重量之和最接近c1。由此可知，装载问题等价于以下特殊的0-1背包问题:

max∑ wi * xi && ∑ wi * xi <= c1, xi ∈ {0, 1}, 1 <= i <= n;

算法思路

用子集树表示解空间,则解为n元向量{x1, … ,xn }, xi∈{0, 1} 。

约束条件

当前搜索的层i <= n时，

当前扩展结点Z为子集树的内部结点，仅当满足cw+w[i] <= c时进入左子树，x[i]=1;

当cw+w[i] > c ，即装不下，在以结点Z为根的子树中所有结点都不满足约束条件，因而该子树中解都是不可行解，因而将在该子树删去。

剪枝

由于是最优化问题, 可利用最优解性质进一步剪去不含最优解的子树:

设Z是解空间树第i层上的当前扩展结点。

设 bestw: 当前最优载重量,
cw : 当前扩展结点Z的载重量 ;
r : 剩余集装箱的重量;

在以Z为根的子树中任意叶结点所相应的载重量不超过cw + r。因此，当cw + r (限界函数) ≤ bestw时，可将Z的右子树剪去

  • 因为目标bestw要尽可能的大，如果发现cw+r，也就是这个子树的最大重量，已经不可能再超过bestw，就无需进入子树

即：只有当 cw + r > bestw 时，才搜索右子树，x[i]=0;

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <bits/stdc++.h>
using namespace std;
int n; //集装箱数
int cw; // 当前载重量, current weight
int bestw; //最优载重重量
int r;  //剩余集装箱重量
int c1; //第一艘轮船的载重量
int c2; //第二艘轮船的载重量
int x[100]; //当前解
int bestx[100]; //当前最优解
int w[100]; //集装箱重量数组
void OutPut()
{
    int restweight = 0;
    for(int i = 1; i <= n; ++i)
        if(bestx[i] == 0)
           restweight += w[i];
    if(restweight > c2)
        printf("不能装入\n");
    else
    {
        printf("船1装入的货物为:");
        for(int i = 1; i <= n; ++i)
            if(bestx[i] == 1)
               printf(" %d", i);
        printf("\n船2装入的货物为:");
        for(int i = 1; i <= n; ++i)
            if(bestx[i] != 1)
               printf(" %d", i);
 
    }
}
//传输的i，是集装箱个数
void BackTrack(int i)
{
    if(i > n)
    {
        if(cw > bestw)
        {
            for(int i = 1; i <= n; ++i)
                bestx[i] = x[i];
            bestw = cw;
        }
        return;
    }
    //“假设”：剩余重量减少
    r -= w[i];
    //【和最大团问题很像，最大团“装”的条件是这个点与团内点都有连接】
    //【最大团问题中，w[i]为1】
    //左子树，对应“装”，但要先判断能否装得下【先判断，再假设的类型】
    if(cw + w[i] <= c1)
    {
        //“假设”：装
        x[i] = 1;
        //“假设”：装入的重量增加
        cw += w[i];
        //讨论下个箱子
        BackTrack(i + 1);
        //“回溯消除”：
        cw -= w[i];
        //“回溯消除”：
        x[i] = 0;
    }
    //右子树，对应“不装”本来无需判断，可以直接调用BackTrack(i + 1);
    //但这里加入了“剪枝”操作，当bestw>=cw+r时，将右子树剪去，右子树无法超过bestw
    //只有cw+r>bestw时才装入，r是剩下的总量【和最大团问题几乎一样】
    if(cw + r > bestw) 
    {
        //x[i] = 0;
        BackTrack(i + 1);
    }//否则不进入子树
    //“回溯消除”
    r += w[i];
 
}
void Initialize()
{
    bestw = 0;
    r = 0;
    cw = 0;
    for(int i = 1; i <= n; ++i)
        r += w[i];
}
void InPut()
{
    scanf("%d", &n);
    scanf("%d %d", &c1, &c2);
    for(int i = 1; i <= n; ++i)
        scanf("%d", &w[i]);
}
int main()
{
    InPut();
    Initialize();
    BackTrack(1);
    OutPut();
}

测试样例

输入：

3

50 50

10 40 40

输出

船1装入的货物为: 1 2

船2装入的货物为: 3