algorithm - 作业 : Dynamic programming - Find optimal subset allocation for an array of integer

Question

我不确定这是不是问作业问题的地方 - 如果不是，我深表歉意。坦率地说，我不想要答案，只想要思考问题的方式。

假设我有一个 n 整数数组，它表示村庄沿直线轴的位置。现在，我可以 build k 个厕所，其中 k 是预先确定的并且 n >= k。我必须 build k 个厕所，以使每个村庄与最近的厕所之间的距离总和最小。

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

一个简单的例子:
村庄:[0, 1, 2, 3, 4], n = 5
厕所(最佳):[2]，如果 k = 1 则总和 = 6，如 Sum([|0-2|], [|1-2|], [|2- 2|], [|3-2|], [|4-2|])
Toilet(Optimal): [1, 3] if k = 2 因此总和 = 3，如 Sum([|0-1|], [|1-1|], [|2 -1|], [|3-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}

并将其乘以二，我将其留作练习。

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

让我们看看您的示例，[0, 1, 2, 3, 4]，对于每个 i，k = 1:

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 大小的组中的选项，为 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，我们可以继续相同的过程。