华为OD机试 - 快递员的烦恼 - 动态规划（Java 2024 C卷 200分）

系统管理员 2024-04-27 07:25 69阅读 0赞

![在这里插入图片描述][986dcebce006483fb6846cb29a3928a7.gif_pic_center]

> 华为OD机试 2024C卷题库疯狂收录中，刷题[**点这里**][Link 1]

### 专栏导读 ###

本专栏收录于[《华为OD机试（JAVA）真题（A卷+B卷+C卷）》][OD_JAVA_A_B_C]。

**刷的越多，抽中的概率越大**，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。

### 一、题目描述 ###

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

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

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

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

### 二、输入描述 ###

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

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

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

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

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

### 三、输出描述 ###

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

### 四、解题思路 ###

可以利用图的遍历方法，特别是基于图的最短路径问题。这个问题实际上是一个变种的旅行销售员问题（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.  最长递增子序列：在一个数列中找到一个最长的递增子序列的长度。

### 六、Java算法源码 ###

public class Test02 {
        
        /**
         * 2 1
         * 1 1000
         * 2 1200
         * 1 2 300
         *
         * 快递员先把快递送到客户1手中，接下来直接走客户1到客户2之间的直通线路，最后走投递站和客户2之间的路，回到投递站，距离为1000+300+1200= 2500
         */
        static final int MAX = 10000; // 一个比较大的数，用于表示无法直接到达
        static final int MAX_CLIENTS = 11; // 最多10个客户加上一个投递站
    
        public static int optimizeDelivery(int n, int m, int[][] deliveryInfo, int[][] customerDistances) {
        
            int V = n + 1; // 顶点总数，包括投递站和所有客户
            int[][] dist = new int[V][V]; // 存储最短路径的距离数组
    
            // 初始化距离数组
            for (int i = 0; i < V; i++) {
        
                Arrays.fill(dist[i], MAX);
                dist[i][i] = 0; // 到自己的距离是0
            }
    
            // 填充投递站到客户的距离
            for (int[] info : deliveryInfo) {
        
                int clientId = info[0];
                int distance = info[1];
                dist[0][clientId] = distance;
                dist[clientId][0] = distance;
            }
    
            // 填充客户间的距离
            for (int[] custDist : customerDistances) {
        
                int cust1 = custDist[0];
                int cust2 = custDist[1];
                int distance = custDist[2];
                dist[cust1][cust2] = Math.min(dist[cust1][cust2], distance); // 取最小值，考虑重复边
                dist[cust2][cust1] = Math.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] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                        }
                    }
                }
            }
    
            // 解决TSP问题
            int ALL_VISITED = (1 << n) - 1; // 全部访问过的状态
            int[][] dp = new int[1 << n][n];
            for (int[] row : dp) {
        
                Arrays.fill(row, MAX);
            }
    
            // 初始化，从投递站到所有客户的起始距离
            for (int i = 1; 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)) != 0) {
         // 如果i已访问
                        for (int j = 0; j < n; j++) {
        
                            if ((mask & (1 << j)) == 0) {
         // 如果j未访问
                                int nextMask = mask | (1 << j);
                                dp[nextMask][j] = Math.min(dp[nextMask][j], dp[mask][i] + dist[i + 1][j + 1]);
                            }
                        }
                    }
                }
            }
    
            // 从任何客户返回投递站的最短路径
            int minPath = MAX;
            for (int i = 0; i < n; i++) {
        
                minPath = Math.min(minPath, dp[ALL_VISITED][i] + dist[i + 1][0]);
            }
    
            return minPath == MAX ? -1 : minPath;
        }
    
        public static void main(String[] args) {
        
            Scanner scanner = new Scanner(System.in);
            int n = scanner.nextInt();
            int m = scanner.nextInt();
            int[][] deliveryInfo = new int[n][2];
            for (int i = 0; i < n; i++) {
        
                deliveryInfo[i][0] = scanner.nextInt();
                deliveryInfo[i][1] = scanner.nextInt();
            }
            int[][] customerDistances = new int[m][3];
            for (int i = 0; i < m; i++) {
        
                customerDistances[i][0] = scanner.nextInt();
                customerDistances[i][1] = scanner.nextInt();
                customerDistances[i][2] = scanner.nextInt();
            }
            int result = optimizeDelivery(n, m, deliveryInfo, customerDistances);
            System.out.println(result);
        }
    }

### 七、效果展示 ###

#### 1、输入 ####

2 1  
1 1000  
2 1200  
1 2 300

#### 2、输出 ####

2500

#### 3、说明 ####

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

![在这里插入图片描述][a72c77ca63ea4bb6b7d3cb626b6b33c6.png_pic_center]

?下一篇：[华为OD机试 - 简易内存池 - 逻辑分析（Java 2024 C卷 200分）][OD_ - _ - _Java 2024 C_ 200]

?本文收录于，[华为OD机试（JAVA）真题（A卷+B卷+C卷）][OD_JAVA_A_B_C]

**刷的越多，抽中的概率越大**，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。

![在这里插入图片描述][8dbe8dd8723c4636af5926ccf1c511b0.gif_pic_center]

[986dcebce006483fb6846cb29a3928a7.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/839d202c635e444e974b1b28c3cdcea3.gif
[Link 1]: https://blog.csdn.net/guorui_java/article/details/132683473
[OD_JAVA_A_B_C]: https://blog.csdn.net/guorui_java/category_12293298.html
[a72c77ca63ea4bb6b7d3cb626b6b33c6.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/2759b6f2906a4ae49a378c43f8648701.png
[OD_ - _ - _Java 2024 C_ 200]: https://blog.csdn.net/guorui_java/article/details/132197477
[8dbe8dd8723c4636af5926ccf1c511b0.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/27c36983a9874d818995376e31796e42.gif