1. for a given SUM, if we can partition S in to l ranges whose each sum
<= SUM such that l < k, we can adjust them into k ranges since si >= 0.
2. for a given SUM, if we can partition S in to k ranges, for all SUM1
> SUM we can find a k partition such that the sum of each ranges will not be
> larger than SUM1
So we can use binary search for SUM, determin if SUM is valid by greedy
algorithm whose complexity is in O(n),
the total complexity will be O( n * log (maxSUM) ).
On 11月12日, 下午1时04分, "[EMAIL PROTECTED]"
<[EMAIL PROTECTED]> wrote:
> Can someone please give me a algorithm/pseudo code for the following
> problem?
>
> Given an arrangement S of non-negative numbers {s1,s2,s3....sn} and an
> integer k.
> Partition S into k ranges, so as to minimize the maximum sum over all
> the ranges.
>
> e.g Optimally S={1,2,3,4,5,6,7,8,9} partitioned into k=3 ranges will be
> {1,2,3,4,5}, {6,7}, {8,9}
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups-beta.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
