CODEWITHSUNDEEP
algorithm
user3697730
user3697730

Reputation: 251

Minimum cost of receiver-transmitter network

Let us assume that we have n devices, n even number . Each device can work either as a transmitter (T) or as a receiver (R). For every device i, we are given 2 numbers, Ti and Ri. Ti is the cost in case the device works as transmitter and Ri the cost in case it works as a receiver . We also know that Ti>=Ri for every i.

Our task is to choose exactly n/2 transmitters and n/2 receivers , in a way that we achieve minimum cost. (the final answer is the minimum cost only)

Additional restriction: Transmiters transmit always from left to right . That means that we can have sequence TTTRRR, TTRTRR, TRTRTR, etc but not RTTTRR. We can never encounter more receivers than transmitters at any point.

Which is the most suitable algorithm for this task?

Example : we have 4 devices . T1=9 ,R1=6 , T2=6 ,R2=2 ,T3=8 ,R3=1 ,T4=5 ,R4=3

Optimal solution : TTRR, cost 19.

So final answer is 19.

Upvotes: 3

Views: 156

Answers (2)

גלעד ברקן
גלעד ברקן

Reputation: 23945

Here's a commented, recursive JavaScript implementation of kraskevich's outline:

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

Upvotes: 0

kraskevich
kraskevich

Reputation: 18566

An O(n^2) dynamic programming solution is pretty straightforward.

Let f(prefix_len, transmitters) be the optimal cost one can obtain in such a way that prefix_len elements have already been processed, the prefix is correct and the number of transmitters is exactly transmitters more than the number of receivers (that is, it's a "balance" in some sense).

The base case is f(0, 0) = 0 (an empty prefix is free). The transitions are as follows f(prefix_len, transmitters) + T[i] -> f(prefix_len, transmitters + 1) (we make the current element a transmitter). If transmitters > 0, there's also a transition f(prefix_len, transmitters) + R[i] -> f(prefix_len + 1, transmitters - 1) (we make it a receiver).

The answer is f(n, 0) (that is, we used all the elements and the number of transmitters is equal to the number of recievers).

Upvotes: 1

Related Questions