J'ai besoin d'aide pour un exo en algorithmique, le problème de l'optimisation d'un ascenseur avec des charges.

Supposons qu'on a un grand batiment, le but est de trouver le nombre fixe d'arrets de l'ascenseur pour que chaque personne puisse rejoindre l'étage qu'elle veut en montant ou en descendant les escaliers. Le but est de minimiser le nombre d'étages parcourus par les personnes après etre sorti de l'ascenseur.

On doit aussi prendre en compte le fait que monter les marches est plus dur que les descendre. On doit assumer qu'un poids de 10kg porté requiert 2 fois plus d'effort pour monter que pour descendre. Pour les poids plus légers, c'est proportionnel, par exemple un poids de 5kg demande 1.5 fois plus d'efforts pour la montée.

Le but du programme est d'implementer le nombre optimal d'arret si les gens portent des charges et préfèrent donc descendre plutot que de monter.

Je peux donner plus de détails sur l'input et l'output.

J'aimerais vraiment svp que quelqu'un puisse m'expliquer comment ca marche et m'aider a le faire, car je ne comprend vraiment pas, et ca fait longtemps que j'ai pas pratiqué

Je pense que pour quelqu'un ayant un bon niveau, ca devrait etre facile a faire.

Merci

La bonne reponse: ecrit le probleme formellement. Quel est l'entree. Quel est la structure d'une solution. Comment sont evalue les solutions.

Je suis désolé, donc voila comment ca marche.

Chaque cas commence par une ligne contenant le nombre de passagers de l'ascenseur et le nombre d'arret qu'il doit faire. S'ils sont tout les deux egaux a 0, c'est la fin de l'input. Après ca, on aura r lignes contenant chacune 2 nombres qui indiquent respectivement l'étage auquel les passagers veulent quitter l'ascenseur ainsi que le poids qu'ils portent en grammes. Le maximum de passager est 100 ainsi que le maximum d'étages (100). Un passager ne peut porter plus de 10 000 grammes.

Le nombre d'arrets ne peut pas etre plus grand que le nombre de passagers.

Pour l'input suivant:

1 1
5 500
2 1
3 500
5 500
3 1
3 500
4 500
5 500
0 0

On aura l'output suivant ( on a 3 cas ici)

5
5
4

J'espère que c'est plus clair

Je n'ai pas compris tes contraintes et ce que tu cherches a optimiser. Si tu peux faire autant d'arret que de passager, alors tu peux t'areter a tous les etages et les passager ne prennent jamais l'escalier.

Ecrit ton probleme formellement sous la forme d'un systeme d'equation. parametre d'entre, sortie, contrainte et fonction a optimiser.

Je n'ai pas compris non plus ce que tu cherches à optimiser. Le nombre d'arrêts de l’ascenseur subis par chaque utilisateur? Le nombre d'escaliers à monter/descendre par l'utilisateur bloqué à un étage parce qu'il a dépassé un nombre limite d'arrêts?

Je pense que le problème n'est de toute façon pas intuitif car perso quand je prends l'ascenseur je ne m'attends pas à qu'il me dise de descendre et de continuer par les escaliers.

Eij_iZ_WanteD, ca existe dans les tres grands batiments. Tu as souvnet des trucs comme ca. Par exemple, des ascenceurs pairs et impairs ou ce genre de truc.

Oui mais tu prends l'autre ascenseur après et non des escaliers. xD

Ce que le problème doit retourner sont les étages ou l'ascenseur doit s'arreter en fonction de notre input ou on indique combien d'arret on doit avoir ainsi que chaque personne et le poids qu'elle porte avec elle. Vous voyez le truc?

Par exemple, pour l'input
2 1
3 500
5 500

On indique qu'on a 2 personne et qu'on doit faire un seul arret.
Puis ensuite on indique la 1ère personne veut s'arreter au 3ème étage et porte 500g et que la 2ème personne veut s'arreter au 5ème et porte 500g.

Le programme va donc output 5 qui est l'étage ou il va s'arreter puisque dans ce cas ce serea plus facile pour le 1er de descendre 2 étages avec 500g que pour l'autre de monter 2 étages avec 500g.

Alors pour coder, je sais meme pas quoi faire..

J'espère avoir été plus clair

Oui je comprends, pour ton dernier exemple :

3 1
3 500
4 500
5 500

Si on s'arrête au 5 on a deux passagers qui descendent, mais le total detage dessendus sera de 3 ( 1 pour le mec du quatrième, et deux pour celui du troisième).
Si on s'arrête au 4 il y aura un etage monté et un etage dessendu, en tout 2 etage parcours.
10kg = x2 effort; 5kg = x1.5 effort; Pour moi cest pas possible mais on peut quand même en déduire qu'avec 500g l'effort n'est pas altéré entre dessente et montée - je crois comprendre que l'effort ne dépend QUE du poids de la charge.
Donc ce sera plus worth de s'arrêter au 4 dans ce cas.
Dailleurs t'aurais du précisé que l'ascenser ne faisait qu'un arrêt a moins que dans ma fonsdé je l'ai zappé.
Tu peux ecrire ca en programme, en testant toute les conditions dans une boucle peut etre ? je sais pas si tu as le droit de faire ca j'ai jamais fais d'algo, dois tu trouver le moyen le plus optimal ou osef complet?

car si jvois bien un

TANT QUE j'ai pas check tout les cas (càd le nombre de dessente/montées avec le poids etc de chaque etage )
Enfait jvois bien une variable qui additione chaque voyage a pied de chaque voyageur multiplié par l'effort si montée.

je te le fait en algo/c/php oklm, EN PARTANT DU PRINCIPE QUE 5kg = eff x1 et 10 = x2 ( ce qui est bcp plus logique que ton bail ).

int $total;

TANT QUE ( a toi de trouvé je te conseil un for jpréfère tu met direct conditions et incrémentation -- genre -- $nbetage = 0; nbetage < total_carrelage ; nbetage ++ )
{
tant que(personne < personne max avec un personne++)
on regarde ce que la personne 0 a comme trajet, enfait faut faire mass variable je pense car tu devras faire pas mal de soustraction/additions pour les etages parcours a iep et de multiplication pour leffort.

je t'aiderais pas plus gl hf

ah ok, j'ai compris!

Le nombre d'arret maximum est donner dans le probleme.
Le nombre d'etage est donne dans le probleme.
L'endroit ou chaque personne et sa charge est donne dans le probleme.

Je n'ai pas compris ce que tu cherche a optimiser. La somme des poids des gens qui ne sont pas dans le bon etage?

PS: ca sent la programmation dynamique ce probleme!

Désolé j'ai zappé ce topic. C'était a faire pour la semaine dernière et j'ai pas réussi, trop dur pour mon niveau.

Je lirais vos réponses demain.

Godrik Oui c'est exactement ca, on était sur le chapitre de la programmation dynamique, comment tu le sais?

C'est evident que dans un probleme comme ca il y a une propriete de sous-optimalite. J'ai pas regarde les equations dans le details, mais clairement la fonction objective a une somme dedans sur une suite de choix qui est pris par l'algorithm. Donc c'est sur qu'il y a un programmation dynamique qui marche.

C'est rigolo comme probleme, je mettrais ptet ca dans mon exam.