Algorithmie [Résolu]

Je vais réfléchir à ton problème, mais je ne connais pas d'emblée de solution...
J'ai essayé de formaliser ton problème, dis moi si jamais il y avait une erreur :

On a n couples (a1,b1) (a2,b2) ... (an,bn) avec pour tout i : ai>0 bi<0
Et on cherche les ci (avec ci=ai ou bi) tels que s=somme(ci,i=1..n) soit positif et minimal

Bonjour, je vais te l'avouer je ne comprends pas ton problème... tu dis que tu as fait -1+-1+7 mais pourquoi?
la somme minimale positive aurait été -1+1+2 non?
ici j'ai pris a1+b1+a2
si j'ai faux, dis le moi parce que là je n'ai pas pigé ton problème. N'hésite pas à redire quoi. (ps si tu dis vrai, que c'est de complexité 2^n, alors avec 3 couples tu as 8 sommes possibles et non 6)

Je pense que cela doit se résoudre en utilisant les écarts a-b de chaque couple. En traitant les couples dans l'ordre de celui ayant le plus grand écart vers le plus petit. Et de voir si on peut "compenser" le nombre avec ce qu'il reste. Cela me paraît être une bonne méthode mais je n'ai pas testé beaucoup de cas pour l'affirmer.

Pour reprendre mon exemple de tout à l'heure ça ferait commencer par
7 qu'on pourrait compenser au max par -2
ou alors -12 qu'on pourrait compenser au max par +3

On élimine ainsi directement "l'étude" avec le -12 car la somme finale serait forcément négative.

Vous y voyez un problème à cette proposition d'algo ? Ou en voyez-vous un plus efficace encore ?

Je ne sais pas trop ce que ça vaut mais regarde ce que ça peut te donner si tu choisis à chaque fois celui dont la valeur absolue est la plus faible, en repérant bien lequel tu as choisis.

Puis à la fin si ton résultat est positif je dirais que c'est forcément le résultat attendu (à démontrer)
Et si ton résultat est négatif, il faut que tu affines en cherchant parmi les valeurs négatives que tu as prises lesquelles pourrais tu exclure (c'est à dire choisir le positif à la place) pour compenser ta somme et qu'elle devienne positive

Moi je propose un truc qui pourait peut être marcher :
tu pars de la somme de tous les a
(1, -1)
(2, -1)
(7, -12)
1+2+7=10
puis tu enlèves le plus grand a pour mettre le b qui lui correspond
1+2-12=-9
comme c'est pas bon, on laisse le plus grand a, maintenant on va remplacer le a intermédiaire
1-1+7=7 tiens on a une somme positive plus petite que la somme de tous les a...
essayons de remplacer le plus petite a par son b
-1-1+7=5, c'est encore plus petit...
et on tombe sur le bon résultat

je prends des autres couples
(10;-3)
(3;-1)
(5;-2)
10+3+5=18
remplacement du 10
-3+3+5=5... ha...
remplacement du 5
-3+3-2=-2... on garde le 5
remplacement du 3
-3-1+5=1... on peut pas mieux de toutes façon... apparement ça marcherait... j'écris donc un niveau général de l'algorithme :

1) ranger les couples dans l'ordre décroissant des a
2)faire la somme des a qu'on appellera S
3)maintenant les remplacements

==>tant que i<n (i est l'indice des tableau et n la taille du tableau)
           ==>S prend une nouvelle valeur : on lui enlève la valeur de a[i] et on lui ajoute b[i]
                 ==>si S<0 alors on enlève b[i] et on ajoute a[i]
                        fin si
          fin tant que

je sais pas si c'est vraiment bon mais c'est une piste selon moi

J'essaye de voir comment marche ton algorithme dans le cas général
Mais j'ai des difficultés à l'étape 2...

n=4

(a1,b1)
(a2,b2)
(a3,b3)
(a4,b4)

Étape 1 : élimination éventuelle a1/b1
(2 opérations)

a1+b2+b3+b4<0 donc on garde
b1+a2+a3+a4>0 donc on garde

Étape 2 : élimination éventuelle (a1+a2)/(a1+b2)/(b1+a2)/(b1+b2)
(4 opérations)

Commençant par a1 :
(a1+a2)+b3+b4<0 donc on garde
(a1+b2)+a3+a4>0 donc on garde // problème ici

Commençant par b1
(b1+a2)+b3+b4<0 donc on garde // et ici
(b1+b2)+a3+a4>0 donc on garde

Dans la mesure où on mélange les a et les b comment choisir si on les garde quand ils sont <0 ou >0 ?

Le problème avec les complexités c'est qu'il faut toujours se placer dans le pire cas.
Quand tu dis que les 4 opérations pourrait n'être que 2, je suis d'accord, mais au pire cas il y en a 4...
Et donc au pire cas tu arrive à O(2^n), bien sûr tu n'atteindras jamais 2^n mais pour des n grands tu auras quand même une complexité exponentielle !

J'ai uneidée d'algorithme en O(n.log n) même s'il ne marche pas tel quel...
Tu tris tes couples comme le proposait artragis (c'est là qu'on a le n.log n)

Tu prends un "couple-somme" que tu initialise en faisant le calcul sur les deux premiers couples...
Puis pour chaque couple suivant tu fais le calcul suivant entre le couple somme et le couple regardé

exemple :

(6; -2)
(5; -9)
(7; -8)
(15; -11)

(6,-2) et (5,-9) => on prends 5 et -2 on obtient un couple-somme (6+5,-2-9)=(11,-11)
(11,-11) et (7,-8) => on prends 7 on obtient un couple-somme (11+7,-11-8)=(18,-19)
(18,-19) et (15,-11) => on prends -11 on obtient un couple-somme (18+15,-19-11)=(33,-30)

Et là j'obtiens 5 / -2 / 7 / -11, alors je sais que c'est pas positif, mais en changeant la façon de faire le tri ou la façon de calculer le couple-somme... y a peut-être moyen de le faire en O(n.log n)

(6,-2) et (5,-9) => on prends 5 et -2 car 5-2>0 alors que 6-9 non
(11,-11) et (7,-8) => on prends -8 car 11-8>0 alors que 7-11 (autant pour moi je me suis trompé)
(18,-19) et (15,-11) => on prends -11 car 18-11>0 alors que 15-19 non...

En fait c'est la façon de calculer la couple-somme qu'il faut changer, en ne prenant que ceux qu'on a séléctionné avant ça ferait

(6,-2) et (5,-9) => on prends 5 et -2 d'où (5,-2)
(5,-2) et (7,-8) => on prends 7 d'où (12,-2)
(12,-2) et (15,-11) => le problème c'est que 15-2 et 12-11 sont tous deux positifs...

Je vais travailler l'idée... je vais peut-être trouvé (l'ordre du tri doit jouer aussi...)

