Identifier les nombres amenant à un résultat précisRésolu

Question

Bonjour à tous, 

Après pas mal de recherche sur le net, je me tourne vers vous.
Mon problème va paraitre simple à plusieurs mais la logique ne veut pas rentrer dans mon petit cerveau ;)

Voila mon problème : 

J'ai un array avec les valeurs suivantes : 
array(12.51, 45.62, 9.14, 1, 45, 0.10);

Et je cherche à déterminer la combinaison de ces chiffres me donnant le total 10.14 par exemple

la fonction est donc censée retourner les valeur 9.14 et 1 qui donnent ce résultat en s'additionnant.

Quelqu'un pourrait me donner des pistes comment réaliser cette fonction en PHP ?

Sur le net, j'ai trouvé plusieurs solutions utilisées sur ... Excel mais rien que je n'ai encore réussi à transposer en PHP.

Merci d'avance de votre aide

jordane45 · Answer

Bonjour,

Pourrais tu nous donner un peu plus d'informations ? 
- Un même nombre peut il être réutilisé plusieurs fois ?
- Veux tu limiter les combinaisons à deux nombres ou peu importe ?
- Quels opérateurs mathématiques sont autorisés ( + - / * ... les puissances ?.. les Modulo ?.. )
- Ton tableau est il toujours de taille fixe ?



Quoi qu'il en soit, une première piste de réflexion est de parcourir ton array par une (ou plusieurs si nécéssaires..) boucle(s) ..et pour chaque nombre.. tester les différentes possibilités avec les autres nombres (en additionnant chacun des nombre à celui que tu regarde (un par un, puis deux par deux....)
Recommencer avec la soustraction..
etc...
Ce qui va faire beaucoup de conditions à tester... 

Maintenant, si tu as trouvé des solutions (à partir d'Excel par exemple) il serait peut être intéressant de les étudier pour ensuite les "ré-encoder" en PHP.
Tu as quelques exemples ?

jdaviaud · Answer

Ah petit probleme je viens de perdre le roman que j'ai voulu poster en envoyant le formulaire en réponse donc je recommence : 

Je disais donc pour commencer, merci beaucoup de ta réponse rapide ;)

J'en ai besoin pour pointer des paiements CB
la banque m'indique tous les matins le total de transactions recues, correspondant à des commandes de mon site, seul problème les montants pris en compte par la banque ne se suivent pas forcement et peuvent avoir plusieurs jours d'éccart

J'ai donc un array avec les montant de mes commandes des X derniers jours, et il faut que je trouve dedans la liste des montants permettant d'obtenir ce total indiqué par la banque

Pour répondre à tes questions plus précisement donc : 
- Chaque nombre de l'array ne peut etre utilisé qu'une seule fois
- Pas de limite sur le nombre de nombres utilisés, il se peut que tout l'array soit nécessaire 
- Seul opérateur utilisé, l'addition
- Le tableau ne sera pas de taille fixe il dépend du nombre de commandes


Les exemples excel que j'ai trouvé ne m'aident pas vraiment
http://www.teachexcel.com/excel-help/excel-how-to.php?i=6073
http://superuser.com/questions/204925/excel-find-a-subset-of-numbers-that-add-to-a-given-total
( Je n'ai pas concervé les autres n'ayant pas trouvé d'utilité pour ce que je souhaitais faire )

Merci d'avance de ton aide

jdaviaud · Answer

Une idée ? :)

nicotontige · Answer

Bonjour, Ceci devrait vous plaire : "; } } } } ?>

nicotontige · Answer

je reviens sur cette solution.
Si tu utilises un grand tableau de nombres, il faut optimiser au maximum cette exécution.
Je pense que ce code est plus léger :
<?php

recherche_valeur(array(12.51, 45.62, 9.14, 1, 45, 0.10), 10.14);

function recherche_valeur($tab, $result) {

for ($i = 0 ; $i < count($tab) ; $i++) {
  if (in_array($result - $tab[$i], $tab)) {
   echo "nombre : " . $tab[$i] . " et " . ($result - $tab[$i]);
   break;
  }
 }
}

