黔西县住房和城乡建设局网站,新手建网站教程,dz门户网站模板,推一手新闻发稿平台目录 问题描述
输入格式
输出格式
解题思路#xff1a;
状态表示
状态转移
动态规划数组
预处理
实现#xff1a;
1.初始化#xff1a; 2.动态规划部分#xff1a;
#xff08;1#xff09;对于已分组状态的#xff0c;跳过#xff1a; #xff08;2…目录 问题描述
输入格式
输出格式
解题思路
状态表示
状态转移
动态规划数组
预处理
实现
1.初始化 2.动态规划部分
1对于已分组状态的跳过 2对于未分组的首先是nextMember变量作为存储未分组成员的位置
3尝试对未分组的进行分组 4最后返回结果
最终代码 运行结果 问题描述
最近团队中新来了许多同事小茗同学所在部门希望通过团建来促进新老成员的沟通交流增进信任同时提升团队协作力、执行力和竞争力。
当团建活动规模较大时参与人数过多一般会分成若干个小组以便于活动展开。然而这也导致了不同小组的成员交流过少。为了缓解这个问题团队提出了分布式团建的方法将活动分成若干轮每轮分成多个 3 人小组每个小组自由支配活动经费单独活动。团队中的成员两两之间的熟悉程度互不相同为了最大化降低成员之间的陌生程度分组时需要考虑尽可能将不熟悉的成员匹配在一起通过团建活动彼此熟络。每个 3 人小组的熟悉程度定义为小组内成员两两之间的熟悉程度之和分组方案需最小化所有小组的熟悉程度之和。
作为一名算法工程师小茗同学开始着手解决这个问题但是遇到了一点小困难想请你帮忙一起解决。
输入格式
第一行为一个整数 N表示团队成员人数。 接下来 N 行每行有 N 个整数 r_{i,j}表示成员 i 与成员 j 的熟悉程度。
输出格式
输出一个整数表示将团队成员分成多个 3 人小组后熟悉程度之和的最小值。
输入样例
输入样例 1
3
100 78 97
78 100 55
97 55 100
输入样例 2
6
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的计算量
vectorlong long dp(1 N, LLONG_MAX);dp[0] 0;// 预处理每个小组的熟悉程度之和unordered_mapstring, 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 位与 mask2进制 的第 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 stringusing namespace std;int solution(int N, vectorvectorint familiarMatrix) {// 初始化 dp 数组vectorlong long dp(1 N, LLONG_MAX);dp[0] 0;// 预处理每个小组的熟悉程度之和unordered_mapstring, 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() {vectorvectorint familiarMatrix1 {{100, 78, 97},{78, 100, 55},{97, 55, 100}};vectorvectorint 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;
} 运行结果
