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

华为OD机试 - 快递员的烦恼 - 动态规划（Python/JS/C/C++ 2024 D卷 200分）

news 2025/1/16 2:01:38

在这里插入图片描述

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

专栏导读

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

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

一、题目描述

快递公司每日早晨，给每位快递员推送需要淡到客户手中的快递以及路线信息，快递员自己又查找了一些客户与客户之间的路线距离信息，请你依据这些信息，给快递员设计一条最短路径，告诉他最短路径的距离。

不限制快递包裹送到客户手中的顺序，但必须保证都送到客户手中；

用例保证一定存在投递站到每位客户之间的路线，但不保证客户与客户之间有路线，客户位置及投递站均允许多次经过；

所有快递送完后，快递员需回到投递站；

二、输入描述

首行输入两个正整数n、m.

接下来n行，输入快递公司发布的客户快递信息，格式为：客户id 投递站到客户之间的距离distance

再接下来的m行，是快递员自行查找的客户与客户之间的距离信息，格式为：客户1id 客户2id distance

在每行数据中，数据与数据之间均以单个空格分割规格:

0 <=n <= 10 0 <= m <= 10 0 < 客户id <= 1000 0 < distance <= 10000

三、输出描述

最短路径距离，如无法找到，请输出-1

四、测试用例

测试用例1：

1、输入

2 2
1 300
2 400
1 2 200
2 1 250

2、输出

900

3、说明

最短路径为：投递站 -> 客户1(300) -> 客户2(200) -> 投递站(400) = 300 + 200 + 400 = 900。

测试用例2：

1、输入

2 1
1 1000
2 1200
1 2 300

2、输出

2500

3、说明

快递员先把快递送到客户1手中，接下来直接走客户1到客户2之间的直通线路，最后走投递站和客户2之间的路，回到投递站，距离为1000+300+1200= 2500

五、解题思路

可以利用图的遍历方法，特别是基于图的最短路径问题。这个问题实际上是一个变种的旅行销售员问题（TSP），需要找到一个最短的路径，让快递员从投递站出发，经过所有客户位置至少一次，然后返回投递站。我们可以通过以下步骤来解决这个问题：

解题思路：

  1. 首先将所有的点（包括投递站和客户）以及它们之间的距离建模成一个完全图。对于客户与客户之间没有直接距离的情况，可以考虑用一个很大的数（如无穷）来表示两点之间无法直接到达。
  2. 由于图中点的数量较少（最多10个客户加一个投递站），我们可以使用Floyd-Warshall算法预处理任意两点间的最短路径。这个算法能在多项式时间内处理完所有点对的最短路径问题。
  3. 在获取了所有点对间的最短路径后，使用动态规划解决TSP问题。状态dp[mask][i]表示已访问的客户集合为mask，当前在客户i的最短路径长度。转移方程需要考虑从任一客户j到i的转移，更新状态。
  4. 计算总路程：计算包括从投递站出发、访问所有客户以及返回投递站的总最短路径长度。
  5. 输出结果：输出计算出的最短路径长度，如果存在无法到达的情况，输出-1。

六、动态规划

动态规划（Dynamic Programming, DP）是一种算法设计技术，用于解决具有重叠子问题和最优子结构的问题。它通常用于求解优化问题。在动态规划中，复杂问题被分解为更小的子问题，这些子问题被逐一解决，并将结果存储起来（称为 “记忆化”），以避免重复计算相同的问题。

1、动态规划的两个主要特征

  1. 重叠子问题：原问题可以分解成许多更小的子问题，且子问题会重复出现。例如，在斐波那契数列的计算中，求解 fib(5) 需要求解 fib(4) 和 fib(3)，而求解 fib(4) 又需要求解 fib(3) 和 fib(2)，这里的 fib(3) 就是一个重叠子问题。
  2. 最优子结构：原问题的最优解包含其子问题的最优解。即一旦我们得到了子问题的最优解，就可以利用这些解构造原问题的最优解。例如，在计算最短路径问题中，从点A到点C的最短路径如果经过点B，则从点A到点B的路径也应是最短路径。

2、动态规划的基本步骤

  1. 定义状态：将问题的解定义成状态，通常是一个数组或矩阵。
  2. 设定状态转移方程：找出状态之间的关系，如何从一个或多个较小的状态推导出当前状态。
  3. 确定边界条件：这些是最小子问题的解，它们作为构建更复杂解答的基础。
  4. 计算并存储解：按照顺序从最小的子问题开始解决，存储它们的结果，逐步构建最终的解决方案。

