回溯法 求一个子集问题：装载问题、最大团问题

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
#include<iostream>
using namespace std;
int n;//集装箱数
int w[40];//集装箱重量
int c1,c2;//两艘船的载重量
int ans;//当前载重量
int bestans;//当前最优载重量
int r;//剩余集装箱重量

void backtrack(int i) {
    tal++;
    if(i>n) {
        if(ans>bestans) {
            bestans=ans;
        }
        return;
    }
    r-=w[i];
    if(ans+w[i]<=c1) {
        ans+=w[i];
        backtrack(i+1);
        //改回辅助的全局变量
        ans-=w[i];
    }
    //剪枝函数，当前已装的重量和剩下的重量 小于 最优重量，则不必往下递归了 
    if(ans+r>bestans) backtrack(i+1);
    //改回辅助的全局变量
    r+=w[i];
}

int main() {
    cin>>n>>c1>>c2;
    int i=1;
    int sum=0;
    //集装箱总重量
    while(i<=n) {
        cin>>w[i];
        r+=w[i];
        sum+=w[i];
        i++;
    }
    backtrack(1);
    backtrack(1);
    if(bestans>0&&((sum-bestans)<=c2)) {
        cout << "轮船1装载的重量为：" <<bestans << "轮船2装载的重量为："<< sum-bestans << endl;
    } else if(sum<=c2) cout<<bestans<<endl;
    else cout<<"No"<<endl;
}

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
#include<iostream>
#include<algorithm>

using namespace std;
int n;//集装箱数
int w[40];//集装箱重量
int c1,c2;//两艘船的载重量
int ans;//当前载重量
int bestans;//当前最优载重量
int r;//剩余集装箱重量
int A[100];//用于放置当前序列
int bestA[100];//用于放置最优序列
int vis[100];//用于记录哪些节点以被访问

int tal = 0;

void back(int cur) {
    tal++;
    if(cur > n) { //走到了边界
        if(ans > bestans) {
            bestans = ans;
            for(int i = 1; i <= n; i++) {
                bestA[i] = A[i];
            }
        }
    } else {
        for(int i = 1; i <= n; i++) {
            if(!vis[i] && ans + w[i] <= c1 && ans+r > bestans) { //剪枝
                r -= w[i];
                ans += w[i];
                A[cur] = w[i];
                vis[i] = 1;

                back(cur+1);

                vis[i] = 0;
                A[cur] = 0;
                ans -= w[i];
                r += w[i];
            }
            if(ans + w[i] > c1) {
                back(cur+1);
            }
        }
    }

}

int main() {
    cin >> n >> c1 >> c2;
    for(int i = 1; i <= n; i++) {
        cin >> w[i];
        r += w[i];
    }
    int sum = r;
    ans = bestans = 0;
    back(1);
    bool ok = true;
    if(r - bestans > c2) {
        ok = false;
    }
    if(ok) {
        cout << "轮船1可以装载以下重量的物品：";
        for(int i = 1; i <= n; i++) {
            if(bestA[i] != 0) {
                cout << bestA[i] << " ";
            }
        }
        cout << endl << "轮船2装载以下重量的物品：" << r-bestans;
    }else{
        cout << "物品过重，无法装载";
    }
    cout << endl << tal;
}

1
2
3
4
5
6
7
8
9
10
11
bool isTuan(int cur){
    for(int i=1; i<cur; i++){
        /*vis[i]代表第i个顶点，如果i顶点是选中的顶点，然而该顶点和cur顶点无边，说明不是最大团
        例如vis[1]=1, vis[2]=1，cur=3，说明已选择了123，
        然而graph[1][3]=0，无边，说明cur不是团中的一员 */
        if(vis[i] && !graph[i][cur]){
            return false;
        }
    }
    return true;
}

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
#include<iostream>
using namespace std;

int v,e,graph[100][100];//v顶点数 e边数 graph图的邻接矩阵
int cn, bestn;//cn 当前团的顶点数 bestn最大团的顶点数 
int corder[100], bestorder[100];//corder 当前团的顶点集 bestorder 最大团的顶点集 
int vis[100];// 记录已选的顶点 

//由于子集的排列时从小到大的，例如{1,2,3}，而不会出现{3,2,1}，因此不用遍历全部顶点
//遍历cur前的顶点即可，因为cur已经是子集排列的最后一位 
bool isTuan(int cur){
    for(int i=1; i<cur; i++){
        /*vis[i]代表第i个顶点，如果i顶点是选中的顶点，然而该顶点和cur顶点无边，说明不是最大团
        例如vis[1]=1, vis[2]=1，cur=3，说明已选择了123，
        然而graph[1][3]=0，无边，说明cur不是团中的一员 */
        if(vis[i] && !graph[i][cur]){
            return false;
        }
    }
    return true;
}

void backtrace(int cur){
    if(cur > v){
        if(cn > bestn){
            bestn = cn;
            for(int i=1; i<=v; i++){
                if(corder[i] != 0)
                cout << corder[i] << " ";
            }
            cout << endl;
        } 
    }
    if(isTuan(cur)){
        cn++;
        vis[cur] = 1;
        corder[cur] = cur;
        backtrace(cur+1);
        cn--;
        vis[cur] = 0;
        corder[cur] = 0;
    }

    //剪枝函数，如果当前团的顶点数 + 剩余的顶点数 小于 当前以得的最大团顶点数，则剪去 
    if(cn + v-cur > bestn){
        backtrace(cur+1);
    }
} 

int main(){
    cin >> v >>e;
    int i,j;
    for(i=1; i<=v; i++){
        for(j=1; j<=v; j++){
            graph[i][j] = 0;
        }
    }
    //输入边 
    for(int k=1; k<=e; k++){
        cin >> i >> j;
        graph[i][j] = 1; 
    } 

    backtrace(1);
    cout << bestn << endl; 
} 

1
2
3
4
5
6
7
8
9
10
11
12
void backtrace(int cur){
    if(cur > n) {
       记录best方案
    }
    if(满足约束条件）{
       backtrace(cur+1);
    }
    if(满足剪枝条件（当前已选 + 剩余的 > 当前已记录的最好的））{
       backtrace(cur+1);
    }
}