Ελάχιστα δρομολόγια

[Al.Koutsouridis]

Από το λατομείο στο μαρμαράδικο χρειάζεται να μεταφερθούν μεγάλα και μικρά κομμάτια μαρμάρου. Η μεταφορά των μαρμάρων γίνεται με φορτηγά, το καθένα από τα οποία χωράει μικρά κομμάτια και έχει μέγιστο φορτίο τόνους. Τα μικρά κομμάτια έχουν βάρος τόνους, τα μεγάλα κομμάτια τόνους και καταλαμβάνουν χώρο όσο μικρά. Να βρείτε τον ελάχιστο αριθμό δρομολογίων που χρειάζονται για την μεταφορά όλων των κομματιών μαρμάρου.

[Demetres]

Τα κομμάτια που έχω αντιστοιχούν σε μικρά κομμάτια. Δεν μπορώ λοιπόν να τα κουβαλήσω σε διαδρομές ή λιγότερες αφού .

Μπορώ όμως να το κάνω με δρομολόγια ως εξής:

Στα δρομολόγια θα κουβαλήσω από μικρά κομμάτια και μεγάλα. (Το συνολικό βάρος είναι ακριβώς τόνοι. Επίσης, ο συνολικός χώρος που καταλαμβάνουν είναι όσο μικρά κομμάτια, οπότε χωράνε στο φορτηγό.)

Στα δρομολόγια θα κουβαλήσω από μικρά κομμάτια. (Συνολικό βάρος μικρότερο των τόνων.)

Στο τελευταίο δρομολόγιο θα κουβαλήσω μικρά κομμάτια.

Συνολικά τα έχω κουβαλήσει όλα.