问题的正式表述如下:给定直线上的 N 个点,并且序列是非n1, n2, n3 ...递减的。排列 M 个点,使得从最近点ni, n (i + 1) ...到该点的距离之和对于mi最小i = 1 ... M。
问题的非正式解释:在路上安排M个加油站,让住在路边的N个人花尽可能少的时间到达加油站。对于一个加油站来说,条件很简单:加油站左右的人数必须相同。
M<=N
随着加油站数量的增加,任务变得更加复杂。我举了一个在 10 个点中放置 3 个加油站的例子。他们每个人都创建了一个段,并且在加油站左右的这个段上的人数相同。
但是,这不是最佳解决方案。我的假设:为了达到最优,需要一个额外的条件:在右边和左边,这个加油站最近的点数必须相同。下图显示了这种布置的一个示例,实际上,这种情况下的距离总和更小。
问题是我不明白如何在加油站安排阶段检查哪个点最近。这可以在第一张图片中看到:我们将点排列成两边的人数相同,但排列后发现离他们最近的加油站并不是我们预期的加油站。