3、常见可以用动态规划解决的问题类型：

  1. 斐波那契数列：计算第n个斐波那契数。
  2. 0/1背包问题：给定一组物品和一个背包的容量，选择其中若干物品装入背包，使得装入的总价值最大，且总重量不超过背包容量。
  3. 最长公共子序列：找出两个序列共有的最长子序列的长度。
  4. 最短路径问题（如Floyd-Warshall算法）：在给定的图中找到所有点对之间的最短路径。
  5. 硬币找零问题：给定不同面额的硬币和一个总金额，找出组成该金额的最少硬币数量。
  6. 编辑距离（Levenshtein距离）：计算从一个字符串转换成另一个字符串最少的插入、删除和替换操作数。
  7. 旅行销售员问题（TSP）：在加权图中找到访问每个顶点恰好一次并返回起点的最短回路。
  8. 最长递增子序列：在一个数列中找到一个最长的递增子序列的长度。

六、Python算法源码

import sysMAX = 10000  # 表示无法到达的一个大数
MAX_CLIENTS = 11  # 最多10个客户和1个投递站def optimize_delivery(n, m, delivery_info, customer_distances):V = n + 1  # 顶点总数，包括投递站和所有客户dist = [[MAX] * V for _ in range(V)]  # 初始化距离数组# 初始化自环距离for i in range(V):dist[i][i] = 0# 填充投递站到客户的距离for client_id, distance in delivery_info:dist[0][client_id] = distancedist[client_id][0] = distance# 填充客户间的距离for cust1, cust2, distance in customer_distances:dist[cust1][cust2] = min(dist[cust1][cust2], distance)dist[cust2][cust1] = min(dist[cust2][cust1], distance)# 使用Floyd-Warshall算法计算最短路径for k in range(V):for i in range(V):for j in range(V):if dist[i][k] < MAX and dist[k][j] < MAX:dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])# 解决TSP问题ALL_VISITED = (1 << n) - 1  # 全部访问过的状态dp = [[MAX] * n for _ in range(1 << n)]# 初始化状态for i in range(n):dp[1 << i][i] = dist[0][i + 1]# 动态规划for mask in range(1 << n):for i in range(n):if (mask & (1 << i)) != 0:  # 如果i已访问for j in range(n):if (mask & (1 << j)) == 0:  # 如果j未访问next_mask = mask | (1 << j)dp[next_mask][j] = min(dp[next_mask][j], dp[mask][i] + dist[i + 1][j + 1])# 返回到投递站的最短路径min_path = MAXfor i in range(n):min_path = min(min_path, dp[ALL_VISITED][i] + dist[i + 1][0])return -1 if min_path == MAX else min_pathif __name__ == "__main__":n, m = map(int, input().split())delivery_info = [tuple(map(int, input().split())) for _ in range(n)]customer_distances = [tuple(map(int, input().split())) for _ in range(m)]result = optimize_delivery(n, m, delivery_info, customer_distances)print(result)

七、JavaScript算法源码

const MAX = 10000; // 表示无法到达的一个大数
const MAX_CLIENTS = 11; // 最多10个客户和1个投递站function optimizeDelivery(n, m, deliveryInfo, customerDistances) {const V = n + 1; // 顶点总数，包括投递站和所有客户let dist = Array.from({ length: V }, () => Array(V).fill(MAX)); // 初始化距离数组// 初始化自环距离for (let i = 0; i < V; i++) {dist[i][i] = 0;}// 填充投递站到客户的距离for (const [clientId, distance] of deliveryInfo) {dist[0][clientId] = distance;dist[clientId][0] = distance;}// 填充客户间的距离for (const [cust1, cust2, distance] of customerDistances) {dist[cust1][cust2] = Math.min(dist[cust1][cust2], distance);dist[cust2][cust1] = Math.min(dist[cust2][cust1], distance);}// 使用Floyd-Warshall算法计算最短路径for (let k = 0; k < V; k++) {for (let i = 0; i < V; i++) {for (let j = 0; j < V; j++) {if (dist[i][k] < MAX && dist[k][j] < MAX) {dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);}}}}// 解决TSP问题const ALL_VISITED = (1 << n) - 1; // 全部访问过的状态let dp = Array.from({ length: 1 << n }, () => Array(n).fill(MAX));// 初始化状态for (let i = 0; i < n; i++) {dp[1 << i][i] = dist[0][i + 1];}// 动态规划for (let mask = 0; mask <= ALL_VISITED; mask++) {for (let i = 0; i < n; i++) {if ((mask & (1 << i)) !== 0) { // 如果i已访问for (let j = 0; j < n; j++) {if ((mask & (1 << j)) === 0) { // 如果j未访问const nextMask = mask | (1 << j);dp[nextMask][j] = Math.min(dp[nextMask][j], dp[mask][i] + dist[i + 1][j + 1]);}}}}}// 返回到投递站的最短路径let minPath = MAX;for (let i = 0; i < n; i++) {minPath = Math.min(minPath, dp[ALL_VISITED][i] + dist[i + 1][0]);}return minPath === MAX ? -1 : minPath;
}// 输入处理
const input = require('fs').readFileSync('/dev/stdin', 'utf8').split('\n');
const [n, m] = input[0].split(' ').map(Number);
const deliveryInfo = input.slice(1, n + 1).map(line => line.split(' ').map(Number));
const customerDistances = input.slice(n + 1, n + m + 1).map(line => line.split(' ').map(Number));
const result = optimizeDelivery(n, m, deliveryInfo, customerDistances);
console.log(result);

