作业:动态规划-寻找整数数组的最优子集分配

Question

我不确定这是不是问家庭作业问题的地方--如果不是，我很抱歉。坦率地说，我不想要答案，我只想要思考这个问题的方法。

假设我有一个n整数数组，它代表沿着直线轴线的村庄的位置。现在，我被允许建造k厕所，k是预先确定的，而n >= k是。我必须建造k厕所，使每个村庄和最近的厕所之间的总距离最小。

如何找到分配的最小可能值？

一个简单的例子：

村庄: 0，1，2，3，4，n = 5

厕所(最优)：2，如果k = 1从而使和= 6，如求和(x=0-2 x，x=1，2，x=2，2，2，2，2，2，2，2，2，2，2，2，2，2，2，2，2，2，2，2，2，2，2，2，4，2，2，2，4，2，2，4，2，2，2，4，2，2，2，2，2，2，2，2，2，2，2，2，2，2，2，2，2，2，2，2，2，2，2，2，2，4，2，4，2，4，2)的总和)。

厕所(最优)：1，3，如果k = 2从而使和=3，作为求和(x=0，1，x=1，x=2，2，2，2，2，2，3，4，3)

现在，我想到的一种方法是使用递归生成所有可能的配置。然后对每个厕所配置，计算最小距离，并选择最小距离。

如果k和n保持较小，它就能工作。但假设我有40个村庄和15个厕所要分配。这使得问题变得难以处理，因为它突然变成了一个大小为40 C 15或40225345056的问题。

我有一种感觉，它与动态规划有关，但我似乎不能将动态规划的概念转化为当前的问题。

再次重申，请不要把答案传给我，而是用不同的方法来构建这个问题。

Answer 1

顺便说一句，利用一些代数，我们可以发现，距离平均值的和可以计算出来，而不需要单独求和这些距离。一种方法是：

2 * [(num_smaller - 1) * sum_smaller + num_smaller * (sum_larger - (n-1) * average)]

where: n is the total number of elements
       num_smaller is the cardinality of {a | a <= average}
       num_larger is the cardinality of {b | b > average}
       sum_smaller is sum of {a | a <= average}
       sum_larger is the sum of {b | b > average}

Why: 
                   v = (a1 + a2 + a3 ... + b3 + b2 + b1) / n

                 n*v = (a1 + a2 + a3 ... + b3 + b2 + b1)

       n*v - (n-1)*v = (a1 + a2 + a3 ... + b3 + b2 + b1) - (n-1)*v

       n*v - n*v + v = (a1 + a2 + a3 ... + b3 + b2 + b1) - (n-1)*v

                   v = (a1 + a2 + a3 ... + b3 + b2 + b1) - (n-1)*v

现在我们正在寻找与平均值的绝对差额之和：

abs_sum_diffs = (v - a1) + (v - a2) + (v - a3) + ... + |v - b3| + |v - b2| + |v - b1|
  where a's are lower than or equal to v, and b's are greater than v         

让我们首先表达一下差异的总和：

      v - a1 = (     a2 + a3 ... + b3 + b2 + b1) - (n-1)*v
    + v - a2 = (a1      + a3 ... + b3 + b2 + b1) - (n-1)*v
    + v - a3 = (a1 + a2      ... + b3 + b2 + b1) - (n-1)*v
    ...
    + v - b1 = (a2 + a2 + a3 ... + b3 + b2     ) - (n-1)*v
    + v - b2 = (a1 + a2 + a3 ... + b3      + b1) - (n-1)*v
    + v - b3 = (a1 + a2 + a3 ...      + b2 + b1) - (n-1)*v
   _________________________________________________________
   sum_diffs = (n-1)*sum(a's)  +  (n-1)*sum(b's) - n*(n-1)*v // each a,b appears (n-1) times

             = (n-1) * (sum (a's + b's) - n * v)
             = (n-1) * (0)  // because sum(a's + b's) = n * v
             = 0

因此，元素与平均值(v - b)的负差异抵消了元素与平均值(v - a)的正差，这意味着它们的和是相等的。为了求差的绝对和，我们可以用相似的代数来找出正差的公式，

sum {v - a | a <= v}

把它乘以2，我把它当作练习。

让我们假设厕所的位置将被放置在每个k'th组元素的平均值上。为了避免重新计算子问题，我们可以为每一组i村庄构建一个矩阵，M[k][i]，从k = 1开始，代表将i村庄分组为k组的最佳方法。

让我们看看您的例子，[0, 1, 2, 3, 4]，在k = 1上为每个i

i = 0, M[1][0]                         = 0
i = 1, M[1][1] = 0.5 + 0.5             = 1
i = 2, M[1][2] = 1 + 0 + 1             = 2
i = 3, M[1][3] = 1.5 + 0.5 + 0.5 + 1.5 = 4
i = 4, M[1][4] = 2 + 1 + 0 + 1 + 2     = 6

现在，当我们计算k = 2时，我们可以依赖于矩阵的第一行。这一次，对于每个i，我们检查将这个村庄包含在不同的j-sized组中的选项，将k-1组的最佳成本添加到i-j村，我们在前面的步骤中计算了这一点：

i = 0;               M[2][0] = null  // we skip dividing one village into two groups

i = 1, j = 1;        M[2][1] = 0 + M[k-1][i-j] = 0 + M[1][0] = 0

i = 2, j = 1,2;      M[2][2] = min(0 + M[1][1] = 1
                                  ,1 + M[1][0] = 1)          = 1

i = 3, j = 1,2,3;    M[2][3] = min(0 + M[1][2] = 2
                                  ,1 + M[1][1] = 2
                                  ,2 + M[1][0] = 2)          = 2

i = 4, j = 1,2,3,4;  M[2][3] = min(0 + M[1][3] = 4
                                  ,1 + M[1][2] = 3
                                  ,2 + M[1][1] = 3
                                  ,4 + M[1][0] = 4)          = 3

该矩阵现在看起来如下：

[[x][x][x][x][x]
,[0][1][2][4][6]
,[x][0][1][2][3]]

对于较大的k和i，我们可以继续相同的过程。

Answer 2

我认为首先你需要找出一个基本的问题:当你有N个村庄，你必须建造一个厕所，在哪里建造它。

你的N应该从1开始。然后2，3.

接下来，你将在N个村庄中建造2个厕所。我认为很明显，你需要把村庄分成两组，分别使用两个厕所。

问题在于如何将村庄分成两组。在这种情况下，从1开始N，然后2，3.

让你的算法工作N(任何正整数)和2个厕所。

一旦你走到这一步，我想你可以继续上三个厕所。这个问题可能已经解决了。如果没有，我相信一旦你能在N个村庄中建造3个厕所，你就可以建造M (M <= N)厕所。

这里的基本方法是:从最简单的案例开始，然后逐步增加问题的复杂性，并确保您的解决方案能够处理增加的复杂性。递归听起来是个不错的方法。在真正成为问题之前，不要担心性能。先解决问题，然后再优化。

祝好运!