c++ - 如何在无限轴上找到N个点，使得M个点到它最近的N个点的距离之和最小？

Question

假设在一条路上有 N 栋房子。我有M个灯杆。鉴于 M < N。所有相邻房屋之间的距离都不同。灯杆只能放在房子里。而且我必须将所有灯杆放在房子里，以便从每个房子到最近的灯杆的距离总和最小。我该如何编码这个问题？

经过一些研究，我开始知道我必须使用动态规划来解决这个问题。但我不知道如何解决这个问题。

Answer 1

这是一个搜索空间为 O(n^2 * m) 的朴素动态程序。也许其他人知道另一个加速？从代码中的函数f应该可以清楚地看到递归。

JavaScript 代码:

// We can calculate these in O(1)
// by using our prefixes (ps) and
// the formula for a subarray, (j, i),
// reaching for a pole at i:
//
// ps[i] - ps[j-1] - (A[i] - A[j-1]) * j
//
// Examples:
// A:  [1,2,5,10]
// ps: [0,1,7,22]
// (2, 3) =>
//   22 - 1 - (10 - 2) * 2
//   = 5
//   = 10-5
// (1, 3) =>
//   22 - 0 - (10 - 1) * 1
//   = 13
//   = 10-5 + 10-2
function sumParts(A, j, i, isAssigned){
  let result = 0
  for (let k=j; k<=i; k++){
    if (isAssigned)
      result += Math.min(A[k] - A[j], A[i] - A[k])
    else
      result += A[k] - A[j]
  }
  return result
}

function f(A, ps, i, m, isAssigned){
  if (m == 1 && isAssigned)
    return ps[i]
    
  const start = m - (isAssigned ? 2 : 1)
  const _m = m - (isAssigned ? 1 : 0)
  let result = Infinity
    
  for (let j=start; j<i; j++)
    result = Math.min(
      result,
      sumParts(A, j, i, isAssigned)
        + f(A, ps, j, _m, true)
    )
  
  return result
}

var A = [1, 2, 5, 10]
var m = 2

var ps = [0]
for (let i=1; i<A.length; i++)
  ps[i] = ps[i-1] + (A[i] - A[i-1]) * i

var result = Math.min(
  f(A, ps, A.length - 1, m, true),
  f(A, ps, A.length - 1, m, false))

console.log(`A:  ${ JSON.stringify(A) }`)
console.log(`ps: ${ JSON.stringify(ps) }`)
console.log(`m:  ${ m }`)
console.log(`Result: ${ result }`)