Boil's Blog HomeArchivesTagsCategories
回溯第一讲
Word count: 2.3k|Reading time: 10 min

运动员最佳配对问题(homework)

题目内容

羽毛球队有男女运动员各n人。给定2个n×n 矩阵P和Q。P[i] [j]是男运动员i和女运动员 j配对组成混合双打的男运动员竞赛优势；Q[i] [j]是女运动员i和男运动员j配合的女运动员竞赛优势；由于技术配合和心理状态等各种因素影响,P[ i ] [ j ]不一定等于Q[j] [i]。男运动员i和女运动员j配对组成混合双打的男女双方竞赛优势为P[i] [j]* Q[j] [i]。设计一个算法，计算男女运动员最佳配对法,使各组男女双方竞赛优势的总和达到最大。 算法设计:设计一个算法，计算男女运动员最佳配对法,使各组男女双方竞赛优势的总和达到最大。

实现思路

实质上就是暴力深搜。我们这里对男运动员和女运动员分别标号（因为男运动员不用涉及到交换，实质上男运动员的标号并不体现在代码里）。标号后我们的解决方法就是固定男运动员，将女运动员进行全排列枚举。枚举的过程我们用到了排序树，实质上这是一种固定全排列前n项对后面项再进行全排列的操作

实现细节

注意这里男女之间是相乘不是相加。并且在最后临界条件判断的时候注意不要忘了把最后一个加上

实现代码

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
//
//  11th homework of Algorithm Designing and Analyzing in spring semester, 2020
//
//  Introduction:
//
//
//  Author:
//      Yihang Bao
//      2018011890
//  Created by Yihang Bao on 2020/5/24.
//
//

#include <bits/stdc++.h>
#define INF 0x3f3f3f3
#define maxn 100100
typedef long long ll;
using namespace std;

int p[50][50],q[50][50];
int seq[50];    //固定男运动员不动，我们对女运动员的标号进行排列树上的全排列
int n,ans,sum_temp;

void dfs(int pos)
{
    if (pos == n)
    {
        sum_temp += p[pos][seq[pos]] * q[seq[pos]][pos];
        ans = max(ans,sum_temp);
        sum_temp -= p[pos][seq[pos]] * q[seq[pos]][pos];
        return;
    }
    for (int i=pos;i<=n;i++)
    {
        swap(seq[pos], seq[i]);
        sum_temp += p[pos][seq[pos]] * q[seq[pos]][pos];
        dfs(pos+1);
        sum_temp -= p[pos][seq[pos]] * q[seq[pos]][pos];
        swap(seq[pos], seq[i]);
    }
    return;
}

/*
 样例：
 3
 10 2 3
 2 3 4
 3 4 5
 2 2 2
 2 5 3
 4 5 1
 */

int main()
{
    cin >> n;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            cin >> p[i][j];
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            cin >> q[i][j];
    ans = 0; sum_temp=0;
    for (int i=1;i<=n;i++)
        seq[i] = i;
    dfs(1);
    cout << ans << endl;
    return 0;
}

拉丁矩阵问题(homework)

题目内容

有n种不同形状的宝石，每种宝石有足够多颗。欲将这些宝石排列成m行n列的矩阵，m<=n，使矩阵中每行和每列的宝石都没有相同的形状。给出方案数

实现思路

枚举每个位置的情况，每次填入的时候都判断是否可以填入，如果可以就填入，不能就不填

实现细节

二维dfs，注意下一跳位置的分类判断

实现代码

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
//
//  13th homework of Algorithm Designing and Analyzing in spring semester, 2020
//
//  Introduction:
//
//
//  Author:
//      Yihang Bao
//      2018011890
//  Created by Yihang Bao on 2020/5/13.
//
//

#include <bits/stdc++.h>
#define INF 0x3f3f3f3
#define maxn 100100
typedef long long ll;
using namespace std;

int m,n;
int ans;
int mp[30][30];

bool check(int x,int y)
{
    for (int i=1;i<=x-1;i++)
        if (mp[i][y] == mp[x][y])
            return false;
    for (int i=1;i<=y-1;i++)
        if (mp[x][i] == mp[x][y])
            return false;
    return true;
}

void dfs(int x,int y)
{
    for (int i=1;i<=n;i++)
    {
        mp[x][y] = i;
        if (check(x, y))
        {
            if (y<n)
                dfs(x, y+1);
            else if (x==m && y==n)
                ans++;
            else
                dfs(x+1,1);
        }
        else
            continue;
    }
    return;
}

int main()
{
    cin >> m >> n;
    ans=0;
    dfs(1, 1);
    cout << ans << endl;
}

排列宝石问题(homework)

题目内容

现有n种不同形状的宝石，每种n 颗，共nn颗。同一种形状的n颗宝石分别具有n种不同的颜色c1,c2,…,cn中的一种 颜色。欲将这nn颗宝石排列成n行n列的一个方阵，使方阵中每一行和每一列的宝石都有n种不同形状和n种不同颜色。试设计一个算法，计算出对于给定的n，有多少种不同的宝石排列方案。

实现思路

我们在上面那个题的基础上，定义了一个初始宝石矩阵，表示的是初始每个宝石的形状和颜色编号以及是否被取。那么之后我们对于每个要遍历的位置，就在这个宝石矩阵当中枚举取值。这里进行了一定的优化，优化之处在于要先判断形状是否满足，如果形状不满足就不再遍历颜色，降低了时间复杂度

