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

Question

Bonjour,
V&#146;la le probl&#232;me : j&#146;ai un ensemble de paires du genre (cat&#233;gorie1, 3 objets), (cat&#233;gorie 2, 6 objets), (cat&#233;gorie 3, 18 objets),&#133; (cat&#233;gorie n, m objets).
N n&#146;est pas connu d&#146;avance, pas plus que le nombre M d&#146;objets que contient chaque cat&#233;gorie.
Je cherche un algorithme qui me permettrait de calculer la r&#233;partition de ces paires en deux sous ensembles le plus &#171; &#233;quilibr&#233; &#187;. C&#146;est-&#224;-dire donnant des sommes de poids (nombre d&#146;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 &#224; quoi &#231;a sert ?

Ayant extrait des donn&#233;es par cat&#233;gorie d&#146;une base de donn&#233;es, je souhaiterais les pr&#233;senter sur deux colonnes, class&#233;es par cat&#233;gorie mais &#233;galement avec une pr&#233;sentation correcte, c&#146;est-&#224;-dire sur deux colonnes &#171; &#233;quilibr&#233;es &#187;

PS : Je ne suis pas une t&#234;te en math&#233;matique, alors si vous avez une solution ayez piti&#233; de me la pr&#233;senter dans un langage pas trop complexe. Ou alors dites-moi direct &#171; Oublies si t&#146;as pas bac +15 et deux ou trois th&#232;ses en pr&#233;paration&#187;.

Merci pour votre aide.

ricky78 · Accepted Answer

bonjour

Je me trompe peut &#234;tre mais si tu scannes tes cat&#233;gories et que tu les tries par ordre de nombe d'&#233;l&#233;ments du plus petit au plus grand et que tu prends tes cat&#233;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'&#233;lement proche de la moyenne du nombre d'objets.
Bien  sur plus le nombre de cat&#233;gories est grand et plus ton nombre d'objet et proche de la moyenne plus tes colonnes seront &#233;quilibr&#233;es.

Cordialement

TOCHE

cs_AlexN · Answer

Whoaaaa 

C'est peut etre pas la solution optimale. Mais elle est &#233;l&#233;gante et surtout pas compliqu&#233;e. J'ai l'impression d'avoir d&#233;j&#224; 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.

Dvdmizo · Answer

Salut,



J'ai bien une proposition &#224; te faire, je ne sais pas si &#231;a va &#234;tre
vraiment efficace mais &#231;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&#233;partition par quelque part  )

donc voici l'id&#233;e :



Se placer sur la "Cat&#233;gorie" dont le nombre d'objets est le plus grand

Tant qu'on a des &#233;l&#233;ments "Cat&#233;gorie"

    Si "Objets &#224; Gauche" > "Objets &#224; Droite"

        Mettre la "Cat&#233;gorie" &#224; "Droite"

        "Objets &#224; Droite" = "Objets &#224; Droite" + " Objets Categorie"

    Sinon

        Mettre la "Cat&#233;gorie" &#224; "Gauche"

        "Objets &#224; Gauche" = "Objets &#224; Gauche" + " Objets Categorie"

    Fin Si

    Passer au prochain &#233;l&#233;ment "Cat&#233;gorie" dont le nombre d'objets est le plus grand

Boucler



Si quelqu'un a mieux &#224; proposer &#231;a m'interesse aussi 


DvdMizo

Dvdmizo · Answer

oops j'ai mis trop longtemps &#224; r&#233;pondre du coup j'avais pas vu les
r&#233;ponses pr&#233;c&#233;dentes ... du coup ma solution est un peu "ridicule" 

lol 


DvdMizo

cs_AlexN · Answer

Salut DvdMizo

Ta solution en est une autre et m&#234;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&#233;j&#224; propos&#233;es, qu'il prenne son clavier (pas pour le jeter, mais pour dispenser un peu sa science, restons en paix)"

cs_AlexN · Answer

On m'a propos&#233; une autre solution :

http://www.javafr.com/forum.v2.aspx?id=696404

Si &#231;a interesse quelqu'un (DvdMizo entre autre)

La question finale est donc : Mais quelle est la meilleure solution ? 

Je tiens &#224; remercier en passant tout ceux qui ont cr&#233;&#233; et qui font vivre ce forum d'utilit&#233; publique ainsi que tout ceux qui y apportent leur pierre.

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

6 réponses

Votre réponse

Discussions similaires