Discussion :

[CQ0sMo]

Bonsoir... je débute sur java et j'ai un problème à résoudre qui me fait souffrir . J'aurais besoin de votre aide si cela est possible.

Merci d'avance.

Voici l'énoncé.

Dans le futur, la foi capitaliste a touché tous les habitants du monde, y

compris le Père Noël. Plus question de distribuer les cadeaux

gratuitement,

maintenant, on les fait payer.

Justement, le Père Noël est en train d'examiner la ville de

Brétigny-sur-Orge, où il doit distribuer certains cadeaux. Ses cerfs se

sont syndiqués, et ils refusent de transporter plus de 170kg de cadeaux

dans la hotte. Le Père Noël doit essayer de rentabiliser au maximum son

voyage vers Brétigny-sur-Orge sans dépasser la limite de poids autorisée

par les cerfs (sinon, ce serait la grève assurée).



La Père Noël a reçu la liste suivante :



45 enfants veulent une Playstation 4

> poids : 9kg

> prix (facturé aux parents) : 630€



70 enfants veulent un iPad2, la nouvelle invention de Steve Jobs (c'est

comme un iPad, mais plus petit... comme un iPhone, mais plus grand...)

> poids : 8kg (par soucis d'écologie, le chargeur est en bois massif)

> prix : 560€



35 enfants veulent un chargeur pour Ipad2

> poids : 6kg

> prix : 420€ (le bois massif, c'est cher)



55 enfants veulent la chaîne hi-fi compatible iPod, "designed" par Tokyo

Hotel (la notice est uniquement en Allemand, et la chaîne ne joue que de

la

très mauvaise musique)

> poids : 4.85kg

> prix : 340€



Quelle quantité de chaque cadeaux le Père Noël doit-il emporter afin de

respecter le quota maximum imposé par ces fainéants de cerfs tout en

maximisant son chiffre d'affaire ?



Vous devrez, dans la réponse, donner le meilleur chiffre d'affaire que

peut réaliser le Père Noël, quels cadeaux il doit emporter, et en quelles

quantités. De plus, vous devrez m'expliquer la méthode choisie pour

trouver

la solution.

Pour trouver la solution, vous pouvez soit calculer à la main (très très

long - à peu près 6 millions de combinaisons possibles à tester) soit

écrire un programme Java qui réalise les calculs (très rapide).

[yaraco]

De base, version brute de décoffrage, il s'agirait de calculer toutes les combinaisons possibles de prix totaux et de les ranger dans un tableau trié.

Ensuite chercher le premier nombre qui correspond au critère de poids (donc le prix le plus élevé possible).

Mais bon, je ne me suis pas penché sur la question, et ça dépend peut-être aussi de la partie du programme que vous êtes en train d'étudier en ce moment (algorithmie des graphes p-e?).

Très marrant l'énoncé en tout cas.

DUT?

[Rei Ichido]

Personnellement ça m'a pris 2 min avec excell ... parce que j'avais la flemme de calculer.
Sachant que tous les cadeaux sauf 1 ont le même ratio prix/poids, c'est pas bien dur.

[CQ0sMo]

Merci de tes indications... je suis penché dessus depuis un bon moment :s


Euh... peut importe la partie du programme, il n'a pas spécifier une quelconque manière de faire ( libre ).

Oui DUT.


Si d'autre on des soluces... je suis preneur

Merci.

[Rei Ichido]

1. Puisqu'on veut optimiser le prix total, avec une limite de poids, calculer le rapport prix/poids de chaque objet.

2. Observer qu'il est le même pour tous (70€/kg), sauf pour un qui est lègérement supérieur (70,1 environ), c'est la chaine.

3. En déduire qu'il faut essayer de caser le maximum de chaines, mais pas tout à fait vu qu'elle a un poids fractionnaire il y aura du poids total perdu.

4. Faire une formule sous excel qui calcule bêtement le prix obtenu en fonction du nombre de chaines mis. Il suffit de faire : (prix de la chaine * n) + 70 * ( 170 - entier supérieur à (poids d'une chaine * n)). Il n'y a pas tant de valeurs que ça, on voit que le max est 11910€, et qu'il est atteint pour 3 valeurs différentes. Il suffit donc d'en prendre une et de chercher 30 secondes comment atteindre le poids restant avec les valeurs 6,8 et 9. Si on ne trouve pas, changer de valeur.

5. Conclure en se disant que vu le prix horaire d'un programmeur java, le Père Noël qui vient de gagner 10€ à optimiser aurait mieux fait de se contenter de pas chercher à calculer quoi que ce soit et de remplir bêtement sa hotte.