[algogeeks] Re: Problem

Tue, 04 Apr 2006 05:12:00 -0700

Well,
       we can solve it using Dynamic Programming.
 
I am giving the gist of my logic.
 
Lets call x,y and z as split points
 
1. Find the cost of x, for all positions in 1..n-3 and store it
2. For each postion in 2..n-2(Y) find the x such that cost is minimum and store it
3. For each Position in 3..n-1(Z) find the y such that cost is minimum and store it.
 
Now for each Z we can find the cost and minimum gives us the answers.
 
PS: I consider this as a variation of this problem. We are having a lift in a building and there are k persons in the lift and the building has n floors. The lift can utmost stop at the m floors. We have to minimize the total number of floors the persons has to walk.
 
regards
Arunacahalam.
 
 

 
On 4/4/06, learner <[EMAIL PROTECTED]> wrote:

Known array: a[max]; divide a[] into four sections: a[0] - a[x], a[x+1]
- a[y], a[y+1] - a[z], a[z+1] - a[max-1].


And 0<x<y<z<max-1;


a[] is an integer greater than 0;


Solve integers x, y and z, to meet the following requirements:
Sum  = (a[0  ]+ ... +a[x]  )* x
    +  (a[x+1]+ ... +a[y]  )* y
    +  (a[y+1]+ ... +a[z]  )* z
    +  (a[z+1]+ ... +a[max-1])*(max)
choosing x, y, z such that the value of sum is the least.



http"//ww.livejournal.com/users/arunachalam
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---

Reply via email to