La partition équilibrée

(a) Pour chaque élément $x$ du tableau, la somme $s$ est atteignable si elle l'était déjà avant de considérer $x$, ou si la somme $s-x$ était atteignable (en choisissant d'intégrer $x$). (b)

def partition_equilibree(t: list) -> tuple:
    S = sum(t)
    atteignable = [True] + [False] * (S // 2)
    temoin = [None] * (S // 2 + 1)  # Stocke l'élément ayant permis d'atteindre la somme s
    for x in t:
        # Parcours à rebours pour éviter de réutiliser le même élément plusieurs fois
        for s in range(S // 2, x - 1, -1):
            if not atteignable[s] and atteignable[s - x]:
                atteignable[s] = True
                temoin[s] = x
    
    # Trouver la plus grande somme atteignable inférieure ou égale à S/2
    meilleur = max(s for s in range(S // 2 + 1) if atteignable[s])
    
    # Reconstruction
    paquet, s = [], meilleur
    while s > 0:
        paquet.append(temoin[s])
        s -= temoin[s]
    return (paquet, meilleur, S - meilleur)

Pour $t=[5,8,13,4,6]$, la somme totale est $36$ (cible $=18$). L'algorithme renvoie le paquet [13, 5] (somme $18$) contre les éléments restants [8, 4, 6] (somme $18$), réalisant un équilibre parfait. (c) Complexité temporelle : $O(n\cdot S)$, mémoire : $O(S)$. La complexité est polynomiale par rapport à la valeur de $S$, mais exponentielle par rapport à son nombre de bits. C'est un algorithme pseudo-polynomial : très rapide pour des valeurs de sommes modérées, mais inefficace si les entiers contiennent un très grand nombre de chiffres.