Comment résoudre ce problème :
On nous donne N paires d'entiers. Pour chaque paire d'entiers, nous devons attribuer un entier à A et l'autre à B, de sorte que la différence entre la somme des entiers attribués à A et la somme des entiers attribués à B soit minimale.
Je ne peux pas penser à quelque chose de mieux que O(2^N).
J'ai pensé à la gourmandise mais elle ne donne pas toujours le résultat optimal.
Réponses
Trop de publicités?
Transformez le problème en ceci :
Étant donné : une séquence d'entiers non négatifs (la différence absolue entre les paires originales)
Problème : Partitionnez les entiers en deux ensembles de manière à minimiser la différence absolue des sommes des éléments de chaque sous-ensemble.
C'est le Problème de partition équilibrée qui est NP-complet. Les deux problèmes sont équivalents, c'est-à-dire que vous pouvez transformer le problème de la partition équilibrée en votre problème : associez, pour chaque élément n i de la séquence, la paire d'entiers (n i , 0). Ainsi, vous ne ferez pas mieux que O(2 N ).
Problème : attribuer un signe (plus/moins) à chaque entier de telle sorte que la valeur absolue de la somme de la séquence soit minimale.
~~
Je soupçonne * que si vous triez d'abord la séquence par ordre décroissant, alors un algorithme gourmand donnera des résultats optimaux. Il s'agira d'un algorithme O(N log N).
~~
( * ) Si je me trompe, veuillez fournir un contre-exemple.
Jonathan Paulson
Points
635
Soit les paires (A_0,B_0),...,(A_n,B_n). Soit D_i = |A_i-B_i|. Alors votre problème est équivalent à choisir des signes pour les D_i afin de minimiser la somme, ce qui est équivalent à trouver un sous-ensemble des D_i dont la somme est égale à la moitié de la somme totale, ce qui est équivalent à un sous-ensemble-somme, ce qui est NP-complet. Vous ne ferez donc pas mieux que 2^n.
Sauf que : si les nombres sont petits, vous pouvez essayer une approche de programmation dynamique : DP[i][n] est vrai si vous pouvez choisir un sous-ensemble dont la somme est égale à n en utilisant D_0, ,D_i. On commence avec DP[0][0] qui est vrai, puis DP[i+1][n] est vrai si DP[i][n] était vrai ou si DP[i][n-D[i+1]] est vrai. Cette solution est O(n*(la somme maximale possible))
