algorithm - 接收器-发送器网络的最低​​成本

Question

假设我们有 n 台设备，n 为偶数。每个设备都可以作为发射器 (T) 或接收器 (R)。对于每个设备 i，我们都给定了 2 个数字，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)(也就是说，我们使用了所有的元素并且发射器的数量等于接收器的数量)。