算法动态规划

货仓选址与安排邮筒

字数统计: 2k字   |   阅读时长: 8分
, , ,

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

【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：潮汐朝夕
我的知乎：潮汐朝夕
我的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