Ready to put your newfound language skills into use? Get 40% off CodeCrafter's real-world proficiency projects!

Διεκδίκησε την έκπτωσή σου

Διαδρομές

Ruby

Ασκήσεις

Σακίδιο

Δύσκολο

Εισαγωγή

Η Lhakpa είναι Σέρπα, οδηγός βουνού και αχθοφόρος. Έπειτα από μήνες προσεκτικού σχεδιασμού, η αποστολή για την οποία εργάζεται η Lhakpa ετοιμάζεται να ξεκινήσει. Θα πληρωθεί την τιμή όσων μετέφερε στο βασικό στρατόπεδο.

Μπροστά της βρίσκονται πολλά αντικείμενα, καθένα με μια τιμή και ένα βάρος. Η Lhakpa θα έπαιρνε ευχαρίστως όλα τα αντικείμενα, αλλά το σακίδιό της μπορεί να χωρέσει μόνο ένα περιορισμένο βάρος.

Οδηγίες

Η αποστολή σου είναι να καθορίσεις ποια αντικείμενα θα πάρει, ώστε η συνολική τιμή της επιλογής της να μεγιστοποιηθεί, λαμβάνοντας υπόψη τη χωρητικότητα του σακιδίου.

Τα αντικείμενα θα αναπαρίστανται ως μια λίστα αντικειμένων. Κάθε αντικείμενο θα έχει βάρος και τιμή. Όλες οι τιμές που δίνονται θα είναι αυστηρά θετικές. Η Lhakpa μπορεί να πάρει μόνο ένα από κάθε αντικείμενο.

Για παράδειγμα:

Items: [
  { "weight": 5, "value": 10 },
  { "weight": 4, "value": 40 },
  { "weight": 6, "value": 30 },
  { "weight": 4, "value": 50 }
]

Knapsack Maximum Weight: 10

Για τα παραπάνω, το πρώτο αντικείμενο έχει βάρος 5 και τιμή 10, το δεύτερο αντικείμενο έχει βάρος 4 και τιμή 40, και ούτω καθεξής. Σε αυτό το παράδειγμα, η Lhakpa πρέπει να πάρει το δεύτερο και το τέταρτο αντικείμενο για να μεγιστοποιήσει την τιμή της, η οποία, σε αυτή την περίπτωση, είναι 90. Δεν μπορεί να πάρει περισσότερα από 90, καθώς το σακίδιό της έχει όριο βάρους 10.