Sunday, 18 August 2013

Reverse of greedy algorithm

Reverse of greedy algorithm

Suppose we have a set of DOUBLE values,lets say
[6-8],[8-9],[9-11.5],[9-11.5],[10.5-14],[12.5-14] And my task is to get
the maximum sum of these intervals. How do i do that? AND THERE SHOULD BE
NO OVERLAPPING. for e.g, if i take 6-8.5,i cant take 8-9 and vice versa.
in this very particular problem,if i take 6-8.5,9-11.5 and 12.5 to 14,i
get max sum as 6.5,which i wont get by any other combination. I think
reverse of greedy algorithm will do but i don't understand as to how to
implement that. I googled and found Kadane's algorithm
http://en.wikipedia.org/wiki/Maximum_subarray_problem but i didnt really
understand that how to implement that. Can anyone explain how do i
proceed?
I am a grad student and i need to implement this in my project. Thanks.

No comments:

Post a Comment