Algorithme : Trouver la meilleur combinaison
Bonjour a tous !
Aujourd'hui je me suis lancé dans un projet un peu fou de calculer la meilleur combinaison possible parmi un ensemble N mais je ne connais pas d'algorithme (je ne peux pas bruteforce trop de possibilités).
Le problème est basé un peu sur le principe du : "Le Compte est bon"
J'ai un tableau de N valeurs distincte a atteindre : (ex) [30, 15, 16]
Pour atteindre ces valeurs, j'ai une piscine de X éléments (très grand nombre, 200 par exemple)
Chacun de ces éléments ajout +N dans chaque case de mon tableau.
Il existe une notion de "points supplémentaires" si n éléments sont présent (par exemple si on a l’élément 1 et 3 et 4 - la case 1 gagne 2, sans tenir compte de l'ordre)
Ex :
l’élément 1 ajoute +2 dans la première case du résultat, +1 dans la seconde, et +3 dans la dernière (j'ai donc [2, 1, 3])
l’élément 1 ajoute +1 dans la première case du résultat, +2 dans la seconde, et +1 dans la dernière (j'ai donc [1, 2, 1])
Etc...
J'ai P emplacement pour mettre des éléments (exemple 42 emplacements), il peut avoir des doublons
L'objectif est de trouver les différentes combinaisons qui me permettent d'attendre mon objectif au plus proche. (par exemple les 10 meilleurs)
Je bloque un peu sur la méthode a utiliser pour les N élements, pour un seul, le problème me semble assez simple il suffit de faire un graphe pondéré et de trouver le chemin le plus court (Algorithme A*) mais pour N ?
Merci d'avance pour l'aide
-----