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

华为OD机试 - 基站维护工程师数 - 动态规划（Python/JS/C/C++ 2024 E卷 200分）

news 2025/5/5 10:20:54

在这里插入图片描述

华为OD机试 2024E卷题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试真题（Python/JS/C/C++）》。

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

小王是一名基站维护工程师，负责某区域的基站维护。某地方有 n 个基站 (1 < n < 10)，已知各基站之间的距离 s (0 <= s < 500)，并且基站 x 到基站 y 的距离，与基站 y 到基站 x 的距离并不一定会相同。

小王从基站 1 出发，途经每个基站 1 次，然后返回基站 1。需要请你为他选择一条距离最短的路径。

二、输入描述

站点数 n 和各站点之间的距离 (均为整数)。

三、输出描述

最短路径的数值。

四、测试用例

测试用例1：

1、输入

3
0 2 1
1 0 2
2 1 0

2、输出

3、说明

测试用例2：

1、输入

4
0 10 15 20
10 0 35 25
15 35 0 30
20 25 30 0

2、输出

3、说明

路径 1 → 2 → 4 → 3 → 1，总距离为10 + 25 + 30 + 15 = 80。

五、解题思路

该问题是典型的旅行商问题（Traveling Salesman Problem, TSP），其中小王需要从基站1出发，经过每个基站一次后返回基站1。由于基站数量 n 较小（1 < n < 10），可以使用动态规划（Dynamic Programming, DP）结合位掩码（Bitmasking）来高效地解决。

距离矩阵（二维数组）：
- 使用二维数组 s[n][n] 存储各基站之间的距离。
- 由于距离不对称，即 s[i][j] 不一定等于 s[j][i]，所以需要单独存储。
动态规划数组（二维数组）：
- 使用 dp[mask][i] 表示访问过的基站集合为 mask，且最后访问的基站是 i 的最短路径长度。
- mask 使用位掩码表示，其中第 k 位为1表示第 k 个基站已被访问。
算法流程：
- 初始化 dp 数组，将起点基站1（索引0）的状态设为0。
- 遍历所有可能的基站访问状态，通过动态规划逐步更新每个状态下的最短路径长度。
- 遍历所有可能的结束基站，计算返回起点的最短路径，并取最小值作为结果。

六、Python算法源码

import sysdef main():# 读取所有输入input = sys.stdin.read().split()index = 0# 读取基站数量n = int(input[index])index += 1# 初始化距离矩阵s = []for i in range(n):row = []for j in range(n):row.append(int(input[index]))index += 1s.append(row)# 全部基站的状态，使用位掩码表示FULL_MASK = (1 << n) - 1# 初始化动态规划数组，dp[mask][i] 表示访问过mask状态，最后访问的基站是i的最小距离dp = [[float('inf')] * n for _ in range(1 << n)]# 起点是基站1，对应索引0，访问了基站1的状态dp[1 << 0][0] = 0# 遍历所有可能的状态for mask in range(1 << n):for last in range(n):# 如果当前状态没有访问到last基站，跳过if not (mask & (1 << last)):continue# 尝试扩展到下一个未访问的基站for next in range(n):# 如果已经访问过next基站，跳过if mask & (1 << next):continue# 更新新的状态newMask = mask | (1 << next)dp[newMask][next] = min(dp[newMask][next], dp[mask][last] + s[last][next])# 最终结果，回到起点基站1res = float('inf')for last in range(n):if last == 0:continue  # 不考虑起点自身res = min(res, dp[FULL_MASK][last] + s[last][0])# 输出最短路径print(res)if __name__ == "__main__":main()

七、JavaScript算法源码