八、C算法源码

#include <stdio.h>
#include <limits.h>
#include <string.h>#define MAX 10000
#define MAX_CLIENTS 11int optimizeDelivery(int n, int m, int deliveryInfo[MAX_CLIENTS][2], int customerDistances[MAX_CLIENTS][3]) {int V = n + 1;int dist[MAX_CLIENTS][MAX_CLIENTS];// 初始化距离数组for (int i = 0; i < V; i++) {for (int j = 0; j < V; j++) {dist[i][j] = (i == j) ? 0 : MAX;}}// 填充投递站到客户的距离for (int i = 0; i < n; i++) {int clientId = deliveryInfo[i][0];int distance = deliveryInfo[i][1];dist[0][clientId] = distance;dist[clientId][0] = distance;}// 填充客户间的距离for (int i = 0; i < m; i++) {int cust1 = customerDistances[i][0];int cust2 = customerDistances[i][1];int distance = customerDistances[i][2];dist[cust1][cust2] = (dist[cust1][cust2] < distance) ? dist[cust1][cust2] : distance;dist[cust2][cust1] = (dist[cust2][cust1] < distance) ? dist[cust2][cust1] : distance;}// 使用Floyd-Warshall算法计算最短路径for (int k = 0; k < V; k++) {for (int i = 0; i < V; i++) {for (int j = 0; j < V; j++) {if (dist[i][k] < MAX && dist[k][j] < MAX) {dist[i][j] = (dist[i][j] < dist[i][k] + dist[k][j]) ? dist[i][j] : (dist[i][k] + dist[k][j]);}}}}// 解决TSP问题int ALL_VISITED = (1 << n) - 1;int dp[1 << MAX_CLIENTS][MAX_CLIENTS];memset(dp, MAX, sizeof(dp));// 初始化状态for (int i = 0; i < n; i++) {dp[1 << i][i] = dist[0][i + 1];}// 动态规划for (int mask = 0; mask <= ALL_VISITED; mask++) {for (int i = 0; i < n; i++) {if (mask & (1 << i)) { // 如果i已访问for (int j = 0; j < n; j++) {if (!(mask & (1 << j))) { // 如果j未访问int nextMask = mask | (1 << j);if (dp[nextMask][j] > dp[mask][i] + dist[i + 1][j + 1]) {dp[nextMask][j] = dp[mask][i] + dist[i + 1][j + 1];}}}}}}// 返回到投递站的最短路径int minPath = MAX;for (int i = 0; i < n; i++) {if (minPath > dp[ALL_VISITED][i] + dist[i + 1][0]) {minPath = dp[ALL_VISITED][i] + dist[i + 1][0];}}return (minPath == MAX) ? -1 : minPath;
}int main() {int n, m;scanf("%d %d", &n, &m);int deliveryInfo[MAX_CLIENTS][2], customerDistances[MAX_CLIENTS][3];for (int i = 0; i < n; i++) {scanf("%d %d", &deliveryInfo[i][0], &deliveryInfo[i][1]);}for (int i = 0; i < m; i++) {scanf("%d %d %d", &customerDistances[i][0], &customerDistances[i][1], &customerDistances[i][2]);}int result = optimizeDelivery(n, m, deliveryInfo, customerDistances);printf("%d\n", result);return 0;
}

九、C++算法源码

