Problème — Partager équitablement

Problème — Partager équitablement.

Deux héritiers se partagent des objets de valeurs entières données par une liste v. On veut savoir s'il est possible de former deux lots de même valeur totale.

• Répondre à la main pour [2, 4, 7], [1, 5, 11, 5] et [3, 1, 5, 9, 12].
• Ramener la question à celle-ci : existe-t-il une partie des objets de valeur totale exactement $T/2$, où $T$ est la somme des valeurs ? On note possible[s] le booléen « on peut atteindre exactement la somme $s$ avec les objets déjà traités ». Écrire une fonction partage_equitable(v) qui met à jour ce tableau objet par objet.
• Quel est son coût ? Pourquoi essayer toutes les parties serait-il bien plus coûteux ?