当前位置：首页 > article >正文

AI刷题-最小化团建熟悉程度和

article 2025/1/27 16:48:43

问题描述

输入格式

输出格式

解题思路：

状态表示

状态转移

动态规划数组

预处理

实现：

1.初始化：

2.动态规划部分：

（1）对于已分组状态的，跳过：

（2）对于未分组的：首先是nextMember变量作为存储未分组成员的位置，

（3）尝试对未分组的进行分组

（4）最后返回结果

最终代码：

运行结果：

问题描述

最近团队中新来了许多同事，小茗同学所在部门希望通过团建来促进新老成员的沟通交流，增进信任，同时提升团队协作力、执行力和竞争力。

当团建活动规模较大时，参与人数过多，一般会分成若干个小组以便于活动展开。然而，这也导致了不同小组的成员交流过少。为了缓解这个问题，团队提出了分布式团建的方法：将活动分成若干轮，每轮分成多个 3 人小组，每个小组自由支配活动经费单独活动。团队中的成员两两之间的熟悉程度互不相同，为了最大化降低成员之间的陌生程度，分组时需要考虑尽可能将不熟悉的成员匹配在一起，通过团建活动彼此熟络。每个 3 人小组的熟悉程度定义为小组内成员两两之间的熟悉程度之和，分组方案需最小化所有小组的熟悉程度之和。

作为一名算法工程师，小茗同学开始着手解决这个问题，但是遇到了一点小困难，想请你帮忙一起解决。

输入格式

第一行为一个整数 N，表示团队成员人数。接下来 N 行，每行有 N 个整数 r_{i,j}，表示成员 i 与成员 j 的熟悉程度。

输出格式

输出一个整数，表示将团队成员分成多个 3 人小组后，熟悉程度之和的最小值。

输入样例

输入样例 1

100 78 97

78 100 55

97 55 100

输入样例 2

100 56 19 87 38 61

56 100 70 94 88 94

19 70 100 94 43 95

87 94 94 100 85 11

38 88 43 85 100 94

61 94 95 11 94 100

输出样例

输出样例 1

230

输出样例 2

299

备注

对于样例 2，组队方案为 (1, 3, 5) 和 (2, 4, 6)，最小的熟悉程度之和为 (19 + 38 + 43) + (94 + 94 + 11) = 299。

数据范围

数据保证 N 是 3 的倍数， r_{i,j} = r_{j,i}, r_{i,i} = 100。

100% 数据：3 ≤ N ≤ 21, 0 ≤ r_{i,j} ≤ 100 。

解题思路：

本题可以使用动态规划（Dynamic Programming）来解决。我们需要将 N 个成员分成若干个 3 人小组，并最小化所有小组的熟悉程度之和。

状态表示

我们使用一个位掩码（bitmask）来表示当前哪些成员已经被分组。具体来说，mask 是一个二进制数，其中第 i 位为 1 表示第 i 个成员已经被分组，为 0 表示未分组。

状态转移

我们从初始状态（所有成员都未分组）开始，逐步将成员分组。对于每个状态 mask，我们找到一个未分组的成员 nextMember，然后尝试将 nextMember 与另外两个未分组的成员组成一个 3 人小组。更新状态 mask 并计算新的熟悉程度之和。

动态规划数组

我们使用一个数组 dp 来存储每个状态的最小熟悉程度之和。dp[mask] 表示在状态 mask 下，所有成员分组后的最小熟悉程度之和。

预处理

我们预处理每个 3 人小组的熟悉程度之和，并存储在一个哈希表中，以便在动态规划过程中快速查找。

实现：

1.初始化：

提前创建一个dp数组进行计算，一个groupFamiliarityMap集合来预处理每三个人的组合情况

减少后面dp的计算量

vector<long long> dp(1 << N, LLONG_MAX);
    dp[0] = 0;

    // 预处理每个小组的熟悉程度之和
    unordered_map<string, int> groupFamiliarity;
    for (int i = 0; i < N; i++) {
        for (int j = i + 1; j < N; j++) {
            for (int k = j + 1; k < N; k++) {
                int sum = familiarMatrix[i][j] + familiarMatrix[i][k] + familiarMatrix[j][k];
                groupFamiliarity[to_string(i) + "," + to_string(j) + "," + to_string(k)] = sum;
            }
        }
    }