?>

jdaviaud · Answer

Bonjour nicotontige  et merci de ta réponse

c'est une fonction de la sorte sur laquelle je suis entrain de travailler également mais ca ne marche qu'avec 2 ou 3 valeurs simples

par exemple dans l'exemple en dessous, ca ne passe plus :

recherche_valeur(array(91.30, 46.30, 60, 45.30, 89.30,65.10), 260.70);

( Obtenir 260.70 avec les nombres 46.30, 60, 89.30 et 65.10 )

Avec 2 valeurs j'arrive à faire une fonction correcte, mais dès que cela dépasse 2 éléments à comparer, c'est là que je suis un peu largué sur la marche à suivre pour intervertir toutes les valeurs

jordane45 · Answer

J'ai trouvé mieux (et beaucoup plus aboutie dans mes recherches ^^ ) $arr = array(12.51, 45.62, 9.14, 1, 45, 0.10); // compte le nombre d'éléménts $n = count($arr); // declare le tableau de sortie $sortie = array(); // Tableau de sortie // Liste des combinaisons : for($i=1;$i<=$n;$i++) { liste_combinaison(",",$arr,$i); } echo '

';
Echo 'Nb Combinaisons : ' . count($sortie);
echo '

'; echo '

';
//print_r($sortie);
echo '

'; $tbl_liste_somme=sommeTbl($sortie); $tbl_liste_somme= msort($tbl_liste_somme, array('somme','combinaison')); echo ""; for ($l=0;$l"; Echo ""; echo ""; } echo "

COMBINAISON	SOMME
".$tbl_liste_somme[$l]['combinaison']."	" . $tbl_liste_somme[$l]['somme'] . "

"; function liste_combinaison($debut,$tags,$profondeur) { global $sortie; if($profondeur == 0) { array_push($sortie,$debut); return; } $n = count($tags); for($i=0;$i<$n;$i++) { liste_combinaison($debut.$tags[$i].",",array_slice($tags,$i+1),$profondeur-1); } } function Factorielle($number){ $retour = 1; if ($number>1) { $retour = Factorielle($number-1); } return $number*$retour; } function sommeTbl($arr){ // Calcule la somme de chaque combinaison $n = count($arr); $tbl_somme = array(); for($i=0;$i<=$n;$i++) { //Combinaison $tbl_somme[$i]['combinaison'] = substr(substr($arr[$i],1),0,-1); //Somme $explode_val=explode(",",$arr[$i]); $sum = array_sum($explode_val); $tbl_somme[$i]['somme'] = $sum; } return $tbl_somme; } function msort($array, $key, $sort_flags = SORT_REGULAR) { // Trouvé sur : http://blog.jachim.be/2009/09/php-msort-multidimensional-array-sort/ if (is_array($array) && count($array) > 0) { if (!empty($key)) { $mapping = array(); foreach ($array as $k => $v) { $sort_key = ''; if (!is_array($key)) { $sort_key = $v[$key]; } else { // @TODO This should be fixed, now it will be sorted as string foreach ($key as $key_key) { $sort_key .= $v[$key_key]; } $sort_flags = SORT_NUMERIC; } $mapping[$k] = $sort_key; } asort($mapping, $sort_flags); $sorted = array(); foreach ($mapping as $k => $v) { $sorted[] = $array[$k]; } return $sorted; } } return $array; } J'ai ajouté du tri (qui marche plus ou moins bien...) Mais maintenant tu as : La liste des combinaisons possible + La somme correspondante exemple: Array ( [0] => 12.51 [1] => 45.62 ) Nb Combinaisons : 3 COMBINAISON SOMME 12.51 12.51 45.62 45.62 12.51,45.62 58.13 0 EDIT : Même plus besoin de GMP ! Cordialement, Jordane

Identifier les nombres amenant à un résultat précis

7 réponses

Votre réponse

Discussions similaires