货仓选址与安排邮筒

  |  

摘要: 安排邮筒问题,使用动态规划解决

【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:潮汐朝夕
我的知乎:潮汐朝夕
我的github:FennelDumplings
我的leetcode:FennelDumplings


今天看一个非常经典的动态规划的问题,本题是第 28 双周赛 D 题,安排邮筒。

安排邮筒说的是一个一维的数轴上分布着 n 个房子,然后要在数轴上放 k 个邮筒,使得每个房子到距离最近的邮筒的距离总和最小。

本文我们先解决在 n 个房子中放 1 个邮筒的问题,然后基于这个简化问题的解来设计动态规划的状态的定义和转移。本题的动态规划算法还是可以优化的,这涉及到决策单调性的知识点,如果了解过机器学习算法的话,会发现本题还可以用层次聚类的方法解决。

决策单调性和层次聚类涉及到比较难的知识点,本文暂时只涉及最基础的动态规划算法,以后我们再来专门学习这两个知识点。

安排邮筒是非常经典的一个问题,如果把它抽象成模型的话,可以进一步解决一些应用问题,例如均分纸牌问题等。以后我们再来进一步研究。

货仓选址

题目

在一条数轴上有 N 家商店,它们的坐标分别为 A1∼AN。

现在需要在数轴上建立一家货仓,每天清晨,从货仓到每家商店都要运送一车商品。

为了提高效率,求把货仓建在何处,可以使得货仓到每家商店的距离之和最小。

1
2
3
4
5
6
7
8
9
10
输入格式
第一行输入整数 N。
第二行 N 个整数 A1∼AN。

输出格式
输出一个整数,表示距离之和的最小值。

数据范围
1<=N<=100000,
0<=Ai<=40000

输入样例:
4
6 2 9 1
输出样例:
12

算法: 中位数

  • 如果 N 是奇数,那么安排在中位数的位置是最好的。
  • 如果 N 是偶数,那么安排在中间的两个数中间的任意位置都是最好的。

以上结论可以由绝对值不等式推出。$||a| - |b|| \leq |a + b| \leq |a| + |b|$

把 A[1] ~ A[N] 排序,设货仓在坐标 X 处,X 左侧有 P 家,X 右侧有 Q 家。

  • 如果 P > Q,则将 X 向右移动 1 单位,距离值和减小 P - Q。
  • 如果 P < Q,则将 X 向左移动 1 单位,距离之和减小 Q - P。

下图是 P=5, Q=3 的情况示意图:

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

int main()
{
int N;
cin >> N;
vector<int> a(N);
for(int i = 0; i < N; ++i)
cin >> a[i];
sort(a.begin(), a.end());
int X = *(a.begin() + (N / 2));
int ans = 0;
for(int i = 0; i < N; ++i)
ans += abs(a[i] - X);
cout << ans << endl;
}

安排邮筒

题目

给你一个房屋数组 houses 和一个整数 k ,其中 houses[i] 是第 i 栋房子在一条街上的位置,现需要在这条街上安排 k 个邮筒。

请你返回每栋房子与离它最近的邮筒之间的距离的 最小 总和。

答案保证在 32 位有符号整数范围以内。

示例 1:
输入:houses = [1,4,8,10,20], k = 3
输出:5
解释:将邮筒分别安放在位置 3, 9 和 20 处。
每个房子到最近邮筒的距离和为 |3-1| + |4-3| + |9-8| + |10-9| + |20-20| = 5 。
示例 2:
输入:houses = [2,3,5,12,18], k = 2
输出:9
解释:将邮筒分别安放在位置 3 和 14 处。
每个房子到最近邮筒距离和为 |2-3| + |3-3| + |5-3| + |12-14| + |18-14| = 9 。
示例 3:
输入:houses = [7,4,6,1], k = 1
输出:8
示例 4:
输入:houses = [3,6,14,10], k = 4
输出:0

题解

算法 : 动态规划

