CODEWITHSUNDEEP
algorithmmathtime-complexitydiscrete-mathematics
Zoomba
Zoomba

Reputation: 1806

Maximizing profit in doing the jobs

We are given two arrays M (money) and E (experience) of integers each of size 50 at most. After Bob does the job i, two things happen:

(Let TE be Bob's total experience initialized by 0)

  1. Bob's experience (i.e. TE) is incremented by E[i]
  2. Then, he will receive money equal to TE*M[i]

What is the maximum profit Bob can make if he does the jobs in the best possible order?

For any i we know:
1 <= E[i] <= 10^5
1 <= M[i] <= 10    

Example:
M[] = { 20, 30,  100 }
E[] = {  1,  1, 6 }

Answer: 880 = job 3-1-2 = 6*100 + 7*20 + 8*30 = 980

Upvotes: 0

Views: 140

Answers (1)

shole
shole

Reputation: 4094

I think the problem can be solved by Greedy Algorithm (which is a special case of DP) as described follow:

  1. Sort the job by ratio Exp/Money in descending order
  2. If tie, then sort the job by Money in ascending order

Then the sorted job sequence is the order of the job which yields the optimal solution.

My reasoning is as follows: The ratio Exp/Money can be interpreted as How much Exp can you buy with 1 money, so it is always better if we choose the job with higher ratio first, as this increase the experience for later jobs.

In the tie case, choose the job with smaller money reward, as this makes the job with higher money reward can be multiplied by a larger experience factor later on.

For example: 

E = {2,1,6,1}
M = {40,20,100,10}

Sorted job = { job3, job4, job2, job1}  

= 6*100 + 7*10 + 8*20 + 10*40 = 1230

Upvotes: 1

Related Questions