Mr besoin d'aide

Help me!!!
j'ai un pti probleme d'algorythmique .
Sa serait possible d'avoir de l'aide?
En fait j'ai un probleme :
Un avion cargo peut contenir exactement 2*N conteneurs, alignés sur deux rangées de N conteneurs chacune. Chaque conteneur a un poids, et le poids d'une rangée est la somme des poids des conteneurs dans celle-ci. Pour équilibrer l'avion, on veut répartir les conteneurs dans les deux rangées de façon à ce que leur différence de poids (en valeur absolue) soit minimale. Étant donnés les poids des 2N conteneurs, écrivez une fonction qui renvoie ce minimum.
Comment on peut faire simple?
Merci d'avance

Napster a écrit:Help me!!!
j'ai un pti probleme d'algorythmique .
Sa serait possible d'avoir de l'aide?
En fait j'ai un probleme :
Un avion cargo peut contenir exactement 2*N conteneurs, alignés sur deux rangées de N conteneurs chacune. Chaque conteneur a un poids, et le poids d'une rangée est la somme des poids des conteneurs dans celle-ci. Pour équilibrer l'avion, on veut répartir les conteneurs dans les deux rangées de façon à ce que leur différence de poids (en valeur absolue) soit minimale. Étant donnés les poids des 2N conteneurs, écrivez une fonction qui renvoie ce minimum.
Comment on peut faire simple?
Merci d'avance

Bn! la solution la plus simple c'est ce qui suis...

























RIEN NON SERIEUX SA SERT A QUOI DES PROBLEME PAREIL!!!!

ben enfet c'est pour un concour d'informatique faut écrire des programmes pour etre selectionner j'ai fait toutes les questions mais la dernieres je bloque! Merci quand meme pour ton aide

Napster a écrit:Help me!!!
j'ai un pti probleme d'algorythmique .
Sa serait possible d'avoir de l'aide?
En fait j'ai un probleme :
Un avion cargo peut contenir exactement 2*N conteneurs, alignés sur deux rangées de N conteneurs chacune. Chaque conteneur a un poids, et le poids d'une rangée est la somme des poids des conteneurs dans celle-ci. Pour équilibrer l'avion, on veut répartir les conteneurs dans les deux rangées de façon à ce que leur différence de poids (en valeur absolue) soit minimale. Étant donnés les poids des 2N conteneurs, écrivez une fonction qui renvoie ce minimum.
Comment on peut faire simple?
Merci d'avance

Questions complémentaires: Tu as le poids de chacun des 2N conteneurs ou seulement la somme des poids des 2N conteneurs? (Si je lis bien, c'est chacun des 2N conteneurs!!!)

Oui c'est sa de chacun des 2N conteneurs . Je suis en train de tester avec une méthode de brute force qui testerai toute les possibilités de sommes de N conteneurs pour trouver la plus petite différence.Mais c'est lourd yoré pas une méthode plus soft?

J'ai spontanément pensé à utiliser la médiane de la série des poids puisqu'elle partage la dite série en deux sous séries de même amplitude: c'est à dire, tu connais le poids médian pour lequel 50% des conteneurs ont un poids inférieur et 50% un poids supérieur. Je réfléchis pour te proposer une solution complète bien ficelée...

C'est aussi ce que j'ai pensédès que j'ai lu le sujet mais en griboullant quelque ligne j'ai pas trouvé comment l'utiliser a bon essient. J'espere que vous trouverez !! Pck la je suis a fond dessus

c koi c topic serieux .....LOL

Dream a écrit:c koi c topic serieux .....LOL

A tois aussi tu trouve

Une autre idée... je n'ai pas cherché de solution bien rigoureuse

• Déterminer la médiane de la série des masses des conteneurs
  
• Déterminer la masse n_1 tel que n_1=max des masses inférieures à la médiane et n_2= min des masses supérieures à la médiane
  
• |n_1-n_2| est la différence cherché.

C'est pas beau mais ça doit marcher

Non sa marche pas
Enfin si j'ai bien compris...
Sinon en cherchant un peu feuille de papier et calculette a la main j'ai fait l'ébauche d'un petit alogorithme qui a l'air de faire des choses intéréssantes:
-il classe la série des 2N conteneurs par odre croissant
-Soit A et B les deux rangée de N conteneurs
-il met le plus gros conteneurs dans A puis le un peu moins gros dans B
-Il teste si A>B si c'est le cas il met le plus lourd des conteneurs restant dans B et le un peu moin lourd dans A
-ceci jusqu'il n'y est plus de conteners
-on obtient 2 rangée A et B + ou - équilibrés
-dès lors on calcule la difference de poids entre A et B
-Puis on cherche si il existe deux conteneurs dont l'inversion entre A et B réduirai la difference
-Ceci tant qu'il y a des solutions


Et sa a l'air de marché plutot pas mal (test avec plusieurs serie avec N=5 et N=6 résultat difference de 2 ou 3 )

Voila si vous avez une meilleure idée...

Pas mieux; mais il faut aussi que j'apprenne à lire!!!

Peut être en ordonnant tes deux sous séries partagés par la médiane ou en utilisant des quartiles et en ordonnant les 4 sous séries dans l'ordre croissant, tu peux optimiser les recherches!!

Tu prends pas l'avion essaie le train peut etre ^^
Aller bonne prise de tete ++

Dis moi si j'ai bien compris ton algorithme :
avec A et B les deux séries on prends par ex: N = 8 Avec m1 < m2 < m3 < m4 pour les valeurs minimums et
Avec M1 < M2 < M3 < M4 pour les valeurs maximum.

ca te ferait :

-A- m1 - m4 - M1 - M4

-B- m2 - m3 - M2 - M3

J'espere pas m'etre trompé jusque la. Par contre la ou je sais pas c pour la caisse ayant la valeur médiane dans le cas ou N est impair.
Je te laisse bucher je t'ai pas beaucoup aidé. J'espere que tu trouveras ta fonction. Dis moi juste si c'était a peu pres ca
Sinon RDV demain a l'aeroport de Marignan pour la partie pratique hein

tiens chuis aller sur ce site qui pourrait t'etre plus utile que mon aide XD : http://www.info.ucl.ac.be/~pvr/ds/FSAB1402/seance5.html
Person j'ai pas tout compris chuis pas un gick mais vu que toi t une brute tu devrais t'en sortir
tchao loick !

Dream a écrit:c koi c topic serieux .....LOL

Tu l'as dit Je me sent mais alors pas du tout concerné

tienoumaths a écrit:tiens chuis aller sur ce site qui pourrait t'etre plus utile que mon aide XD : http://www.info.ucl.ac.be/~pvr/ds/FSAB1402/seance5.html
Person j'ai pas tout compris chuis pas un gick mais vu que toi t une brute tu devrais t'en sortir
tchao loick !

Il est pas mal ton site
Même si ça m'interresse pas, j'arrive à comprendre!