Παρακάτω θα δούμε ένα πρόγραμμα στο Excel VBA ότι λύνει μια μικρή περίπτωση α πρόβλημα με το σακίδιο.
Ορισμός: Δεδομένου ενός συνόλου στοιχείων, το καθένα με βάρος και τιμή, καθορίστε τα στοιχεία που θα συμπεριληφθούν σε μια συλλογή, έτσι ώστε η συνολική αξία να είναι όσο το δυνατόν μεγαλύτερη και το συνολικό βάρος να είναι μικρότερο από ένα δεδομένο όριο. Πήρε το όνομά του από το πρόβλημα που αντιμετωπίζει κάποιος που περιορίζεται από ένα σακίδιο σταθερού μεγέθους και πρέπει να το γεμίσει με τα πιο χρήσιμα αντικείμενα.
Παράδειγμα: 5 στοιχεία με βάρη, τιμές και όριο όπως δίνονται.
Στο Excel αυτό το πρόβλημα φαίνεται ως εξής:
1. Πρώτον, δηλώνουμε πέντε μεταβλητές τύπου Double με όριο ονομάτων, βάρος, τιμή, totalWeight και μέγιστοValue.
Όριο μειώσεως ως διπλό, βάρος ως διπλό, τιμή ως διπλό, συνολικό βάρος ως διπλό, μέγιστη τιμή ως διπλό
2. Στη συνέχεια, δηλώνουμε πέντε μεταβλητές τύπου Integer με ονόματα i, j, k, l, m.
Dim i, j, k, l, m Ως ακέραιος
3. Αρχικοποιούμε δύο μεταβλητές. Αρχικοποιούμε το όριο μεταβλητών με την τιμή του κελιού D6. Αρχικοποιούμε τη μεταβλητή maximumValue με τιμή 0.
όριο = Εύρος ("D6"). τιμή
μέγιστη τιμή = 0
4. Στη συνέχεια, ελέγχουμε κάθε πιθανή λύση. Μπορούμε είτε να συμπεριλάβουμε ένα στοιχείο (1) είτε να το αφήσουμε εκτός (0). Ξεκινάμε 5 για τους επόμενους βρόχους. Ένα για κάθε είδος.
Για i = 0 έως 1
Για j = 0 έως 1
Για k = 0 έως 1
Για l = 0 έως 1
Για m = 0 έως 1
5. Υπολογίζουμε το βάρος και την τιμή μιας πιθανής λύσης.
βάρος = 12 * i + 2 * j + 1 * k + 1 * l + 4 * m
τιμή = 4 * i + 2 * j + 2 * k + 1 * l + 10 * m
6. Μόνο εάν η τιμή είναι υψηλότερη από τη μέγιστη τιμή και το βάρος είναι χαμηλότερο από το όριο, βρήκαμε μια νέα καλύτερη λύση.
Εάν τιμή> μέγιστη τιμή και βάρος <= όριο Τότε
7. Εάν ισχύει, γράφουμε τη νέα λύση στη σειρά 4, το βάρος στο totalWeight και την τιμή στο maximumValue.
Εύρος ("B4"). Τιμή = i
Εύρος ("C4"). Τιμή = j
Εύρος ("D4"). Τιμή = k
Εύρος ("Ε4"). Τιμή = l
Εύρος ("F4"). Τιμή = m
συνολικό βάρος = βάρος
maximumValue = τιμή
8. Μην ξεχάσετε να κλείσετε τη δήλωση If.
Τέλος εαν
9. Μην ξεχάσετε να κλείσετε τους βρόχους 5 For Next.
Επόμενο μ
Επόμενο λ
Επόμενο κ
Επόμενο j
Επόμενο i
Το Excel VBA ελέγχει κάθε πιθανή λύση με αυτόν τον τρόπο και ως αποτέλεσμα η βέλτιστη λύση θα εμφανιστεί στη σειρά 4. Θυμηθείτε, 1 σημαίνει ότι συμπεριλαμβάνουμε ένα στοιχείο, 0 σημαίνει ότι το αφήνουμε εκτός.
10. Τέλος, γράψτε totalWeight και maximumValue της βέλτιστης λύσης στα αντίστοιχα κελιά Β6 και Β8.
Εύρος ("B6"). Αξία = συνολικό βάρος
Εύρος ("B8"). Τιμή = μέγιστη τιμή
11. Δοκιμάστε το πρόγραμμα.
Αποτέλεσμα:
Συμπέρασμα: είναι βέλτιστο να συμπεριληφθούν τα τέσσερα τελευταία στοιχεία με μέγιστη τιμή 15. Αυτή η λύση με συνολικό βάρος 2 + 1 + 1 + 4 = 8 δεν υπερβαίνει το όριο των 15.
Σημείωση: κάνοντας μεταβλητά τα βάρη και τις τιμές μπορείτε να λύσετε οποιοδήποτε πρόβλημα σακιδίου αυτού του μεγέθους (δείτε το αρχείο Excel που μπορείτε να κατεβάσετε).
