Algorithmie
Résolu/Fermé
bizu53
Messages postés
1274
Date d'inscription
samedi 30 août 2008
Statut
Membre
Dernière intervention
21 juin 2015
-
2 janv. 2009 à 17:08
bizu53 Messages postés 1274 Date d'inscription samedi 30 août 2008 Statut Membre Dernière intervention 21 juin 2015 - 4 janv. 2009 à 13:21
bizu53 Messages postés 1274 Date d'inscription samedi 30 août 2008 Statut Membre Dernière intervention 21 juin 2015 - 4 janv. 2009 à 13:21
12 réponses
KX
Messages postés
16752
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
31 août 2024
3 019
2 janv. 2009 à 18:28
2 janv. 2009 à 18:28
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
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
artragis
Messages postés
481
Date d'inscription
mardi 12 juin 2007
Statut
Membre
Dernière intervention
6 avril 2010
146
2 janv. 2009 à 18:43
2 janv. 2009 à 18:43
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)
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)
KX
Messages postés
16752
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
31 août 2024
3 019
2 janv. 2009 à 19:29
2 janv. 2009 à 19:29
Je crois qu'en fait les sommes dont il parle sont :
a1+a2+a3 = 1+2+ 7 = 10 a1+a2+b3 = 1+2-12 = -9 a1+b2+a3 = 1-1+ 7 = 7 a1+b2+b3 = 1-1-12 = -1 b1+a2+a3 = -1+2+ 7 = 8 b1+a2+b3 = -1+2-12 =-11 b1+b2+a3 = -1-1+ 7 = 5 b1+b2+b3 = -1-1-12 = -3Mais effectivement ça fait bien 8 sommes possibles et non 6
bizu53
Messages postés
1274
Date d'inscription
samedi 30 août 2008
Statut
Membre
Dernière intervention
21 juin 2015
860
2 janv. 2009 à 19:30
2 janv. 2009 à 19:30
Au temps pour moi c'est 8 :p je ne sais pas pourquoi j'ai écrit 6 ^^
Pour mon truc je choisis pour chaque couple a ou b.
Si on considère :
(a1, b1)
(a2, b2)
(a3, b3)
Les sommes possibles avec ces 3 couples sont donc
a1+a2+a3
a1+a2+b3
a1+b2+a3
a1+b2+b3
b1+a2+a3
b1+a2+b3
b1+b2+a3
ou
b1+b2+b3
Et dans l'exemple que j'ai pris tout à l'heure c'est bien 5 car on choisi un seul nombre par couple ;-)
edit : j'ai pas rafraichi après avoir écrit mon message pour voir si ça n'avait pas déjà été dit le temps que j'écrive
Pour mon truc je choisis pour chaque couple a ou b.
Si on considère :
(a1, b1)
(a2, b2)
(a3, b3)
Les sommes possibles avec ces 3 couples sont donc
a1+a2+a3
a1+a2+b3
a1+b2+a3
a1+b2+b3
b1+a2+a3
b1+a2+b3
b1+b2+a3
ou
b1+b2+b3
Et dans l'exemple que j'ai pris tout à l'heure c'est bien 5 car on choisi un seul nombre par couple ;-)
edit : j'ai pas rafraichi après avoir écrit mon message pour voir si ça n'avait pas déjà été dit le temps que j'écrive
bizu53
Messages postés
1274
Date d'inscription
samedi 30 août 2008
Statut
Membre
Dernière intervention
21 juin 2015
860
2 janv. 2009 à 19:45
2 janv. 2009 à 19:45
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 ?
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 ?
KX
Messages postés
16752
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
31 août 2024
3 019
2 janv. 2009 à 20:31
2 janv. 2009 à 20:31
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
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
KX
Messages postés
16752
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
31 août 2024
3 019
2 janv. 2009 à 20:48
2 janv. 2009 à 20:48
En fait, en considérant ce que j'ai dit il faudrait également affiner si le résultat est positif
exemple : (5,-1) et (3,-4) mon algo ferai : -1+3=2 alors qu'on pourrai faire 5-4=1
exemple : (5,-1) et (3,-4) mon algo ferai : -1+3=2 alors qu'on pourrai faire 5-4=1
Vous n’avez pas trouvé la réponse que vous recherchez ?
Posez votre question
artragis
Messages postés
481
Date d'inscription
mardi 12 juin 2007
Statut
Membre
Dernière intervention
6 avril 2010
146
3 janv. 2009 à 11:51
3 janv. 2009 à 11:51
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
je sais pas si c'est vraiment bon mais c'est une piste selon moi
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
bizu53
Messages postés
1274
Date d'inscription
samedi 30 août 2008
Statut
Membre
Dernière intervention
21 juin 2015
860
3 janv. 2009 à 13:09
3 janv. 2009 à 13:09
Elle était belle mais elle fonctionne pas tout le temps. Car le fait de trouver plus petit en sélectionnant le b au lieu du a, n'est pas forcément le meilleur pour la suite.
Avec :
(5; -9)
(6; -2)
(7; -8)
(15; -11)
5+6+7+15=33
j'échange le 15 avec le -11 cela donne :
5+6+7-11=7
7<33 donc on continue sur cette somme...
5+6-8-11<0
5-2+7-11<0
-9+6+7-11<0
Au final on trouve, 5+6+7-11=7
Je n'ai pas essayé d'autre algo (même pas celui que j'ai proposé) mais juste à la vue des couples parce qu'ils sont peu nombreux, 15-9-8+6=4 ;-)
Avec :
(5; -9)
(6; -2)
(7; -8)
(15; -11)
5+6+7+15=33
j'échange le 15 avec le -11 cela donne :
5+6+7-11=7
7<33 donc on continue sur cette somme...
5+6-8-11<0
5-2+7-11<0
-9+6+7-11<0
Au final on trouve, 5+6+7-11=7
Je n'ai pas essayé d'autre algo (même pas celui que j'ai proposé) mais juste à la vue des couples parce qu'ils sont peu nombreux, 15-9-8+6=4 ;-)
bizu53
Messages postés
1274
Date d'inscription
samedi 30 août 2008
Statut
Membre
Dernière intervention
21 juin 2015
860
>
bizu53
Messages postés
1274
Date d'inscription
samedi 30 août 2008
Statut
Membre
Dernière intervention
21 juin 2015
3 janv. 2009 à 13:32
3 janv. 2009 à 13:32
En déroulant mon algo :
Dans l'ordre des écarts décroissants
(15; -11) ecart=26
(7; -8) ecart=15
(5; -9) ecart=14
(6; -2) ecart=8
Sous-étapes
Sous-sous-étapes
On a tout sommé donc on compare cherche le min entre 10 et 4,
donc c'est bien 15-8-9+6=4 la somme minimale positive.
Dans l'ordre des écarts décroissants
(15; -11) ecart=26
(7; -8) ecart=15
(5; -9) ecart=14
(6; -2) ecart=8
15 compensable au max par -8-9-2=-19 => 15-19=-4<0 donc on garde ou -11 compensable au max par 7+5+6=18 => -11+18=7>0 donc on garde
Sous-étapes
Sous-sous-étapes
On a tout sommé donc on compare cherche le min entre 10 et 4,
donc c'est bien 15-8-9+6=4 la somme minimale positive.
KX
Messages postés
16752
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
31 août 2024
3 019
>
bizu53
Messages postés
1274
Date d'inscription
samedi 30 août 2008
Statut
Membre
Dernière intervention
21 juin 2015
3 janv. 2009 à 13:35
3 janv. 2009 à 13:35
Tu vas encore te retrouver avec une complexité en O(2^n) !!!
Les pistes d'avant était "mieux" puisqu'elles étaient sauf erreur en O(n²)...
Les pistes d'avant était "mieux" puisqu'elles étaient sauf erreur en O(n²)...
bizu53
Messages postés
1274
Date d'inscription
samedi 30 août 2008
Statut
Membre
Dernière intervention
21 juin 2015
860
>
KX
Messages postés
16752
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
31 août 2024
3 janv. 2009 à 13:44
3 janv. 2009 à 13:44
Je ne sais pas c'est quelle complexité, mais ce n'est pas exponentielle car je fais plein de coupure dans mon arbre lorsque je tombe sur des résultats non-compensables => plein de sommes ne sont même pas tentées (ça ne se voit pas là parce qu'il n'y a pas beaucoup de couples donc c'est pas la meilleure sûrement oui sur si peu).
Par contre pour la dernière étape je me suis rendu compte que je dois bien faire les 2 sommes car si j'avais eu (1; -2) au lieu du (6; -2), je serais tombé sur 10, -1, -1, et -12 sans voir le 2 (-11+7+5+1)
Par contre pour la dernière étape je me suis rendu compte que je dois bien faire les 2 sommes car si j'avais eu (1; -2) au lieu du (6; -2), je serais tombé sur 10, -1, -1, et -12 sans voir le 2 (-11+7+5+1)
KX
Messages postés
16752
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
31 août 2024
3 019
3 janv. 2009 à 14:20
3 janv. 2009 à 14:20
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 ?
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 ?
bizu53
Messages postés
1274
Date d'inscription
samedi 30 août 2008
Statut
Membre
Dernière intervention
21 juin 2015
860
3 janv. 2009 à 14:33
3 janv. 2009 à 14:33
Parce qu'il s'agit de compensation maximale.
Donc si on a (par exemple) 5 qui peut est compensé au max par -438 on garde parce que dans les termes de la somme (des b) qui a donné -438 il peut y avoir -4, qui pourrait être bon par la suite 5-4, et éventuellement des nombres trop négatifs seront éliminés parce qu'ils le seraient trop.
Inversement, un nombre négatif qui peut être compensé jusqu'à "revenir" dans les positifs, on le garde parce que de cette sous-sommes positives on pourra peut être en trouver la somme minimale par la suite.
Contrairement à un nombre négatif qui serait compensé par un nombre trop petits (-52+47 par exemple), on l'élimine, ce qui nous évitera par la suite d'essayer toutes les sommes ayant ces 2 nombres. (De même du côté positif, si la sous-somme obtenue s'avère impossible à réduire sous un nombre que l'on a déjà)
Mais avec des (a1; b1) (a2; b2) (a3; b3), on ne peut pas dérouler mon algo puisque les coupures (ou inversement, qd on garde) ça dépend des résultats des sous-sommes... (qui d'ailleurs, ne sont faite qu'une fois).
D'ailleurs pour l'étape 2 tu écris "4 opérations" => ça pourrait n'être que 2 si à la première étape une à été éliminé.
Donc si on a (par exemple) 5 qui peut est compensé au max par -438 on garde parce que dans les termes de la somme (des b) qui a donné -438 il peut y avoir -4, qui pourrait être bon par la suite 5-4, et éventuellement des nombres trop négatifs seront éliminés parce qu'ils le seraient trop.
Inversement, un nombre négatif qui peut être compensé jusqu'à "revenir" dans les positifs, on le garde parce que de cette sous-sommes positives on pourra peut être en trouver la somme minimale par la suite.
Contrairement à un nombre négatif qui serait compensé par un nombre trop petits (-52+47 par exemple), on l'élimine, ce qui nous évitera par la suite d'essayer toutes les sommes ayant ces 2 nombres. (De même du côté positif, si la sous-somme obtenue s'avère impossible à réduire sous un nombre que l'on a déjà)
Mais avec des (a1; b1) (a2; b2) (a3; b3), on ne peut pas dérouler mon algo puisque les coupures (ou inversement, qd on garde) ça dépend des résultats des sous-sommes... (qui d'ailleurs, ne sont faite qu'une fois).
D'ailleurs pour l'étape 2 tu écris "4 opérations" => ça pourrait n'être que 2 si à la première étape une à été éliminé.
bizu53
Messages postés
1274
Date d'inscription
samedi 30 août 2008
Statut
Membre
Dernière intervention
21 juin 2015
860
3 janv. 2009 à 15:09
3 janv. 2009 à 15:09
Je fais un schéma (propre) ça sera plus parlant, parce qu'en réalité c'est ce que je fais, et que je dis par écrit :p
bizu53
Messages postés
1274
Date d'inscription
samedi 30 août 2008
Statut
Membre
Dernière intervention
21 juin 2015
860
>
bizu53
Messages postés
1274
Date d'inscription
samedi 30 août 2008
Statut
Membre
Dernière intervention
21 juin 2015
3 janv. 2009 à 15:20
3 janv. 2009 à 15:20
Voilà (j'y ai même fait figuré les opérations non calculées)
https://www.cjoint.com/?bdqhyDrfP1
https://www.cjoint.com/?bdqhyDrfP1
KX
Messages postés
16752
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
31 août 2024
3 019
3 janv. 2009 à 15:21
3 janv. 2009 à 15:21
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 !
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 !
bizu53
Messages postés
1274
Date d'inscription
samedi 30 août 2008
Statut
Membre
Dernière intervention
21 juin 2015
860
3 janv. 2009 à 15:31
3 janv. 2009 à 15:31
Je sais que la complexité est le pire.
Mais au pire ce n'est pas 4 : c'est pour ça que je prends mes couples dans l'ordre de leur écart décroissant => ça implique que les 2 qui ont été éliminés (dans mon schéma) allaient obligatoirement l'être.
Mon schéma là est un cas presque au pire (il y a simplement les résultats finaux tous négatifs sauf un, au lieu de devoir faire une recherche du minimum.
Mais au pire ce n'est pas 4 : c'est pour ça que je prends mes couples dans l'ordre de leur écart décroissant => ça implique que les 2 qui ont été éliminés (dans mon schéma) allaient obligatoirement l'être.
Mon schéma là est un cas presque au pire (il y a simplement les résultats finaux tous négatifs sauf un, au lieu de devoir faire une recherche du minimum.
KX
Messages postés
16752
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
31 août 2024
3 019
3 janv. 2009 à 15:35
3 janv. 2009 à 15:35
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)
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)
bizu53
Messages postés
1274
Date d'inscription
samedi 30 août 2008
Statut
Membre
Dernière intervention
21 juin 2015
860
3 janv. 2009 à 15:44
3 janv. 2009 à 15:44
Je n'ai pas compris ton "Et là j'obtiens", comment ?
KX
Messages postés
16752
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
31 août 2024
3 019
3 janv. 2009 à 15:52
3 janv. 2009 à 15:52
(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...)
(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...)
bizu53
Messages postés
1274
Date d'inscription
samedi 30 août 2008
Statut
Membre
Dernière intervention
21 juin 2015
860
3 janv. 2009 à 16:08
3 janv. 2009 à 16:08
Ah oui au temps pour moi. Mais j'ai bien peur qu'il ne s'agisse pas de les trier dans un certain ordre .. mais qu'au final on se retrouve à faire les sommes-couples couples à couples (combinaisons)
pour 4 couples A B C D, 6 au début
A+B
A+C
A+D
B+C
B+D
C+D
Puis, 3 additions
Le "somme-couple" résultant S + chaque couple non pris.
Puis 2, idem
Puis 1
Ça n'a pas l'air mal :) je vais voir aussi
pour 4 couples A B C D, 6 au début
A+B
A+C
A+D
B+C
B+D
C+D
Puis, 3 additions
Le "somme-couple" résultant S + chaque couple non pris.
Puis 2, idem
Puis 1
Ça n'a pas l'air mal :) je vais voir aussi
bizu53
Messages postés
1274
Date d'inscription
samedi 30 août 2008
Statut
Membre
Dernière intervention
21 juin 2015
860
3 janv. 2009 à 16:22
3 janv. 2009 à 16:22
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".
(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".
KX
Messages postés
16752
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
31 août 2024
3 019
3 janv. 2009 à 19:59
3 janv. 2009 à 19:59
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...
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...
bizu53
Messages postés
1274
Date d'inscription
samedi 30 août 2008
Statut
Membre
Dernière intervention
21 juin 2015
860
3 janv. 2009 à 21:15
3 janv. 2009 à 21:15
C'est vrai que je n'y avais pas pensé en binaire comme ça, mais je pense que lorsqu'on a un algo pour un, on peut en déduire facilement l'autre (et réciproquement).
Pour ta dernière remarque, c'est vrai que ça ressemble un peu à ce jeu sur le fond, mais pour le jeu ce n'est pas optimisable (si ce n'est éviter de recalculer des choses qui peuvent l'être) car il s'agit de tout type d'opération.
Dans mon/notre cas là, c'est seulement des additions, donc on peut (en plus de celle d'éviter de recalculer des choses inutilement) avoir une stratégie du choix plutôt qu'une stratégie de la manière de faire.
En tout cas j'ai pissé mon code et ça marche donc je vais mettre ce sujet en résolu, mais si quelqu'un veut continuer rien ne l'empêche de toute façon :).
Pour ta dernière remarque, c'est vrai que ça ressemble un peu à ce jeu sur le fond, mais pour le jeu ce n'est pas optimisable (si ce n'est éviter de recalculer des choses qui peuvent l'être) car il s'agit de tout type d'opération.
Dans mon/notre cas là, c'est seulement des additions, donc on peut (en plus de celle d'éviter de recalculer des choses inutilement) avoir une stratégie du choix plutôt qu'une stratégie de la manière de faire.
En tout cas j'ai pissé mon code et ça marche donc je vais mettre ce sujet en résolu, mais si quelqu'un veut continuer rien ne l'empêche de toute façon :).
bizu53
Messages postés
1274
Date d'inscription
samedi 30 août 2008
Statut
Membre
Dernière intervention
21 juin 2015
860
4 janv. 2009 à 13:21
4 janv. 2009 à 13:21
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.
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.
2 janv. 2009 à 19:31