下一个问题我很难解决。
我有一条直线，上面有m个村庄的名单。我需要在这些村庄中分配N个火车站，这样一个村庄与火车站的平均距离就可以最小化。
例子：
村庄：1、2、3、4、5、6、7---
我们有3个火车站。
试图使用动态编程，但做不到。有人能提出解决这个问题的方法吗？（除了尝试所有选择的明显方式之外）？
最佳答案
我想，对于每个村庄，你只关心从那个村庄到某个火车站的距离，而不是所有火车站的距离。所以，如果你能在每个村子里建一个火车站，即使村庄相距数千英里，“从一个村庄到火车站的平均距离”也将为零，这样，从一个村庄到另一个村庄的不同火车站的距离就会很大。
如果有一组村庄必须全部使用同一个火车站，则该火车站的最佳位置是村庄线路上的中间位置（如果村庄数量为奇数），或线路中间两个村庄之间的任何位置（如果村庄数量为偶数）。这是因为如果火车站在其他地方，向中间线移动会缩短到该组大多数村庄的距离，而只增加到少数村庄的距离。
因此，解决这一问题的一个简单方法是研究如何将m个村庄划分为n组相邻的村庄，每个村庄由一个火车站服务，位于中间村庄，或位于该组中两个最中心村庄之间的任何地方。
这是一个动态规划问题，你沿着村庄的路线工作，在k村计算将k个村庄分成j个组的最佳方法，以及最佳方法的成本你可以通过检查每个i，从最后i个村庄创建一个组的成本，并加上从第一个k-i村庄创建j-1组的成本来完成这项工作。
如果你真的是指每个村庄和每个火车站之间的平均距离，那么请注意，你可以一次处理一个火车站，因为一个火车站的位置不影响另一个火车站的定位成本。然后你会得到N个火车站，在中间带上相互重叠，或者沿着两个中心村庄之间的地带，如果有偶数个村庄的话——这真的没有意义。