Trouver la meilleure repartition (A la recherche de l'algorithme)

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.

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.

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

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

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)"

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.