Εισαγωγή
Η 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.
Ειδικές σημειώσεις για WebAssembly
Τα αντικείμενα περνούν μέσω της γραμμικής μνήμης, με το πρώτο αντικείμενο στο offset 0.
Κάθε αντικείμενο αναπαρίσταται ως ένα ζεύγος από 32-bit ακέραιους.
Ο πρώτος αριθμός στο ζεύγος είναι το βάρος και ο δεύτερος είναι η τιμή.
Για παράδειγμα, θεώρησε μια λίστα με δύο αντικείμενα, όπου το πρώτο έχει weight=1, value=2 και το δεύτερο weight=5, value=8.
Η λίστα θα έμοιαζε λοιπόν έτσι στη μνήμη:
| 00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 | 13 | 14 | 15 |
| - item 1 weight - | -- item 1 value - | - item 2 weight - | -- item 2 value - |
|0x01,0x00,0x00,0x00|0x02,0x00,0x00,0x00|0x05,0x00,0x00,0x00|0x08,0x00,0x00,0x00|
Αν το επιλέξεις, μπορείς να αντικαταστήσεις τις διευθύνσεις της γραμμικής μνήμης που χρησιμοποιούνται για την είσοδο.
