Gegeven een lijst met een even aantal natuurlijke getallen, groepeer deze getallen dan als koppels (a1, b1), (a2, b2), ..., (an, bn) zodat de som van het kleinste element uit elk koppel maximaal is.
Schrijf een functie lijst_verdelen(getallen) die gegeven een lijst met (niet gesorteerde) getallen deze maximale som retourneert.
Bestudeer grondig onderstaande voorbeelden.
>>> lijst_verdelen([1, 4, 3, 2])
4
Er zijn verschillende mogelijkheden om deze lijst te verdelen:
(1, 4) en (3, 2), waarbij de som van alle minima gelijk is aan 3;(1, 3) en (4, 2), waarbij de som van alle minima gelijk is aan 3;(1, 2) en (4, 3), waarbij de som van alle minima gelijk is aan 4. Dit is de beste oplossing.>>> lijst_verdelen([6, 2, 6, 5, 1, 2])
9
Je kan de lijst immers als volgt verdelen: (1, 2), (2, 5) en (6, 6). Dan is de som van alle minima gelijk aan 9.
Tip
Indien je de lijst eerst sorteert, wordt het werk een pak eenvoudiger…