Will this work ?
Order by choosing the last element of the permutation first.
initially Calculate T = Total time of all tasks
and calculate for all i, (T-Ti)*Ci and choose the task with min among them
as last.
To find the next last element , re-calculate T = T-Ti(i being the element
chosen in
can you give the problem link ?
On Thu, Jun 9, 2011 at 12:38 PM, Algoose chase harishp...@gmail.com wrote:
Will this work ?
Order by choosing the last element of the permutation first.
initially Calculate T = Total time of all tasks
and calculate for all i, (T-Ti)*Ci and choose the task
ya aanchal, kaun si problem hai?
On Sun, Jun 12, 2011 at 1:41 AM, Arpit Sood soodfi...@gmail.com wrote:
can you give the problem link ?
On Thu, Jun 9, 2011 at 12:38 PM, Algoose chase harishp...@gmail.comwrote:
Will this work ?
Order by choosing the last element of the permutation first.
sort the jobs increasingly according to ratio: duration/penalty.
It is easy to prove it's optimal for two jobs.
Then you generalize the proof for n jobs easily because you can swap
two consecutive jobs i,j that have duration(i)/penalty(i)duration(j)/
penalty(j) to decrease the total penalty of
Yes, pshaus is absolutely right. I have just confirmed it by exchange
arguments. Just schedule the one first having (duration/panelty) ratio
lesser.
On Wed, Jun 8, 2011 at 12:01 AM, pschaus psch...@gmail.com wrote:
sort the jobs increasingly according to ratio: duration/penalty.
It is easy to
@Aakash Johari:
Sorting works fine if all jobs can be completed in a day..
I have a modification to this question -
suppose the time to do a job is not one day and is given as Ti for job
i, then how should one solve it?
On Jun 7, 11:58 am, Aakash Johari aakashj@gmail.com wrote:
yes, it's