#include <iostream>
#include <vector>
#include <limits.h>using namespace std;const int MAX = 10000;
const int MAX_CLIENTS = 11;int optimizeDelivery(int n, int m, vector<pair<int, int>> &deliveryInfo, vector<tuple<int, int, int>> &customerDistances) {int V = n + 1;int dist[MAX_CLIENTS][MAX_CLIENTS];// 初始化距离数组for (int i = 0; i < V; i++) {for (int j = 0; j < V; j++) {dist[i][j] = (i == j) ? 0 : MAX;}}// 填充投递站到客户的距离for (auto &info : deliveryInfo) {int clientId = info.first;int distance = info.second;dist[0][clientId] = distance;dist[clientId][0] = distance;}// 填充客户间的距离for (auto &custDist : customerDistances) {int cust1 = get<0>(custDist);int cust2 = get<1>(custDist);int distance = get<2>(custDist);dist[cust1][cust2] = min(dist[cust1][cust2], distance);dist[cust2][cust1] = min(dist[cust2][cust1], distance);}// 使用Floyd-Warshall算法计算最短路径for (int k = 0; k < V; k++) {for (int i = 0; i < V; i++) {for (int j = 0; j < V; j++) {if (dist[i][k] < MAX && dist[k][j] < MAX) {dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);}}}}// 解决TSP问题int ALL_VISITED = (1 << n) - 1;vector<vector<int>> dp(1 << MAX_CLIENTS, vector<int>(MAX_CLIENTS, MAX));// 初始化状态for (int i = 0; i < n; i++) {dp[1 << i][i] = dist[0][i + 1];}// 动态规划for (int mask = 0; mask <= ALL_VISITED; mask++) {for (int i = 0; i < n; i++) {if (mask & (1 << i)) { // 如果i已访问for (int j = 0; j < n; j++) {if (!(mask & (1 << j))) { // 如果j未访问int nextMask = mask | (1 << j);dp[nextMask][j] = min(dp[nextMask][j], dp[mask][i] + dist[i + 1][j + 1]);}}}}}// 返回到投递站的最短路径int minPath = MAX;for (int i = 0; i < n; i++) {minPath = min(minPath, dp[ALL_VISITED][i] + dist[i + 1][0]);}return (minPath == MAX) ? -1 : minPath;
}int main() {int n, m;cin >> n >> m;vector<pair<int, int>> deliveryInfo(n);vector<tuple<int, int, int>> customerDistances(m);for (int i = 0; i < n; i++) {cin >> deliveryInfo[i].first >> deliveryInfo[i].second;}for (int i = 0; i < m; i++) {cin >> get<0>(customerDistances[i]) >> get<1>(customerDistances[i]) >> get<2>(customerDistances[i]);}int result = optimizeDelivery(n, m, deliveryInfo, customerDistances);cout << result << endl;return 0;
}

🏆下一篇：华为OD机试真题 - 简易内存池（Python/JS/C/C++ 2024 E卷 200分）

🏆本文收录于，华为OD机试真题（Python/JS/C/C++）

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

在这里插入图片描述


http://www.mrgr.cn/news/63213.html

相关文章：

  • 数据仓库: 10- 新技术与趋势
  • 服务器一次性部署One API + ChatGPT-Next-Web
  • 学习模板之一
  • HTTP常见状态码：从1xx到 5xx的全面解析
  • typescript语法
  • 线程并发下的单例模式
  • Halcon 2D测量Metrology找线/圆/矩形/椭圆
  • Git进阶（十七）：特性分支
  • 用二维码展示信息，有哪些常见应用场景
  • Idea常用插件
  • 2025 年IT技术人员关键技能（非常详细），零基础入门到精通，看这一篇就够了
  • Go使用SIMD指令——以string转为整数为例
  • netty之bootstrap源码分析
  • Android 中选择本地文件并获取文件路径
  • BC1 2充电协议简介
  • JS进阶级案例-----时钟
  • Python零基础 [2.3] if else 语句的详解与示例
  • 《PHP爬虫：当“购物狂”遇上“代码诗人”》
  • 算子级血缘助企业数据管理“自动化、精细化、智能化”
  • Redis 中的定期删除和惰性删除究竟是怎样实现的？
  • flutter报错‘/Users/xxx/.gradle/caches/journal-1/file-access.bin‘.
  • 用图像增强来充实训练数据集，算不算是一种‘摸鱼’的方法？
  • 大型语言模型如何影响就业？大模型入门到精通，收藏这篇就够了
  • 初学者如何对大模型进行微调？
  • Openlayers高级交互（14/20）：汽车移动轨迹动画（开始、暂停、结束）
  • 页面跳转不刷新 histoy.go hisroty.back不生效