2.动态规划部分：

用一个mask（位掩码）作为循环变量

（1）对于已分组状态的，跳过：

if (dp[mask] == LLONG_MAX) {
            continue;
        }

（2）对于未分组的：首先是nextMember变量作为存储未分组成员的位置，

注意：!(mask & (1 << i))这个判断条件是为了检查第 i 位是否未被设置（即未分组），其中只有第 i 位与 mask（2进制） 的第 i 位都为 1 时，结果的第 i 位才为 1，否则为 0。

// 找到下一个未分组的成员
        int nextMember = -1;
        for (int i = 0; i < N; i++) {
            if (!(mask & (1 << i))) {
                nextMember = i;
                break;
            }
        }

找不到则跳过

        if (nextMember == -1) {
            continue;
        }

（3）尝试对未分组的进行分组

        // 尝试将 nextMember 与另外两个未分组的成员组成一个小组
        for (int j = nextMember + 1; j < N; j++) {
            if (!(mask & (1 << j))) {
                for (int k = j + 1; k < N; k++) {
                    if (!(mask & (1 << k))) {
                        int newMask = mask | (1 << nextMember) | (1 << j) | (1 << k);
                        string key = to_string(nextMember) + "," + to_string(j) + "," + to_string(k);
                        int groupFamiliaritySum = groupFamiliarity[key];
                        dp[newMask] = min(dp[newMask], dp[mask] + groupFamiliaritySum);
                    }
                }
            }
        }

（4）最后返回结果

return (int)dp[(1 << N) - 1];

最终代码：

#include <iostream>
#include <vector>
#include <unordered_map>
#include <climits>
#include <string>

using namespace std;

int solution(int N, vector<vector<int>> familiarMatrix) {
    // 初始化 dp 数组
    vector<long long> dp(1 << N, LLONG_MAX);
    dp[0] = 0;

    // 预处理每个小组的熟悉程度之和
    unordered_map<string, int> groupFamiliarity;
    for (int i = 0; i < N; i++) {
        for (int j = i + 1; j < N; j++) {
            for (int k = j + 1; k < N; k++) {
                int sum = familiarMatrix[i][j] + familiarMatrix[i][k] + familiarMatrix[j][k];
                groupFamiliarity[to_string(i) + "," + to_string(j) + "," + to_string(k)] = sum;
            }
        }
    }

    // 动态规划
    for (int mask = 0; mask < (1 << N); mask++) {
        if (dp[mask] == LLONG_MAX) {
            continue;
        }

        // 找到下一个未分组的成员
        int nextMember = -1;
        for (int i = 0; i < N; i++) {
            if (!(mask & (1 << i))) {
                nextMember = i;
                break;
            }
        }
        if (nextMember == -1) {
            continue;
        }

        // 尝试将 nextMember 与另外两个未分组的成员组成一个小组
        for (int j = nextMember + 1; j < N; j++) {
            if (!(mask & (1 << j))) {
                for (int k = j + 1; k < N; k++) {
                    if (!(mask & (1 << k))) {
                        int newMask = mask | (1 << nextMember) | (1 << j) | (1 << k);
                        string key = to_string(nextMember) + "," + to_string(j) + "," + to_string(k);
                        int groupFamiliaritySum = groupFamiliarity[key];
                        dp[newMask] = min(dp[newMask], dp[mask] + groupFamiliaritySum);
                    }
                }
            }
        }
    }

    return (int)dp[(1 << N) - 1];
}

int main() {
    vector<vector<int>> familiarMatrix1 = {
        {100, 78, 97},
        {78, 100, 55},
        {97, 55, 100}
    };

    vector<vector<int>> familiarMatrix2 = {
        {100, 56, 19, 87, 38, 61},
        {56, 100, 70, 94, 88, 94},
        {19, 70, 100, 94, 43, 95},
        {87, 94, 94, 100, 85, 11},
        {38, 88, 43, 85, 100, 94},
        {61, 94, 95, 11, 94, 100}
    };

    cout << (solution(3, familiarMatrix1) == 230) << endl;  // 输出: 1 (true)
    cout << (solution(6, familiarMatrix2) == 299) << endl;  // 输出: 1 (true)

    return 0;
}