Pour un exemple pas mal à tester :
(100; -1)
(1; -50)
(12; -3)
(10; -60)

La somme min est 100-60-50+12=2 (et non -1+1-3+10=7).
Il élimine toutes mes idées d'algo à tendance abusive de "recherche de minimum".

Je vais partir du problème initial et avec quelques transformations le transformer en un autre problème qui doit avoir déjà été résolu...

on a (a1,b1), (a2,b2)... (an,bn)
soit S=a1+a2+...+an
et c1=a1-b1, c2=a2-b2, ... cn=an-bn

Rechercher pour chaque couple (ai,bi) lequel de ai ou bi choisir, ça revient à chercher une somme de ci (avec chaque ci pris 0 ou 1 fois) tel que cette somme se rapproche de S
Si on utilise c1 alors c'est qu'on a pris b1 et non a1, idem pour c2.. cn
Le résultat final sera alors la différence entre S et la somme des ci

Exemple : (100,-1)=>101 / (1,-50)=>51 / (12,-3)=>15 / (10,-60)=>70 / S=123
On cherche à obtenir 123 en sommant 101,51,15 et 70
Par exemple en faisant 51+70=121
Donc on a pris 100, -50, 12, -60 (ce que tu trouvais précédemment)
Et le résultat obtenu est 123-121=2 !

Il reste "plus qu'à" trouver un algorithme qui permette de trouver une telle somme de ci, mais ça ressemble un peu à la partie chiffre du jeu "Des chiffres et des lettres" et c'est pourquoi je pense que l'algorithme doit déjà exister...

Waouh ! En cherchant à optimiser mon code je me suis aperçu d'une chose.
En fait j'étais trop dans la vision "arbre de recherche de solution" mais je me suis rendu compte (du fait des coupures systématiques) que c'est super simple, seulement fallait y penser ^^.

En considérant les couples (pi; ni) (p de positif et n de négatif)
Au début je faisais dans mon arbre p0+somme(ni) et n0+somme(pi) (car p0+somme(pi) et n0+somme(ni) étaient obligatoirement éliminés du fait du tri initial).
Mais en construisant mon arbre je ne fais rien d'autre que chercher quel p_i (ou n_i) compense "trop".

C'est tellement simple que même à la main ça le devient :)
Par exemple :
Avec
(15; -11) /26
(7; -8) /15
(5; -9) /14
(1; -2) /3
(1; -1) /2

Je fais p0+n1+n2+n3+n4 = -5
C'est donc trop compensé de 5, donc je regarde les écarts pour avoir la plus petite somme supérieure ou égale à 5 => 2+3, des couples 4 et 5, donc je change mon choix pour 4 et pour 5.
Ce qui me fait p0+n1+n2+p3+p4 = 0

Je fais de même en partant de n0
n0+p1+p2+p3+p4 = 3
C'est trop compensé de 3, donc je regarde les écarts pour avoir la plus grande somme inférieure ou égale à 3 => 3, du couple 3, donc je change mon choix pour 3
Ce qui me fait n0+p1+p2+n3+p4 = 0 aussi.

Pour un autre exemple où il n'y a qu'une solution :
(100; -1) /101
(10; -60) /70
(1; -50) /51
(12; -3) /15

p0+n1+n2+n3 = 100-113 = -13, je change donc de choix pour le 3 (puisque 15 est le minimum >= 13)
p0+n1+n2+p3 = -13+15 = 2

Je regarde en partant de n0
n0+p1+p2+p3 = -1+23 = 22, je change donc de choix pour le 3 aussi (puisque 15 est le max <= 22)
n0+p1+p2+n3 = 22-15 = 7

2<7 donc c'est p0+n1+n2+p3 la somme minimale :)
Je ne sais pas la complexité de cette méthode mais je ne pense pas qu'on puisse trouver mieux :)

edit : bon, avec un nombre important de couples il faut également faire un autre petit algo pour trouver la "meilleure" somme selon le cas en fonction des écarts.