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

解法一"/>

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

分享一个大牛的人工智能教程。零基础！通俗易懂！风趣幽默！希望你也加入到人工智能的队伍中来！请轻击人工智能教程

package live.every.day.ProgrammingDesign.CodingInterviewGuide.Other;/*** 邮局选址问题** 【题目】* 一条直线上有居民点，邮局只能建在居民点上。给定一个有序整型数组arr，每个值表示居民点的一维坐标，再给定一个正数num，表* 示邮局数量。选择num个居民点建立num个邮局，使所有的居民点到邮局的总距离最短，返回最短的总距离。** 【举例】* arr=[1,2,3,4,5,1000]，num=2。* 第一个邮局建立在3位置，第二个邮局建立在1000位置。那么1位置到邮局距离为2，2位置到邮局距离为1，3位置到邮局距离为0，4位* 置到邮局距离为1，5位置到邮局距离为2，1000位置到邮局距离为0。所以这种方案下的总距商为6，其他任何方案的总距离都不会比* 该方案的总距离更短，所以返回6。** 【难度】* 困难** 【解答】* 方法一，动态规划。首先解决一个问题，如果在arr[i..j](0<=i<=j<N)区域上只能建一个邮局，并且这个区域上的居民点都前往这* 个邮局，要让arr[i..j]上所有的居民点到邮局的总距离最短，这个邮局应该建在哪里？如果arr[i..j]上有奇数个民居点，邮局建* 在中点位置会使总距离最短；如果arr[i..j]上有偶数个民居点，此时认为中点有两个，邮局建在哪个中点上都行，都会使总距离最* 短。根据这种思路，我们先生成一个规模为NxN的矩阵w，w[i][j](0<=i<=j<N)的值代表如果在arr[i..j](0<=i<=j<N)区域上* 只建一个邮局，这一区间上的总距离为多少。因为始终有i<=j的要求，所以我们求w矩阵的时候，实际上只求w矩阵的一半。* 求w矩阵的过程。在求每一个位置w[i][j]的时候，求法并不是把区间arr[i..j]上的每个位置到中点的距离求出后累加，这样求虽然* 肯定正确，但会很慢。更快速的求法是如果已经求出了w[i][j-1]的值，那么w[i][j]=w[i][j-1]+arr[j]-arr[(i+j)/2]。解* 释一下这是为什么，如果arr[i..j-1]上有奇数个点，那么中点是arr[(i+j-1)/2]，加上arr[j]之后，arr[i..j]有偶数个点，* 第一个中点是arr[(i+j)/2]。在这种情況下，(i+j-1)/2和(i+j/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[(i+j)/2]的距离，即w[i][j]=w[i][j-1]+arr[j]-arr[(i+j)/2]。如果arr[i..j-1]上有偶数个点，中点有两个，无* 论选在哪一个，w[i][j-1]的值都是一样的。加上arr[j]之后，arr[i..j]有奇数个点，中点是arr[(i+j)/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[(i+j)/2]的距离，即w[i][j]=w[i][j-1]+arr[j]-arr[(i+j)/2]。所以w矩阵求解的代码片段如下。* 如上代码中让把w申请成规模(N+1)x(N+1)的原因是为了在接下来的代码实现中，省去很多越界的判断，实际上w的有效区域就是* w[0..N][0..N]中的一半，剩下的部分都是0。* 有了w矩阵之后，接下来介绍动态规划的过程。dp[a][b]的值代表如果在arr[0..b]上建设a+1个邮局，总距离最少是多少。所以* dp[0][b]的值代表如果在arr[0..b]上建设1个邮局，总距离最少是多少。很明显，总距离最少是w[0][b]。那么dp[0][0..N-1]* 上的所有值都可以直接赋值，即如下的代码片段。* 当arr[0..b]上可以建设不止1个邮局时，即dp[a][b](a>0)时，应该如何计算？举例说明，比如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[k+1][b](0<=k<N}。* 方法一的全部过程请参看如下代码中的minDistances1方法。* w矩阵的求解过程O(N^2)，动态规划的求解过程O(N^2*num)。所以方法一总的时间复杂为O(N^2)+O(N^2*num)，即O(N^2*num)。** @author Created by LiveEveryDay*/public class PostOfficeAddressProblem1 {public static int minDistances1(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];for (int j = 0; j != arr.length; j++) {dp[0][j] = w[0][j];}for (int i = 1; i < num; i++) {for (int j = i + 1; j < arr.length; j++) {dp[i][j] = Integer.MAX_VALUE;for (int k = 0; k <= j; k++) {dp[i][j] = Math.min(dp[i][j], dp[i - 1][k] + w[k + 1][j]);}}}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", minDistances1(arr, num));}}// ------ Output ------
/*
The min distance is: 6
*/