如果考虑安排一个邮筒的情况,那就是前面的货仓选址问题。

如果有多个邮筒,那么每个邮筒的覆盖范围应该是连续的。也就是说假如有两个邮筒 T1, T2,那么他们分别负责数轴上一段连续的房子,如下图:

T2 在 T1 右侧,则 T1 和 T2 的覆盖分为不会交叉。T1 负责的房子 xi, 一定小于 T2 负责的房子 xj。

根据前面的分析,考虑 K 个邮筒时,每个邮筒负责一段连续的房子,一共有 K 段。用 dp[i][k] 表示考虑前 i 个房子分成 k 段时的距离总和最小值。也就是给前 i 个房子安排 k 个邮筒时,距离和的最小值。

对于状态转移,根据前面分析的每个邮筒的覆盖范围是连续的,前 i 个房子具体怎样被 k 个邮筒负责就比较好枚举出来了。

枚举最后一个房子的可能得覆盖范围:最大范围是前 k - 1 个邮局各自负责一个房子(即前 k-1 个邮局覆盖了 [1..k-1] 这 k - 1 个房子),最后一个邮局就覆盖 [k, i] 的所有房子;最小范围是前 k - 1 个邮局负责了 [1..i-1] 这些房子,最后一个邮局就覆盖 i 这个房子。

具体的实现方式是枚举前 k - 1 个邮局覆盖范围的最右端点 l, k - 1 <= l <= i - 1,此时考虑最后一个邮局 k,问题变成了 [l+1..i] 上安排一个邮局安排在哪里最佳的问题,这正是前面的货仓选址问题。如果定义 cost[i][j] := 在 [i..j] 上安排一个邮筒,距离总和的最小值。则 cost[l+1][i] 是我们要的值。

完整算法如下:

1
2
3
4
5
6
7
8
9
10
11
状态定义:
dp[i][k] := 考虑前 i 个房子,安排 k 个邮筒,距离和的最小值

答案:
dp[n][K]

初始化:
dp[0][0] = 0

状态转移:
dp[i][k] = min(dp[l][k - 1] + cost[l + 1][i]) 其中 k - 1 <= l <= i

预处理优化

由于每次状态转移时都要询问 cost[i][j],我们可以把所有的 cost[i][j] 预处理出来。

过程中需要用到前缀和,记 sums[i] 为前 i 个房子的坐标的总和。

[i..j] 这段房子的中位数是 m = (i + j) / 2,因此 cost[i][j] 可以分为两部分:

1
2
3
4
5
第一部分是第 m 个房子左侧的房子 [i..m-1] 到第 m 个房子的距离
houses[m - 1] * (m - i + 1) - (sums[m] - sums[i - 1])

第二部分是第 m 个房子右侧的房子 [m+1..j] 到第 m 个房子的距离
sums[j] - sums[m] - houses[m - 1] * (j - m)

代码(c++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
int minDistance(vector<int>& houses, int K) {
int n = houses.size();

sort(houses.begin(), houses.end());
vector<int> sums(n + 1);
for(int i = 0; i < n; ++i)
sums[i + 1] = houses[i] + sums[i];

vector<vector<int> > cost(n + 1, vector<int>(n + 1));
for(int i = 1; i < n; ++i)
for(int j = i + 1; j <= n; ++j)
{
int m = (i + j) / 2;
cost[i][j] = houses[m - 1] * (m - i + 1) - (sums[m] - sums[i - 1]) + (sums[j] - sums[m] - houses[m - 1] * (j - m));
}

vector<vector<int> > dp(n + 1, vector<int>(K + 1, INT_MAX / 2));
dp[0][0] = 0;
for(int k = 1; k <= K; ++k)
for(int i = 1; i <= n; ++i)
for(int l = k - 1; l < i; ++l)
dp[i][k] = min(dp[i][k], dp[l][k - 1] + cost[l + 1][i]);

return dp[n][K];
}
};

Share