Je cherche depuis 20 min un algo sans trouver de véritable piste.
Il s’agit d’un algo qui regroupe des données. Comme un exemple vaut mieux qu’un long discours voici quelques choses de concret.
Voici plusieurs valeurs : 7, 15, 5, 10, 5, 2, 10, 13, 13
Je cherche à faire des groupes de 20, en optimisant on devrait donc trouver :
{15, 5}
{13, 7}
{13, 5, 2}
{10, 10}
Facile à dire, difficile à faire, j’ai commencé à chercher sous google avec des arbres sans rien trouver, il me faudrai juste une piste.
Actuellement, j’ai trouvé un algo moins optimisé qui me donne ça :
{7, 5, 5, 2}
{15}
{10, 10}
{13}
{13}
Il prend les valeurs dans l’ordre.
Si il s’agit de la première valeur, je crée mon premier groupe et je passe à la valeur suivante
Pour les valeurs suivantes :
(1) je met ma valeur dans le premier groupe
(2) si la somme est inférieur à 20, je laisse cette valeur dans ce groupe, sinon je le met dans le groupe suivant et je reviens en (2)
(3) Si il n’y a pas de groupe suivant, je crée un nouveau groupe.
Comme vous pouvez le remarquer, l’algo ci-dessus crée 5 groupes alors qu’il pourrait s’en contenter de 4.
Comment faire ?
