【困难】邮局选址问题－Java：解法二

分享一个大牛的人工智能教程。零基础通俗易懂风趣幽默希望你也加入到人工智能的队伍中来请轻击人工智能教程大家好欢迎来到我的网站 人工智能被认为是一种拯救世界、终结世界的技术。毋庸置疑人工智能时代就要来临了科… 继续阅读 前言https://www.captainai.net/troubleshooterpackage live.every.day.ProgrammingDesign.CodingInterviewGuide.Other; /** * 邮局选址问题 * * 【题目】 * 一条直线上有居民点邮局只能建在居民点上。给定一个有序整型数组arr每个值表示居民点的一维坐标再给定一个正数num表 * 示邮局数量。选择num个居民点建立num个邮局使所有的居民点到邮局的总距离最短返回最短的总距离。 * * 【举例】 * arr[1,2,3,4,5,1000]num2。 * 第一个邮局建立在3位置第二个邮局建立在1000位置。那么1位置到邮局距离为22位置到邮局距离为13位置到邮局距离为04位 * 置到邮局距离为15位置到邮局距离为21000位置到邮局距离为0。所以这种方案下的总距商为6其他任何方案的总距离都不会比 * 该方案的总距离更短所以返回6。 * * 【难度】 * 困难 * * 【解答】 * 方法一动态规划。首先解决一个问题如果在arr[i..j](0ijN)区域上只能建一个邮局并且这个区域上的居民点都前往这 * 个邮局要让arr[i..j]上所有的居民点到邮局的总距离最短这个邮局应该建在哪里如果arr[i..j]上有奇数个民居点邮局建 * 在中点位置会使总距离最短如果arr[i..j]上有偶数个民居点此时认为中点有两个邮局建在哪个中点上都行都会使总距离最 * 短。根据这种思路我们先生成一个规模为NxN的矩阵ww[i][j](0ijN)的值代表如果在arr[i..j](0ijN)区域上 * 只建一个邮局这一区间上的总距离为多少。因为始终有ij的要求所以我们求w矩阵的时候实际上只求w矩阵的一半。 * 求w矩阵的过程。在求每一个位置w[i][j]的时候求法并不是把区间arr[i..j]上的每个位置到中点的距离求出后累加这样求虽然 * 肯定正确但会很慢。更快速的求法是如果已经求出了w[i][j-1]的值那么w[i][j]w[i][j-1]arr[j]-arr[(ij)/2]。解 * 释一下这是为什么如果arr[i..j-1]上有奇数个点那么中点是arr[(ij-1)/2]加上arr[j]之后arr[i..j]有偶数个点 * 第一个中点是arr[(ij)/2]。在这种情況下(ij-1)/2和(ij/2)其实是同一个位置。比如arr[i..j-1][4,15,26]中 * 点是15。arr[i..j][4,15,26,47]第一个中点是15。所以此时w[i][j]比w[i][j-1]多出来的距离就是arr[j]到 * arr[(ij)/2]的距离即w[i][j]w[i][j-1]arr[j]-arr[(ij)/2]。如果arr[i..j-1]上有偶数个点中点有两个无 * 论选在哪一个w[i][j-1]的值都是一样的。加上arr[j]之后arr[i..j]有奇数个点中点是arr[(ij)/2]。在这种情況下 * arr[i..j-1]上的第二个中点和arr[i..j]上唯一的中点其实是同一个位置。比如arr[i..j-1][4,15,26,47]第二个中点 * 是26。arr[i..j][4,15,26,47,53]唯一的中点是26。所以此时w[i][j]比w[i][j-1]多出来的距离还是arr[j]到 * arr[(ij)/2]的距离即w[i][j]w[i][j-1]arr[j]-arr[(ij)/2]。所以w矩阵求解的代码片段如下。 * 如上代码中让把w申请成规模(N1)x(N1)的原因是为了在接下来的代码实现中省去很多越界的判断实际上w的有效区域就是 * w[0..N][0..N]中的一半剩下的部分都是0。 * 有了w矩阵之后接下来介绍动态规划的过程。dp[a][b]的值代表如果在arr[0..b]上建设a1个邮局总距离最少是多少。所以 * dp[0][b]的值代表如果在arr[0..b]上建设1个邮局总距离最少是多少。很明显总距离最少是w[0][b]。那么dp[0][0..N-1] * 上的所有值都可以直接赋值即如下的代码片段。 * 当arr[0..b]上可以建设不止1个邮局时即dp[a][b](a0)时应该如何计算举例说明比如arr[-3,-2,-1,0,1,2]要计 * 算dp[2][5]的值即可以在arr[0..5]上建立3个邮局的情况下最少的总距离是多少并且此时已经有dp[0..1][0..5]的所有值。 * 方案1邮局1、2负责[-3]邮局3负责[-2,-1,0,1,2]距离dp[1][0]w[1][5]。 * 方案2邮局1、2负责[-3,2]邮局3负责[-1,0,1,2]距离dp[1][1]w[2][5]。 * 方案3邮局1、2负责[-3,-2,-1]邮局3负责[0,1,2]距离dp[1][2]w[3][5]。 * 方案4邮局1、2负责[-3,-2,-1,0]邮局3负责[1,2]距离dp[1][3]w[4][5]。 * 方案5邮局1、2负责[-3,-2,-1,0,1]邮局3负责[2]距离dp[1][4]w[5][5]。 * 方案6邮局1、2负责[-3,-2,-1,0,1,2]邮局3负责[]距离dp[1][5]w[6][5](w越界为0)。 * 枚举所有的划分方案选一个距离最短的即可所以dp[a][b]Min{dp[a-1][k]w[k1][b](0kN}。 * 方法一的全部过程请参看如下代码中的minDistances1方法。 * w矩阵的求解过程O(N^2)动态规划的求解过程O(N^2*num)。所以方法一总的时间复杂为O(N^2)O(N^2*num)即O(N^2*num)。 * * 方法二用四边形不等式优化动态规划的枚举过程使整个过程的时间复杂度降低至O(N^2)。在方法一中求解dp[a][b]的时候几乎 * 枚举了所有的dp[a-1][0..b]但这个枚举过程其实是可以得到加速的。具体解释为 * 1.当邮局为a-l个区间为arr[0..b]时如果在其最优划分方案中发现邮局1~a-2负责arr[0..l]邮局a-l负责arr[l1..b]。 * 那么当邮局为a个区间为arr[0..b]时如果想得到最优方案邮局1~a-1负责的区域不必尝试比arr[0..1]小的区域只需尝试 * arr[0..k](k1)。 * 2.当邮局为a个区间为arr[0..b1]时如果在其最优划分方案中发现邮局1~a-1负责arr[0..m]邮局a负责arr[m1..b1]。 * 那么当邮局为a个区间为arr[0..b]时如果想得到最优方案邮局1~a-1负责的区域不必尝试比arr[0..m]大的区域只尝试 * arr[0..k](km)。 * 本题为何能用四边形不等式进行优化的证明略。有兴趣的读者可以自行学习四边形不等式的相关内容。有了这个枚举优化过程后在 * 算dp[a][b]时只用在dp[a-1][b]的最优尝试位置1和dp[a][b1]的最优尝试位置m之间进行枚举其他的位置一概不用再试。具 * 体过程请参看如下代码中的minDistances2方法。 * * author Created by LiveEveryDay */ public class PostOfficeAddressProblem2 { public static int minDistances2(int[] arr, int num) { if (arr null || num 1 || arr.length num) { return 0; } int[][] w new int[arr.length 1][arr.length 1]; for (int i 0; i arr.length; i) { for (int j i 1; j arr.length; j) { w[i][j] w[i][j - 1] arr[j] - arr[(i j) / 2]; } } int[][] dp new int[num][arr.length]; int[][] s new int[num][arr.length]; for (int j 0; j ! arr.length; j) { dp[0][j] w[0][j]; s[0][j] 0; } int minK 0; int maxK 0; int cur 0; for (int i 1; i num; i) { for (int j arr.length - 1; j i; j--) { minK s[i - 1][j]; maxK j arr.length - 1 ? arr.length - 1 : s[i][j 1]; dp[i][j] Integer.MAX_VALUE; for (int k minK; k maxK; k) { cur dp[i - 1][k] w[k 1][j]; if (cur dp[i][j]) { dp[i][j] cur; s[i][j] k; } } } } return dp[num - 1][arr.length - 1]; } public static void main(String[] args) { int[] arr {1, 2, 3, 4, 5, 1000}; int num 2; System.out.printf(The min distance is: %d, minDistances2(arr, num)); } } // ------ Output ------ /* The min distance is: 6 */