Trouver la meilleure repartition (A la recherche de l'algorithme) [Résolu]

Signaler
Messages postés
694
Date d'inscription
lundi 5 décembre 2005
Statut
Membre
Dernière intervention
8 janvier 2014
-
Messages postés
694
Date d'inscription
lundi 5 décembre 2005
Statut
Membre
Dernière intervention
8 janvier 2014
-
Bonjour,
V’la le problème : j’ai un ensemble de paires du genre (catégorie1, 3 objets), (catégorie 2, 6 objets), (catégorie 3, 18 objets),… (catégorie n, m objets).
N n’est pas connu d’avance, pas plus que le nombre M d’objets que contient chaque catégorie.
Je cherche un algorithme qui me permettrait de calculer la répartition de ces paires en deux sous ensembles le plus « équilibré ». C’est-à-dire donnant des sommes de poids (nombre d’objets) de chaque sous ensemble dont le rapport est le plus proche de 1.

Par exemple :
Cat1, 2
Cat2 3
Cat3, 5
Cat4 1

Pourrait me donner comme solution
(Cat1, Cat2) et (Cat3, Cat4) parce que 2+3 / 5 +1 est proche de 1
ou encore
(Cat1, Cat2, Cat4) et (Cat3) parce que 2+3+1 / 5 est proche de 1

mais pas (Cat1, Cat2, Cat3) et (Cat4) parce que (2+3+5) / 1 est moins proche de 1 que les autres solutions

Mais à quoi ça sert ?

Ayant extrait des données par catégorie d’une base de données, je souhaiterais les présenter sur deux colonnes, classées par catégorie mais également avec une présentation correcte, c’est-à-dire sur deux colonnes « équilibrées »

PS : Je ne suis pas une tête en mathématique, alors si vous avez une solution ayez pitié de me la présenter dans un langage pas trop complexe. Ou alors dites-moi direct « Oublies si t’as pas bac +15 et deux ou trois thèses en préparation».

Merci pour votre aide.

6 réponses

Messages postés
126
Date d'inscription
jeudi 5 juin 2003
Statut
Membre
Dernière intervention
11 juillet 2006

bonjour

Je me trompe peut être mais si tu scannes tes catégories et que tu les tries par ordre de nombe d'éléments du plus petit au plus grand et que tu prends tes catégories par multiple de 2, la 1ere et la nieme la 2eme et la nieme-1 la 3eme et la nieme-2 tu vas ordonner tes colonnes pour avoir toujours un nombre d'élement proche de la moyenne du nombre d'objets.
Bien sur plus le nombre de catégories est grand et plus ton nombre d'objet et proche de la moyenne plus tes colonnes seront équilibrées.

Cordialement

TOCHE
Messages postés
694
Date d'inscription
lundi 5 décembre 2005
Statut
Membre
Dernière intervention
8 janvier 2014
15
Whoaaaa

C'est peut etre pas la solution optimale. Mais elle est élégante et surtout pas compliquée. J'ai l'impression d'avoir déjà compris rien qu'en lisant. Je l'adopte.

Cependant, si quelqu'un a encore mieux que la solution de ricky... J'ai cru comprendre qu'il s'agirait d'un algorithme de partition...

Merci beaucoup ricky.
Messages postés
74
Date d'inscription
jeudi 6 mars 2003
Statut
Membre
Dernière intervention
3 mai 2006

Salut,



J'ai bien une proposition à te faire, je ne sais pas si ça va être
vraiment efficace mais ça a l'air de fonctionner avec ton exemple...

On va dire qu'on a une colonne "Gauche" et une "Droite". On choisit
arbitrairement de favoriser la colonne "Gauche" (il faut bien
commencer la répartition par quelque part )

donc voici l'idée :



Se placer sur la "Catégorie" dont le nombre d'objets est le plus grand

Tant qu'on a des éléments "Catégorie"

Si "Objets à Gauche" > "Objets à Droite"

Mettre la "Catégorie" à "Droite"

"Objets à Droite" = "Objets à Droite" + " Objets Categorie"

Sinon

Mettre la "Catégorie" à "Gauche"

"Objets à Gauche" = "Objets à Gauche" + " Objets Categorie"

Fin Si

Passer au prochain élément "Catégorie" dont le nombre d'objets est le plus grand

Boucler



Si quelqu'un a mieux à proposer ça m'interesse aussi


DvdMizo
Messages postés
74
Date d'inscription
jeudi 6 mars 2003
Statut
Membre
Dernière intervention
3 mai 2006

oops j'ai mis trop longtemps à répondre du coup j'avais pas vu les
réponses précédentes ... du coup ma solution est un peu "ridicule"

lol


DvdMizo
Messages postés
694
Date d'inscription
lundi 5 décembre 2005
Statut
Membre
Dernière intervention
8 janvier 2014
15
Salut DvdMizo

Ta solution en est une autre et même si celle de ricky semble plus proche, la tienne n'est pas ridicule.

Merci de ta participation.
Et si vous lisez notre appel au secours :

"Si quelqu'un a encore pire que les solutions déjà proposées, qu'il prenne son clavier (pas pour le jeter, mais pour dispenser un peu sa science, restons en paix)"
Messages postés
694
Date d'inscription
lundi 5 décembre 2005
Statut
Membre
Dernière intervention
8 janvier 2014
15
On m'a proposé une autre solution :

http://www.javafr.com/forum.v2.aspx?id=696404

Si ça interesse quelqu'un (DvdMizo entre autre)

La question finale est donc : Mais quelle est la meilleure solution ?

Je tiens à remercier en passant tout ceux qui ont créé et qui font vivre ce forum d'utilité publique ainsi que tout ceux qui y apportent leur pierre.