const readline = require('readline');const rl = readline.createInterface({input: process.stdin,output: process.stdout
});let input = [];
rl.on('line', (line) => {input = input.concat(line.trim().split(/\s+/).map(Number));
}).on('close', () => {let index = 0;// 读取基站数量const n = input[index++];// 初始化距离矩阵const s = [];for(let i = 0; i < n; i++) {const row = [];for(let j = 0; j < n; j++) {row.push(input[index++]);}s.push(row);}// 全部基站的状态，使用位掩码表示const FULL_MASK = (1 << n) - 1;// 初始化动态规划数组，dp[mask][i] 表示访问过mask状态，最后访问的基站是i的最小距离const dp = Array.from({length: 1 << n}, () => Array(n).fill(Infinity));// 起点是基站1，对应索引0，访问了基站1的状态dp[1 << 0][0] = 0;// 遍历所有可能的状态for(let mask = 0; mask < (1 << n); mask++) {for(let last = 0; last < n; last++) {// 如果当前状态没有访问到last基站，跳过if( (mask & (1 << last)) === 0 ) continue;// 尝试扩展到下一个未访问的基站for(let next = 0; next < n; next++) {// 如果已经访问过next基站，跳过if(mask & (1 << next)) continue;// 更新新的状态const newMask = mask | (1 << next);dp[newMask][next] = Math.min(dp[newMask][next], dp[mask][last] + s[last][next]);}}}// 最终结果，回到起点基站1let res = Infinity;for(let last = 0; last < n; last++) {if(last === 0) continue; // 不考虑起点自身res = Math.min(res, dp[FULL_MASK][last] + s[last][0]);}// 输出最短路径console.log(res);
});

八、C算法源码

#include <stdio.h>
#include <limits.h>int main(){int n;// 读取基站数量scanf("%d", &n);// 初始化距离矩阵int s[n][n];for(int i=0;i<n;i++){for(int j=0;j<n;j++){scanf("%d", &s[i][j]);}}// 全部基站的状态，使用位掩码表示int FULL_MASK = (1 << n) - 1;// 初始化动态规划数组，dp[mask][i] 表示访问过mask状态，最后访问的基站是i的最小距离long long dp[1<<n][n];for(int mask=0; mask<(1<<n); mask++){for(int i=0; i<n; i++){dp[mask][i] = LLONG_MAX / 2; // 避免溢出}}// 起点是基站1，对应索引0，访问了基站1的状态dp[1<<0][0] = 0;// 遍历所有可能的状态for(int mask=0; mask<(1<<n); mask++){for(int last=0; last<n; last++){// 如果当前状态没有访问到last基站，跳过if( (mask & (1<<last)) == 0 ) continue;// 尝试扩展到下一个未访问的基站for(int next=0; next<n; next++){// 如果已经访问过next基站，跳过if( mask & (1<<next) ) continue;// 更新新的状态int newMask = mask | (1<<next);if(dp[newMask][next] > dp[mask][last] + s[last][next]){dp[newMask][next] = dp[mask][last] + s[last][next];}}}}// 最终结果，回到起点基站1long long res = LLONG_MAX;for(int last=0; last<n; last++){if(last == 0) continue; // 不考虑起点自身if(res > dp[FULL_MASK][last] + s[last][0]){res = dp[FULL_MASK][last] + s[last][0];}}// 输出最短路径printf("%lld\n", res);return 0;
}

九、C++算法源码

#include <bits/stdc++.h>
using namespace std;int main(){ios::sync_with_stdio(false);cin.tie(0);int n;// 读取基站数量cin >> n;// 初始化距离矩阵vector<vector<int>> s(n, vector<int>(n));for(int i=0;i<n;i++) {for(int j=0;j<n;j++) {cin >> s[i][j];}}// 全部基站的状态，使用位掩码表示int FULL_MASK = (1 << n) - 1;// 初始化动态规划数组，dp[mask][i] 表示访问过mask状态，最后访问的基站是i的最小距离vector<vector<long long>> dp(1<<n, vector<long long>(n, LLONG_MAX / 2));// 起点是基站1，对应索引0，访问了基站1的状态dp[1<<0][0] = 0;// 遍历所有可能的状态for(int mask=0; mask<(1<<n); mask++){for(int last=0; last<n; last++){// 如果当前状态没有访问到last基站，跳过if( (mask & (1<<last)) == 0 ) continue;// 尝试扩展到下一个未访问的基站for(int next=0; next<n; next++){// 如果已经访问过next基站，跳过if(mask & (1<<next)) continue;// 更新新的状态int newMask = mask | (1<<next);dp[newMask][next] = min(dp[newMask][next], dp[mask][last] + (long long)s[last][next]);}}}// 最终结果，回到起点基站1long long res = LLONG_MAX;for(int last=0; last<n; last++){if(last == 0) continue; // 不考虑起点自身res = min(res, dp[FULL_MASK][last] + (long long)s[last][0]);}// 输出最短路径cout << res;return 0;
}