最小成本的收发网络

Question

假设我们有n设备，n偶数。每个设备都可以作为发射机(T)或接收器(R)工作。对于每一个设备i，我们都有两个数字，Ti和Ri。Ti是设备作为发射机工作时的成本，Ri是作为接收器工作的成本。我们还知道，Ti>=Ri对于每一个i。

我们的任务是选择准确的n/2发射机和n/2接收机，以达到最低的成本。(最后的答案是最低成本)

附加限制:传送者总是从左向右发送。这意味着我们可以有序列TTTRRR，TTRTRR，TRTRTR等，而不是RTTTRR。在任何时候，我们都不会遇到比发射机更多的接收器。

哪一种算法最适合这个任务？

例:我们有4个设备。T1=9，R1=6，T2=6，R2=2，T3=8，R3=1，T4=5，R4=3

• 可能的解决方案1：TTRR总成本: 9+6+1+3 =19
• 可能的解决方案2：TRTR总成本: 9+2+8+3 =22

最优解：TTRR，成本19。

最后的答案是19。

Answer 1

O(n^2)动态规划解决方案非常简单。

假设f(prefix_len, transmitters)是人们可以获得的最优成本，prefix_len元素已经被处理过，前缀是正确的，发送者的数量恰好比接收者的数量多(也就是说，在某种意义上是“平衡”)。

基本情况是f(0, 0) = 0 (空前缀是免费的)。这些转换如下所示：f(prefix_len, transmitters) + T[i] -> f(prefix_len, transmitters + 1) (我们将当前元素作为发射机)。如果是transmitters > 0，也有一个转换f(prefix_len, transmitters) + R[i] -> f(prefix_len + 1, transmitters - 1) (我们把它变成接收器)。

答案是f(n, 0) (也就是说，我们使用了所有的元素，发射器的数量等于接收者的数量)。

Answer 2

下面是kraskevich的大纲的一个注释的递归JavaScript实现：

var ts = [9,6,8,5],
    rs = [6,2,1,3],
    n = ts.length;

// returns cost from index i forward, with t more transmitters than receivers
function f(i,t){
  // last one must be a receiver
  if (i === n - 1) return rs[n-1];

  return Math.min(
    // avoid having more transmitters than we can receive
    t + 1 <= (n - i + 1) >> 1 ? ts[i] + f(i + 1,t + 1) : Infinity,

    // don't encounter more receivers than transmitters
    t > 0 ? rs[i] + f(i + 1,t - 1) : Infinity
  );
}

console.log(f(0,0)); // 19