Combinaison pour arriver au résultat

Bonjour à tous.

J'ai un tableau avec 3 valeurs par lignes en pourcentage
exemple
ligne 1 = 30 / 20 / 50
ligne 2 = 10 / 10 / 80
ligne 3 = 20 / 20 / 60
ligne 4 = 80 / 05 / 15

le résultat 20 / 25 / 55
Je cherche un moyen de trouver la meilleurs combinaison possible en additionnant des valeurs, pour arriver à un chiffre le plus proche du résultat.

merci

Je ne comprends pas du tout ta question, et je crains de n'être pas le seul ! Dans l'exemple que tu donnes, à quoi faut-il aboutir ?

Désolé je me doute que je n'ai pas été très clair.

Je vais essayer d'être plus explicite .

j'ai trois valeurs qui corresponde à trois résultats
20 / 25 / 55

Ensuite j'ai plusieurs tableaux avec aussi trois valeurs

array[1] = 30 / 20 / 50
array[2] = 10 / 10 / 80
array[3] = 20 / 20 / 60
array[4] = 80 / 05 / 15


J'aimerais que, pour les résultats ( 20 / 25 / 55) un résultat le plus proche possible, soit trouvé en additionnant les tableaux entre eux, ou si les valeurs sont identiques, choisir directement le tableau.

Désolé si ce n'est pas encore très clair, ce n'est pas évident à expliquer .



le résultat 20 / 25 / 55

Et donc, ici, le résultat le plus proche possible serait array[3] ? Et si on avait array[5]=10/15/30 et array[6]=10/10/25, le résultat le plus proche serait atteint par array[5]+array[6] ?
Si c'est bien ça... l'algo s'annonce coton, en effet !

oui exactement, j'ai bien l'idée de faire toutes les additions possibles, mais ça risque de charger la page .

Au niveau de la charge, tout dépend des dimensions : combien de tableaux de combien d'éléments au maximum. Je verrais bien une solution par récursivité. Je sais que ça fait débat, les algos récursifs, perso je trouve ça élégant... à condition de pas faire exploser la pile ! Donc : quelles dimensions ?
Modifié par petibato (27 Sep 2013 - 23:30)

J'ai trouvé une solution
je vais utiliser la fonction de Levenshtein

Ouais, c'est sûr que t'as besoin d'une fonction de calcul de distance, mais le repérage des matrices à sommer pour minimiser cette distance, selon moi doit passer par la récursivité.

petibato a écrit :
Ouais, c'est sûr que t'as besoin d'une fonction de calcul de distance, mais le repérage des matrices à sommer pour minimiser cette distance, selon moi doit passer par la récursivité.

J'adore !

Voici un début de solution...

function somme($valeurs) {
	$ret = 0;
	foreach($valeurs as $valeur) {
		$ret += $valeur;
	}
	return $ret;
}

function distance($valeurs, $cible) {
	$ret = abs(somme($valeurs) - $cible);
	
	return $ret;
}

function fabriquer_combinaisons($combinaisons, $tableau, $resultat, $initial, $index) {
	$nb_valeurs = count($tableau);
	for ($cpt = $index;$cpt < $nb_valeurs;$cpt++) {
		$valeur = $tableau[$cpt];
		$combinaison = $initial;
		$combinaison[$cpt] = $valeur;
		$combinaisons[] = array(distance($combinaison, $resultat), $combinaison);
		fabriquer_combinaisons(&$combinaisons, $tableau, $resultat, $combinaison, $cpt+1);
	}
}

function trouver_combinaison($tableau, $resultat) {
	$initial = array();
	$combinaisons = array();
	fabriquer_combinaisons(&$combinaisons, $tableau, $resultat, $initial, 0);
	sort($combinaisons);
	foreach($combinaisons as $combinaison) {
		print_r($combinaison);echo "<br>";
	}
}

$tableau = array(1,2,3,4);
$resultat  = 6;
trouver_combinaison($tableau, $resultat);

On met des valeurs dans $tableau, on donne un $resultat à atteindre, et l'algo affiche toutes les solutions possibles classées de la meilleure à la pire. Ici, la distance nulle est atteinte pour 2+4 (la meilleure car la plus courte) et pour 1+2+3 (classée en seconde position). Je te laisse extrapoler