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

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

Διαδρομές

Haskell

Ασκήσεις

Σακίδιο

Μέτριο

Εισαγωγή

Ο Bob είναι κλέφτης. Έπειτα από μήνες προσεκτικού σχεδιασμού, καταφέρνει επιτέλους να παραβιάσει τα συστήματα ασφαλείας ενός πολυτελούς καταστήματος.

Μπροστά του βρίσκονται πολλά αντικείμενα, καθένα με μια αξία και ένα βάρος. Ο Bob θα έπαιρνε ευχαρίστως όλα τα αντικείμενα, αλλά το σακίδιό του μπορεί να χωρέσει μόνο περιορισμένο βάρος. Ο Bob πρέπει να σκεφτεί προσεκτικά ποια αντικείμενα να πάρει, ώστε να μεγιστοποιηθεί η συνολική αξία της επιλογής του.

Οδηγίες

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

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

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

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, και ούτω καθεξής. Σε αυτό το παράδειγμα, ο Bob θα πρέπει να πάρει το δεύτερο και το τέταρτο αντικείμενο για να μεγιστοποιήσει τη συνολική τιμή της επιλογής του, η οποία, στην περίπτωση αυτή, είναι 90. Δεν μπορεί να έχει συνολική τιμή μεγαλύτερη από 90, καθώς το σακίδιό του έχει όριο βάρους 10.