Επιλυτής προβλήματος σακιδίου 0/1

Επιλυτής προβλήματος σακιδίου 0/1

Βρείτε μία επιλογή μέγιστης συνολικής αξίας για το πρόβλημα σακιδίου 0/1, με ακέραια βάρη και χωρητικότητα.

Εισαγάγετε ένα αντικείμενο ανά γραμμή ως όνομα,βάρος,αξία με κόμματα ASCII. Τα ονόματα πρέπει να είναι μοναδικά μετά την αφαίρεση εξωτερικών κενών, μη κενά και χωρίς κόμματα. Επιτρέπονται κενά γύρω από τα πεδία· οι κενές γραμμές αγνοούνται. Χρησιμοποιήστε τελεία στα δεκαδικά.

A,2,6
B,3,10
C,4,12

Επικολλήστε τις τρεις γραμμές παρακάτω και ορίστε χωριστά χωρητικότητα 5: μέγιστη αξία 16, επιλογή A, B. Η αντιγραφή αντιγράφει το αποτέλεσμα· η εκκαθάριση αδειάζει και τη χωρητικότητα.

1–200 αντικείμενα· ακέραια χωρητικότητα 1–5000· ακέραιο βάρος από 1 έως τη χωρητικότητα· μη κενή πεπερασμένη αξία 0–1000000000, και δεκαδική. Ένα υπέρβαρο αντικείμενο απορρίπτει όλη την είσοδο. Όριο κειμένου: 500000 μονάδες κώδικα UTF-16. Κάθε αντικείμενο επιλέγεται το πολύ μία φορά. Εμφανίζονται μόνο μέγιστη αξία και ονόματα, όχι συνολικό βάρος. Σε ακριβή ισοπαλία παραλείπονται τα μεταγενέστερα αντικείμενα: η σειρά μπορεί να αλλάξει τη βέλτιστη επιλογή, χωρίς προτεραιότητα ελάχιστου βάρους. Μόνο μηδενικές αξίες δίνουν 0 και κενή επιλογή. Τα δεκαδικά μπορεί να στρογγυλοποιηθούν· μετατρέψτε ακριβή ποσά σε ακέραιες μονάδες.