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 (s1: int) = list_sum l1
in let (s2: int) = list_sum l2
in
match l2 with
[ ] ® m
| x::l2' ®
let max1 = max (m+x) (linpart (k) m 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
Pages last (re-)generated October 28, 2002 (Martin Steffen)