Κυριακή, 7 Δεκεμβρίου 2014

Τα Δώρα

Καθ' ότι πλησιάζουν Χριστούγεννα, το σημερινό πρόβλημα έχει σχέση με τα Χριστούγεννα, ώστε να μπούμε σιγά - σιγά στο εορταστικό κλίμα του Δωδεκαήμερου.
Ο Johann και  Klaus είναι δυο ξωτικά που εργάζονται το δωδεκαήμερο των Χριστουγέννων με μερική απασχόληση, λόγω της κρίσης που υπάρχει στην αγορά εργασίας, στο εργαστήρι του Άγιου Βασίλη στο Ρόβανιεμι, το «χωριό του Άϊ - Βασίλη», στη Φιλανδία.
Παραμονή πρωτοχρονιάς πρέπει να φορτώσουν ένα από τα  έλκηθρα του Άϊ - Βασίλη με 10 μικρά δώρα βάρους 5 κιλών το καθένα και 10 μεγάλα δώρα βάρους 20 κιλών το καθένα. Τα δυο ξωτικά  δεν έχουν την ίδια απόδοση στο κουβάλημα , αυτό φαίνεται και στον παρακάτω πίνακα όπου βλέπουμε το χρόνο που χρειάζεται το κάθε ξωτικό για να φορτώσει στο έλκηθρο  ένα μικρό δώρο όσο και ένα μεγάλο δώρο.
Εάν ξεκίνησαν να φορτώνουν το έλκηθρο στις 10 η ώρα το πρωί, σε πόση ώρα, το λιγότερο, μπορούν να φορτώσουν όλα τα δώρα στο έλκηθρο;
Πηγή: Crux Μagazine

7 σχόλια:

  1. Έστω ότι οJohann κουβάλησε $X$ των $5 kg$ και $Y$ των $20kg$ και ο Klaus $10-X$ των $5kg$ και $10-Y$ των $20kg$. Για να υπάρχει εκμετάλλευση του χρόνου πρέπει να ισχύει:
    $1X+6Y=3(10-X)+5(10-Y) \Rightarrow $ $4X+11Y=80 \Rightarrow $ $Y= \dfrac{80-4X}{11}$.
    Επειδή οι $X,Y$ είναι ακέραιοι, άρα $X=9$ και $Y=4$. Άρα ο ελάχιστος χρόνος είναι:

    $9*1+4*6=33 min$ $(=1*3+5*6=33 min)$

    ΑπάντησηΔιαγραφή
    Απαντήσεις
    1. Πολύ σωστά Ευθύμη. Συγχαρητήρια!!

      Διαγραφή
    2. Γιατί αποκλείεται η περίπτωση κάποιος να έχει τελειώσει γρηγορότερα από τον άλλον; Αν ας πούμε ο Klaus έκανε 2 λεπτά αντί για 1, για το μικρό δώρο, οι χρόνοι τους δεν θα ήταν ίδιοι.

      Διαγραφή
    3. Αυτό το σχόλιο αφαιρέθηκε από τον συντάκτη.

      Διαγραφή
    4. Κατ΄ αρχάς είπαμε και οι δύο Klaus ενώ ενοούμε τον Johann. Στην περίπτωση λοιπόν που ο Johann έκανε 2 λεπτά αντί για 1, για το μικρό δώρο, o βέλτιστος χρόνος είναι 38 λεπτά (με 10 και 3 ή 9 και 3 δώρα γι' αυτόν). Σε κάθε περίπτωση οι χρόνοι των Johann και Klaus δεν θα είναι ίδιοι (38 και 35 ή 36 και 38 αντίστοιχα). Αυτό το 38 δεν προέκυψε εξισώνοντας τους χρόνους και δεν κατάλαβα ακόμα πώς θα μπορούσε να προκύψει (με τρόπο εκτός του γραμμικού προγραμματισμού).

      Διαγραφή
  2. Και μια προγραμματιστική λύση με R

    fn <- function(x) {
    f1 <- x[1] + 6*x[2]
    f2 <- 3*(10-x[1]) + 5*(10-x[2])
    max(f1, f2)
    }

    library(rgenoud)
    genoud(fn, nvars=2, Domains=matrix(c(0,0,10,10),nrow=2), data.type.int=TRUE)

    ΑΠΟΤΕΛΕΣΜΑ (οι μεταβλητές είναι τα δώρα που θα κουβαλήσει ο Johann)

    value
    [1] 33

    par
    [1] 9 4

    ΑπάντησηΔιαγραφή