我有我有一个很难解决的下一个问题。
我有一条直线，并在其上中号村庄的名单。 我需要分配的N个车站这些村庄，使得从一个火车站一个村庄的平均距离，将被最小化。 例：
村庄----- 1 -------------- 2-3 --------- ----------- 4-5 -6 ---------- 7 ---和我们有3个车站。
试图用动态规划，但不能这样做。 任何人都可以提出一个方法来SOLV这个问题？ （除了尝试所有选项的明显的方式）？
Answer 1:
我认为，对于每一个村，你只关心从村到一个特定的火车站，并不是所有车站的距离。 所以，如果你可以把一个火车站在每个村的“平均距离从村到火车站”将为零，即使村是相差十万八千里，这样从一个村到不同火车站的距离不同的村子就很大。
如果你有一组村庄必须全部使用相同的火车站那么该火车站的最佳位置是在村庄的线中间位置（如果村庄的数量为奇数），或在中间的两个村庄之间的任何地方线（若村的数量是偶数）。 这是因为如果火车站是其他地方，移动它朝向中心将缩短到广大组中的村庄的距离，同时增加只有少数的距离。
因此，一个简单的方法解决这个问题是要解决如何将M个村划分为连续村庄N个组，每个组由一个火车站，放置在正中村或组中的两个最中心村之间的任何地方。
这是一个动态规划问题，你在村沿村，计算的工作线k到划分那些ķ村达成J个组的最佳方式，并认为最好的办法成本。 您可以通过检查做到这一点，对于每一个我，从上次我村创建组，添加来自前k创建J-1组的成本为代价的 - 我的村庄。
如果你真的是每一座火车站之间的平均距离，然后注意，您可以只处理火车站一次一个，因为一个火车站的位置不影响定位的另一个火车站的成本。 然后你得到N个车站建在彼此的顶部在中间，或沿着两个中心村之间的长条放入，如果有偶数个村庄 - 这并没有真正意义。
文章来源: Algorithm : allocation of N railway stations in a M villages which are on a straight line