实现细节

同上

实现代码

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
98
99
100
101
102
103
104
105
106
107
108
109
//
//  13th homework of Algorithm Designing and Analyzing in spring semester, 2020
//
//  Introduction:
//
//
//  Author:
//      Yihang Bao
//      2018011890
//  Created by Yihang Bao on 2020/5/13.
//
//

#include <bits/stdc++.h>
#define INF 0x3f3f3f3
#define maxn 100100
typedef long long ll;
using namespace std;

/*
    设计思路：
        这里在常规回溯的基础上进行了一定的剪枝。也就是在试探的时候先判断形状能不能满足，如果
        形状不能满足的话就直接continue，无需再遍历颜色，减小时间复杂度
*/
struct stone
{
    int shape;
    int color;
    bool exist;
};

struct mat
{
    int x;
    int y;
};
mat mp[30][30];
stone a[30][30];
int n,ans;

bool check_shape(int x, int y)
{
    for (int i=1;i<=x-1;i++)
        if (a[mp[i][y].x][mp[i][y].y].shape == a[mp[x][y].x][1].shape)
            return false;
    for (int i=1;i<=y-1;i++)
        if (a[mp[x][i].x][mp[x][i].y].shape == a[mp[x][y].x][1].shape)
            return false;
    return true;
}

bool check_color(int x, int y)
{
    for (int i=1;i<=x-1;i++)
        if (a[mp[i][y].x][mp[i][y].y].color == a[mp[x][y].x][mp[x][y].y].color)
            return false;
    for (int i=1;i<=y-1;i++)
        if (a[mp[x][i].x][mp[x][i].y].color == a[mp[x][y].x][mp[x][y].y].color)
            return false;
    return true;
}

void dfs(int x,int y)
{
    for (int i=1;i<=n;i++)
    {
        mp[x][y].x = i;
        if (!check_shape(x, y))
            continue;
        for (int j=1;j<=n;j++)
        {
            mp[x][y].y = j;
            if (!a[i][j].exist)
                continue;
            if (!check_color(x, y))
                continue;
            cout << x << y << " " <<i <<j <<endl;
            if (y<n)
            {
                a[i][j].exist = false;
                dfs(x, y+1);
                a[i][j].exist = true;
            }
            else if (x==n && y==n)
                ans++;
            else
            {
                a[i][j].exist = false;
                dfs(x+1,1);
                a[i][j].exist = true;
            }
        }
    }
}

int main()
{
    cin >> n;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
        {
            a[i][j].shape = i;
            a[i][j].color = j;
            a[i][j].exist = true;
        }
    ans = 0;
    dfs(1, 1);
    cout << ans << endl;
}

旅行售货员问题(homework)

题目内容

旅行售货员问题是个很经典的问题。题目的意思就是一个售货员要经过所有的城市并回到原来的城市，问最短路径长度是多少，并输出方案

实现思路

在这里我们使用回溯法来解决这个问题。很显然这个问题的解是一棵排列树，那么我们利用dfs向下不断回溯遍历这颗排列树就可以。每次记得判断路径是否存在以及当前的路径长度是否大于当前已经得到的最优值。对于路径记录我们每次找到最优值后就进行记录

实现细节

注意这里是经典的排列树问题，那么我们只需一个一维数组来记录路径即可，每次的操作只是交换某两个的顺序

实现代码

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
//
//  14th homework of Algorithm Designing and Analyzing in spring semester, 2020
//
//  Introduction:
//
//
//  Author:
//      Yihang Bao
//      2018011890
//  Created by Yihang Bao on 2020/5/27.
//
//

#include <bits/stdc++.h>
#define INF 0x3f3f3f3
#define maxn 100100
typedef long long ll;
using namespace std;

int m,n;
int x[110];
int ansx[110];
int mp[110][110];
int ans,now;

void dfs(int level)
{
    if (level == m)
    {
        if (mp[x[level-1]][x[level]] == 0 || mp[x[level]][1] == 0)
            return;
        if (now+mp[x[level-1]][x[level]]+mp[x[level]][1] < ans)
        {
            ans = now+mp[x[level-1]][x[level]]+mp[x[level]][1];
            for(int i=1;i<=m;i++)
                ansx[i] = x[i];
        }
        return;
    }
    for (int i=level;i<=m;i++)
        if (mp[x[level-1]][x[i]] != 0 && now+mp[x[level-1]][x[i]]<ans)
        {
            now += mp[x[level-1]][x[i]];
            swap(x[level], x[i]);
            dfs(level+1);
            swap(x[level], x[i]);
            now -= mp[x[level-1]][x[i]];
        }
    return;
}

int main()
{
    memset(mp, 0, sizeof(mp));
    ans = INF; now = 0;
    cin >> m >> n;
    int t1,t2,t3;
    for (int i=1;i<=n;i++)
    {
        cin >> t1 >> t2 >> t3;
        mp[t1][t2] = t3;
        mp[t2][t1] = t3;
    }
    for (int i=1;i<=m;i++)
        x[i] = i;
    dfs(2);
    if (ans==INF)
        cout << "No answer" << endl;
    else
    {
        cout << "min cost: " << ans << endl;
        cout << "route: ";
        for(int i=1;i<=m;i++)
            cout << ansx[i] << " ";
        cout << 1 << endl;
    }
    return 0;
}
Author: YihangBao
Link: https://roarboil.github.io/2020/05/24/cha5-1/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.