Previous Contents Next

Module Linpartition

let list_sum = List.fold_left (fun x ® fun y ® x+y) 0

let rec part l1 l2 m k = (* Number of trenner in l2 *)
   let (s1int) = list_sum l1 
   in let (s2int) = list_sum l2
   in
   match l2 with
     [ ] ® m
   | x::l2' ® 
       let max1 = max (m+x) (linpart (km l2')
       in let max2 = max m (linpart (k-1) m l2)
       in (min max1 max2)

and linpart k m l2 =
   if k = 0 
   then ((m + (list_sum l2)))
   else (part [ ] l2 m k)

-------------------------------- linpart: input: k >0 l : list of integers

output: best k-partition of l, i.e. the partition with at most k subsequences, where the max. the sums of each partition is minimal. -------------------------------

recursive, non-efficient variant of




January 31, 2002
Previous Contents Next