Le 4 mai 2021, la plateforme Yahoo Questions/Réponses fermera. Elle est désormais accessible en mode lecture seule. Aucune modification ne sera apportée aux autres sites ou services Yahoo, ni à votre compte Yahoo. Vous trouverez plus d’informations sur l'arrêt de Yahoo Questions/Réponses et sur le téléchargement de vos données sur cette page d'aide.
Algorithme de distribution de nombres?
Soit un ensemble de n nombres entiers positifs xi : x0, x1, x2, ...xn.
Je les distribue dans K sous-ensembles, avec k valant 2, 3, ... n-1.
K étant donné, comment procéder pour cette distribution sachant que je cherche à ce que les sommes des nombres xi contenus dans chaque sous-ensemble soient les plus proches possibles les unes des autres ?
Par exemple : les nombres 3, 5, 7 et 8. Si K vaut 2, j'aurais les sous-ensembles optimaux au sens du critère ci-dessus : (3 et 8) et (5 et 7).
2 réponses
- Ramis VLv 7il y a 1 décennieRéponse favorite
c'est très simple.
le même genre de problème se pose quand on cherche à optimiser une palette de couleurs ou à créer un arbre de Huffmann.
tu fais la somme de tes xi et tu divise par K, tu obtiendra alors la somme moyenne de chaque sous ensemble.
ensuite, pour composer le premier, tu as le choix de rechercher toutes les combinaisons pour trouver celle qui est le plus proche de la moyenne, puis passer au suivant avec ce qui reste, mais vers la fin, tu sera obligé de t'écarter de plus en plus de cette moyenne. ou bien de rechercher un optimal global (par un calcul de somme des écarts, très long), ou bien de prendre les valeurs dans l'ordre où elles se présentent et d'arrêter le remplissage du sous-ensemble quand la moyenne est atteinte, ensuite, tu peux gérer un reste de ce qui dépasse de la moyenne, et le cuimmuler au sous-ensemble suivant (compensation par diffusion d'erreur)
pour certaines de ces impémentation, il faut passer pas la récursivité.
pour les grands ensembles, ce type de traitement peut devenir très long.
tu peux aussi t'inspirer des programmes de conversion d'images tramées aléatoires (nuage de points)
- latite bretonneLv 5il y a 1 décennie
il faut raisonner sur des moyennes : si k = 2 tu calcules les moyennes en prennant les xi 2 par 2 , puis tu choisis la répartition dont les moyennes sont les moins éloignées (question de distance à ma moyenne absolue... )