Bonjour.
Je dois résoudre un problème algorithmique. Pour ce problème, je pense avoir trouvé un algorithme mais je ne sait pas si il est valide. J'aimerais savoir si il l'est ou si il existe une solution plus simple.
Enoncé
Etant donné une liste L de N entiers strictement positif. Etant donné K un entier strictement inferieur à N.
Trouver une partition de L en K sous liste tel que la plus grande somme de toute les sous liste soit minimal (Si plusieurs partitions sont possibles, en renvoyer une).
Exemples
Exemple 1:
L = [ 10, 5, 4, 2 ]
K = 2
Résultat:
sous liste 1: [10] (sum = 10)
sous liste 2: [5, 4, 2] (sum = 11)
maximum somme des sous listes = 11
Exemple 2:
L = [100, 50, 61, 22, 22, 1]
K = 3
sous liste 1: [100] (sum = 100)
sous liste 2: [61] (sum = 61)
third sub list = [22, 22, 1] (sum = 45)
maximum somme des sous listes = 100
(Dans ce cas, plusieurs partitions sont possibles, par exemple: [100], [61, 22, 1], [22] est aussi une partition possible car la aussi, la plus grande somme des sous liste est 100).
Algorithme
On définit une classe SubList:
attribut:
sum = 0
list = []
methode:
add(integer):
add integer to list
increment sum: sum += integer
Algorithime:
Trier L du plus grand au plus petit
Créer la liste des K SubList: sublist_list = [ S0, S1, S2, ...] (cette liste sera toujours triée: la premiere sous liste est celle avec la somme la plus petite, la dernière est celle avec la somme la plus grande)
Pour chaque element de L: (on commence par le plus grand et on termine par le plus petit)
s = prendre premiere sous liste de sublist_list (celle avec la pus petite sum donc)
s.add(integer)
replacer s pour que sublist_list reste triée (binary search pour replacer la sous liste)
complexité: O( N log(N) )
Mon problème sur cette algo
Je n'ai pas trouvé de contre exemple à cette algorithme (une entré qui donne un résultat ne vérifiant la propriété).
Mais je n'ai pas non plus réussis à démontrer qu'il est valide.
Est il valide ? Si oui comment le prouver ?
(si il existe un algorithme plus simple, ou l'on peux démontrer qu'il renvoie le bon résultat, je suis preneur).
Tentative de démonstration
Voici ce j'ai tenté pour démontrer que l'algorithme est valide (je n'ai pas réussis):
Natation (K fixé):
A: l'algorithme ci dessus.
L = [x1, x2, ..., xN] (déjà trié: x1 >= x2 >= x3 >= ... >= xN))
L_i: la liste ne prenant que les i premier entiers = [x1, x2, ..., xi]
A(L_i): le résultat de A avec L_i comme liste (K est fixé)
Pb_i: la meilleur partition de L_i
P_i: une partition de L_i
P_i_0 < P_i_1 signifie: la plus grande somme des sous liste de P_i_0 est plus petite que la plus grande somme des sous liste P_i_1 (cela veux dire que P_i_0 n'est pas la meilleur partition)
Par récurrence:
H_i: A(L_i) = Pb_i
H_1 est vrai
En supposant H-i, il faut montrer que H_i+1 est vrai.
Supposons que H_i+1 soit faux (raisonnement par l'absurde).
Alors:
Pb_i+1 < A(L_i+1)
Si j'enleve x_i+1 de Pb_i+1 et A(L_i+1):
- en enlevant x_i+1 de A(L_i+1) on obtient A(L_i) (par construction de l'algorithme A). D'après H_i: A(L_i) = Pb_i
- on note Pb_i+1 moins x_i+1: rem(Pb_i+1, x_i+1)
on sait que:
rem(Pb_i+1, x_i+1) <= Pb_i
On sait que: Pb_i+1 < A(L_i+1)
On sait (d'après l'algorithme A) que A(L_i+1) est obtenue en plaçant x_i+1 sur la sous liste avec la plus petite somme
on sait que x_i+1 est plus petit que tout les autres x (x_i+1 <= x_j pour tout j entre 1 et i+1)
--> Montrer contradiction (la je n'ai pas réussis).
-----