-3
$\begingroup$

I am new in writing recursive algorithm so I tried this problem from SPOJ but I could not formulate the recursive relation from where I can find the optimal solution. Can anyone help me to see the optimal solution of the problem below please.

There are N pilots working for his company (N is even) and N/2 plane crews needs to be made. A plane crew consists of two pilots - a captain and his assistant. A captain must be older than his assistant. Each pilot has a contract granting him two possible salaries - one as a captain and the other as an assistant. A captain's salary is larger than assistant's for the same pilot. However, it is possible that an assistant has larger salary than his captain. Write a program that will compute the minimal amount of money Charlie needs to give for the pilots' salaries if he decides to spend some time to make the optimal (i.e. the cheapest) arrangement of pilots in crews.

Input

The first line of input contains integer N, 2 ≤ N ≤ 10,000, N is even, the number of pilots working for the Charlie's company. The next N lines of input contain pilots' salaries. The lines are sorted by pilot's age, the salaries of the youngest pilot are given the first. Each of those N lines contains two integers separated by a space character, X i Y, 1 ≤ Y < X ≤ 100,000, a salary as a captain (X) and a salary as an assistant (Y).

Output

The first and only line of output should contain the minimal amount of money Charlie needs to give for the pilots' salaries.

Like

4

Person:1 Captain Salary =5 Assistant Salary=3

Person:2 Captain Salary =6 Assistant Salary=2

Person:3 Captain Salary =8 Assistant Salary=1

Person:4 Captain Salary =9 Assistant Salary=6

Here Ans would be 19.

we have to say Min how much money we have to pay to select 2 crews where all the N pilots are part of as Pilot or Assistant.

Can someone help me to solve in Polynomial Time please

$\endgroup$
  • 1
    $\begingroup$ 1. Sorry, I can't understand what you're asking. We expect questions to be self-contained. Please edit the question to provide all necessary information in the question, so people don't need to visit an external site. (External links can disappear; search works better if you have a full description of the problem in the question.) 2. What have you tried? Where did you get stuck? We expect you to make a serious effort before asking, tell us in the question what you tried. If you have a specific question about your attempts, that might be more suitable for this site. $\endgroup$ – D.W. Oct 5 '14 at 5:55
  • $\begingroup$ Note: there are $\prod\limits_{j=0}^{n/2-1} {n-2j \choose 2}$ ways to pick the pairs. $\endgroup$ – d'alar'cop Oct 5 '14 at 9:54
  • $\begingroup$ @d'alar'cop I know that,so u r asking me to make that many combination and find min out of them ?? $\endgroup$ – javaG Oct 5 '14 at 9:59
  • $\begingroup$ @javaG No, that's probably a bad way. Someone will come back with a good algorithm, don't worry. I might advise you to generalise the problem then put it on programmers.stackexchange $\endgroup$ – d'alar'cop Oct 5 '14 at 10:09
  • $\begingroup$ GENERAL VERSION: Take an array of objects $X$ where $|X| = 2z$ for some $z \in \mathbb{Z}$. Consider an object which is an orderer tuple $Y = \{a,b\}$ where $a=X[n] \land b=X[m] \land n>m$. Now consider a set $Z$ of objects $Y$ where $|Z|=|X|/2$ and $(j \in Z \cap k \in Z = \emptyset)$ for all $j,k$ where $j \neq k$. Now, consider a function $f(X[i]) = \begin{cases} v_1 &\mbox{if } \{a,X[i]\} \in Z\\ v_2 & \mbox{if } \{X[i],b\} \in Z \end{cases}$ Now, consider a function $g(Y) = Y.first + Y.second$ What is the best way to calculate $\min \sum\limits_{i=1}^{|Z|}g(Z_i)$? $\endgroup$ – d'alar'cop Oct 5 '14 at 10:35
5
$\begingroup$

This is an instance of the assignment problem. There are polynomial-time algorithms for the assignment problem, as described on Wikipedia. Put another way, your job is to find a minimum weight perfect matching in a bipartite graph. There are polynomial-time algorithms for that.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.