algorithm for minimisation of time given profit is maximised

i am confused here as to how can the profit be maximised and time be minimised at the same time.. now if the profit is maximised then first i sort the profits and select the company first that has maximum profit for 1st month and so on till nth month .. i know the profit will be maximised here..but for the same permutation i have no idea if the time will be minimum ...help me understand ..thanks .. i am learning algorithms and new to this ..

[William Rose]

@Malloju Dinesh,

Please explain what ideas you have to solve the problem, and show what you have tried so far to solve this problem. Then people will help you where something does not work as you expect. Thank you.

[Malloju Dinesh]

i am confused here as to how can the profit be maximised and time be minimised at the same time.. now if the profit is maximised then first i sort the profits and select the company first that has maximum profit for 1st month and so on till nth month .. i know the profit will be maximised here..but for the same permutation i have no idea if the time will be minimum ...help me understand ..thanks .. i am learning algorithms and new to this ..

[Malloju Dinesh]

i dont need the answer .. i just want to understand it .. so please help me understand my query ..thanks ... i think matlab involves algorithms as well ...

[Torsten]

For each ordering of the n companies, you'll get a total profit and a total oversee time after n months.

Now, from the n! possible orderings, you are asked to determine the ordering that gives maximum total profit, but (since there might be more than one ordering with maximum total profit) with the least total oversee time.

At least this is my interpretation of the assignment.

[Malloju Dinesh]

But for the maximum total profit , the time need not be minimum for those orderings .. so how can i unserstand this question?

[Torsten]

Read my comment again more carefully.

Say n = 3.

Say you get total profits and total oversee times as follows for the 6 possible orderings:

P1 = 200, T1 = 20

P2 = 150, T2 = 10

P3 = 70, T3 = 10

P4 = 180, T4 = 15

P5 = 200, T5 = 18

P6 = 190, T6 = 16

Now ordering 1 and 5 give maximum profit 200, but among these 2 possibilities, you choose ordering 5 because it has oversee time 18 < 20.

[Malloju Dinesh]

Thanks for explaining in detail .. highly appreciated ..

Answer 1

[William Rose]

@Malloju Dinesh,

YOu asked "how can the profit be maximised and time be minimised at the same time.. "

Good question. The problem says "LO wants to minimize time spent, given that total profit over n months is maximized." The phrase "given that" means (to me) that first requirement is to maximize total profit over n months, and the second requirement is to mimize the total time spent. The implication is that there may be more than one solution that maximizes the profit over n months. Among all the solutions that give the same maximum profit over n months, LO wants the solution that requires the minimum time spent.

There are n! possible orderings which LO could choose. I hope you can see that that is true. If n is small, you could just enumerate all the options and pick the one that A. maximizes total profits, and B. minimizes total time spent. But if n is large, n! will be very large. Therefore a better algorithm would be good to identify.

Each company generates a certain profit per month, which is the same for all months for that company. To maximize total profit, LO must buy the most profitable company first, so that they hold it for all n months. Then they buy the next most profitable company, and so on. Finally, LO buys the least profitable company in the final month. LO must do this in order to maximize total profit over n months. The second requirement kicks in if there are two companies that generate equal monthly profit. If there is a tie for monthly profits, LO should buy the company that requires less work first, so that they don't own it as long as the higher-workload, equal profit company.

How do you prove that the plan just described satisfies the requirements? I don't know. I leave that part to you. Maybe my plan is not even right. I think it is, but I could be wrong. You decide.

[Malloju Dinesh]

thanks a lot .. i understand the question a lot better now ...