接收器-发射器网络的最小成本

Question

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

我们的任务是选择恰好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。

- user3697730

---

n可以有多大？暴力算法是一种选择吗？ - Dmitry Bychenko

没有对 n 的限制，它可以是一个非常大的数字。暴力破解肯定是一个选项，但我希望我们能够找到更快的方法。 - user3697730

Answer 1

一个时间复杂度为O(n^2)的动态规划解决方案非常直观。

设f(prefix_len, transmitters)为已处理了prefix_len个元素，前缀正确且发射器数量恰好比接收器多transmitters个的情况下所能获得的最优成本。

基本情况是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)（也就是说，我们使用了所有元素，发射器的数量等于接收器的数量）。

- kraskevich

Answer 2

这是一个有注释的、递归的 JavaScript 实现 kraskevich 大纲的代码：

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

- גלעד ברקן