Πρόβλημα κλασματικού σακιδίου: Άπληστος αλγόριθμος με Παράδειγμα
Τι είναι η Greedy Strategy;
Οι άπληστοι αλγόριθμοι είναι σαν αλγόριθμοι δυναμικού προγραμματισμού που χρησιμοποιούνται συχνά για την επίλυση βέλτιστων προβλημάτων (βρίσκουν τις καλύτερες λύσεις του προβλήματος σύμφωνα με ένα συγκεκριμένο κριτήριο).
Οι άπληστοι αλγόριθμοι εφαρμόζουν βέλτιστες τοπικές επιλογές με την ελπίδα ότι αυτές οι επιλογές θα οδηγήσουν σε μια βέλτιστη συνολική λύση για το πρόβλημα που πρέπει να λυθεί. Οι άπληστοι αλγόριθμοι συχνά δεν είναι πολύ δύσκολοι στη ρύθμιση, γρήγοροι (η χρονική πολυπλοκότητα είναι συχνά μια γραμμική συνάρτηση ή πολύ μια συνάρτηση δεύτερης τάξης). Επιπλέον, αυτά τα προγράμματα δεν είναι δύσκολο να εντοπιστούν σφαλμάτων και χρησιμοποιούν λιγότερη μνήμη. Όμως τα αποτελέσματα δεν είναι πάντα η βέλτιστη λύση.
Οι άπληστες στρατηγικές χρησιμοποιούνται συχνά για την επίλυση του προβλήματος της συνδυαστικής βελτιστοποίησης δημιουργώντας μια επιλογή A. Η επιλογή Α δημιουργείται επιλέγοντας κάθε στοιχείο Ai του A μέχρι να ολοκληρωθεί (αρκετά n συστατικά). Για κάθε Ai, επιλέγετε το Ai βέλτιστα. Με αυτόν τον τρόπο, είναι πιθανό στο τελευταίο βήμα να μην έχετε τίποτα να επιλέξετε παρά να αποδεχτείτε την τελευταία τιμή που απομένει.
Υπάρχουν δύο κρίσιμα συστατικά των άπληστων αποφάσεων:
- Τρόπος άπληστης επιλογής. Μπορείτε να επιλέξετε ποια λύση είναι η καλύτερη επί του παρόντος και στη συνέχεια να λύσετε το υποπρόβλημα που προκύπτει από την πραγματοποίηση της τελευταίας επιλογής. Η επιλογή των άπληστων αλγορίθμων μπορεί να εξαρτάται από προηγούμενες επιλογές. Αλλά δεν μπορεί να εξαρτάται από οποιαδήποτε μελλοντική επιλογή ή από τις λύσεις υποπροβλημάτων. Ο αλγόριθμος εξελίσσεται με τρόπο που κάνει επιλογές σε βρόχο, συρρικνώνοντας ταυτόχρονα το δεδομένο πρόβλημα σε μικρότερα υποπροβλήματα.
- Βέλτιστη υποδομή. Εκτελείτε τη βέλτιστη υποδομή για ένα πρόβλημα εάν η βέλτιστη λύση αυτού του προβλήματος περιέχει βέλτιστες λύσεις στα υποπροβλήματά του.
Ένας άπληστος αλγόριθμος έχει πέντε στοιχεία:
- Ένα σύνολο υποψηφίων, από τα οποία να δημιουργούνται λύσεις.
- Μια συνάρτηση επιλογής, για να επιλέξετε τον καλύτερο υποψήφιο για προσθήκη στη λύση.
- Μια εφικτή συνάρτηση χρησιμοποιείται για να αποφασίσει εάν ένας υποψήφιος μπορεί να χρησιμοποιηθεί για την κατασκευή μιας λύσης.
- Μια αντικειμενική συνάρτηση, που καθορίζει την τιμή μιας λύσης ή μιας ημιτελούς λύσης.
- Μια λειτουργία αξιολόγησης, που υποδεικνύει πότε βρίσκετε μια ολοκληρωμένη λύση.
The Idea of Greedy One
Με την πρώτη ιδέα, έχετε τα ακόλουθα βήματα του Greedy One:
- Ταξινόμηση με μη αύξουσα σειρά τιμών.
- Με τη σειρά σας, λάβετε υπόψη τα παραγγελθέντα πακέτα, βάλτε το πακέτο εξεταζόμενης στο σακίδιο εάν η υπολειπόμενη χωρητικότητα του σακιδίου είναι αρκετή για να το περιέχει (που σημαίνει ότι το συνολικό βάρος των συσκευασιών που έχουν τοποθετηθεί στο σακίδιο και το βάρος των συσκευασιών εξέτασης δεν υπερβαίνουν η χωρητικότητα του σακιδίου).
Ωστόσο, αυτός ο άπληστος αλγόριθμος δεν δίνει πάντα τη βέλτιστη λύση. Εδώ έχετε ένα αντιπαράδειγμα:
- Οι παράμετροι του προβλήματος είναι: n = 3; M = 19.
- Τα πακέτα: {i = 1; W[i] = 14; V[i] = 20}; {i = 2; W[i] = 6; V[i] = 16}; {i = 3; W[i] = 10; V[i] = 8} -> Μεγάλη αξία αλλά και μεγάλο βάρος.
- Ο αλγόριθμος θα επιλέξει το πακέτο 1 με συνολική τιμή 20, ενώ επιλέγεται η βέλτιστη λύση του προβλήματος (πακέτο 2, πακέτο 3) με συνολική τιμή 24.
The Idea of Greedy Two
Με τη δεύτερη ιδέα, έχετε τα ακόλουθα βήματα του Greedy Two:
- Ταξινόμηση με μη φθίνουσα σειρά βαρών.
- Με τη σειρά σας, λάβετε υπόψη τα παραγγελθέντα πακέτα, βάλτε το πακέτο εξεταζόμενης στο σακίδιο εάν η υπολειπόμενη χωρητικότητα του σακιδίου είναι αρκετή για να το περιέχει (που σημαίνει ότι το συνολικό βάρος των συσκευασιών που έχουν τοποθετηθεί στο σακίδιο και το βάρος των συσκευασιών εξέτασης δεν υπερβαίνουν η χωρητικότητα του σακιδίου).
Ωστόσο, αυτός ο άπληστος αλγόριθμος δεν δίνει πάντα τη βέλτιστη λύση. Εδώ έχετε ένα αντιπαράδειγμα:
- Οι παράμετροι του προβλήματος είναι: n = 3; M = 11.
- Τα πακέτα: {i = 1; W[i] = 5; V[i] = 10}; {i = 2; W[i] = 6; V[i] = 16}; {i = 3; W[i] = 10; V[i] = 28} -> Μικρό βάρος, αλλά η τιμή είναι επίσης πολύ ελαφριά.
- Ο αλγόριθμος θα επιλέξει (πακέτο 1, πακέτο 2) με συνολική τιμή 26, ενώ η βέλτιστη λύση του προβλήματος είναι (πακέτο 3) με συνολική τιμή 28.
The Idea of Greedy Three
Με την τρίτη ιδέα, έχετε τα ακόλουθα βήματα του Greedy Three. Στην πραγματικότητα, αυτός είναι ο πιο ευρέως χρησιμοποιούμενος αλγόριθμος.
- Ταξινόμηση πακέτων με τη σειρά μη αύξησης της αξίας του μοναδιαίου κόστους . Εχεις:
- Με τη σειρά σας, λάβετε υπόψη τα παραγγελθέντα πακέτα, βάλτε το πακέτο εξεταζόμενης στο σακίδιο εάν η υπολειπόμενη χωρητικότητα του σακιδίου είναι αρκετή για να το περιέχει (που σημαίνει ότι το συνολικό βάρος των συσκευασιών που έχουν τοποθετηθεί στο σακίδιο και το βάρος των συσκευασιών εξέτασης δεν υπερβαίνουν η χωρητικότητα του σακιδίου).
Ιδέα: Η άπληστη ιδέα αυτού του προβλήματος είναι ο υπολογισμός του αναλογία του καθενός . Στη συνέχεια, ταξινομήστε αυτές τις αναλογίες με φθίνουσα σειρά. Θα διαλέξεις το υψηλότερο πακέτο και η χωρητικότητα του σακιδίου μπορεί να περιέχει αυτό το πακέτο (remain > wi). Κάθε φορά που τοποθετείται μια συσκευασία στο σακίδιο, θα μειώσει επίσης τη χωρητικότητα του σακιδίου.
Τρόπος επιλογής πακέτων:
- Εξετάστε τη σειρά των μοναδιαίων δαπανών. Επιλέγετε πακέτα ανάλογα με το μειωμένο μοναδιαίο κόστος.
- Ας υποθέσουμε ότι βρήκατε μια μερική λύση: (χ1,…, Χi).
- Η αξία του σακιδίου λαμβάνεται:
- Αντίστοιχο με το βάρος των συσκευασιών που έχουν τοποθετηθεί στο σακίδιο:
- Επομένως, το υπόλοιπο όριο βάρους του σακιδίου είναι:
Βήματα Αλγορίθμου
Βλέπετε ότι αυτό είναι ένα πρόβλημα εύρεσης μέγ. Η λίστα των πακέτων ταξινομείται με φθίνουσα σειρά του κόστους μονάδας για να ληφθεί υπόψη η διακλάδωση.
- Βήμα 1: Η ρίζα του κόμβου αντιπροσωπεύει την αρχική κατάσταση του σακιδίου, όπου δεν έχετε επιλέξει κανένα πακέτο.
- ΣυνολικήΤιμή = 0.
- Το άνω όριο του ριζικού κόμβου UpperBound = M * Μέγιστο κόστος μονάδας.
- Βήμα 2: Η ρίζα του κόμβου θα έχει θυγατρικούς κόμβους που αντιστοιχούν στη δυνατότητα επιλογής του πακέτου με το μεγαλύτερο κόστος μονάδας. Για κάθε κόμβο, υπολογίζετε εκ νέου τις παραμέτρους:
- TotalValue = TotalValue (παλιά) + αριθμός επιλεγμένων πακέτων * αξία κάθε πακέτου.
- M = M (παλιά) – αριθμός επιλεγμένων πακέτων * βάρος κάθε πακέτου.
- UpperBound = TotalValue + M (νέο) * Το μοναδιαίο κόστος του πακέτου που θα εξεταστεί στη συνέχεια.
- Βήμα 3: Στους θυγατρικούς κόμβους, θα δώσετε προτεραιότητα στη διακλάδωση για τον κόμβο που έχει το μεγαλύτερο άνω όριο. Τα παιδιά αυτού του κόμβου αντιστοιχούν στη δυνατότητα επιλογής του επόμενου πακέτου με μεγάλο κόστος μονάδας. Για κάθε κόμβο, πρέπει να υπολογίσετε εκ νέου τις παραμέτρους TotalValue, M, UpperBound σύμφωνα με τον τύπο που αναφέρεται στο βήμα 2.
- Βήμα 4: Επαναλάβετε το βήμα 3 με τη σημείωση: για τους κόμβους με το ανώτερο όριο είναι χαμηλότερες ή ίσες τιμές με το προσωρινό μέγιστο κόστος μιας επιλογής που βρέθηκε, δεν χρειάζεται πλέον να διακλαδώσετε για αυτόν τον κόμβο.
- Βήμα 5: Εάν όλοι οι κόμβοι είναι διακλαδισμένοι ή αποκομμένοι, η πιο ακριβή επιλογή είναι αυτή που πρέπει να αναζητήσετε.
Ψευδοκώδικας για τον αλγόριθμο:
Fractional Knapsack (Array W, Array V, int M) 1. for i <- 1 to size (V) 2. calculate cost[i] <- V[i] / W[i] 3. Sort-Descending (cost) 4. i ← 1 5. while (i <= size(V)) 6. if W[i] <= M 7. M ← M – W[i] 8. total ← total + V[i]; 9. if W[i] > M 10. i ← i+1
Η πολυπλοκότητα του αλγορίθμου:
- Εάν χρησιμοποιείτε έναν απλό αλγόριθμο ταξινόμησης (επιλογή, συννεφάκι…) τότε η πολυπλοκότητα του όλου προβλήματος είναι O(n2).
- Εάν χρησιμοποιείτε γρήγορη ταξινόμηση ή ταξινόμηση συγχώνευσης, τότε η πολυπλοκότητα του όλου προβλήματος είναι O(nlogn).
Java κωδικός για Greedy Three
- Αρχικά, ορίζετε την κλάση KnapsackPackage. Αυτή η κατηγορία έχει ιδιότητες είναι: βάρος, αξία και αντίστοιχο κόστος κάθε συσκευασίας. Το κόστος ιδιοκτησίας αυτής της κλάσης χρησιμοποιείται για την ταξινόμηση εργασίας στον κύριο αλγόριθμο. Η αξία κάθε κόστους είναι το αναλογία κάθε συσκευασίας.
public class KnapsackPackage { private double weight; private double value; private Double cost; public KnapsackPackage(double weight, double value) { super(); this.weight = weight; this.value = value; this.cost = new Double(value / weight); } public double getWeight() { return weight; } public double getValue() { return value; } public Double getCost() { return cost; } }
- Στη συνέχεια δημιουργείτε μια συνάρτηση για την εκτέλεση του αλγόριθμου Greedy Three.
public void knapsackGreProc(int W[], int V[], int M, int n) { KnapsackPackage[] packs = new KnapsackPackage[n]; for (int i = 0; i < n; i ++) { packs[i] = new KnapsackPackage(W[i], V[i]); } Arrays.sort(packs, new Comparator<KnapsackPackage>() { @Override public int compare(KnapsackPackage kPackA, KnapsackPackage kPackB) { return kPackB.getCost().compareTo(kPackA.getCost()); } }); int remain = M; double result = 0d; int i = 0; boolean stopProc = false; while (!stopProc) { if (packs[i].getWeight() <= remain) { remain -= packs[i].getWeight(); result += packs[i].getValue(); System.out.println("Pack " + i + " - Weight " + packs[i].getWeight() + " - Value " + packs[i].getValue()); } if (packs[i].getWeight() > remain) { i ++; } if (i == n) { stopProc = true; } } System.out.println("Max Value:\t" + result); }
Επεξήγηση κωδικού:
- Αρχικοποιήστε το βάρος και την αξία για κάθε συσκευασία σακιδίου.
- Ταξινομήστε τα πακέτα σακιδίων ανά κόστος με φθίνουσα σειρά.
- Εάν επιλέξετε το πακέτο i.
- Αν επιλέξετε τον αριθμό του πακέτου i είναι αρκετό.
- Διακοπή κατά την περιήγηση σε όλα τα πακέτα.
Σε αυτό το σεμινάριο, έχετε δύο παραδείγματα. Ακολουθεί ο κώδικας java για την εκτέλεση του παραπάνω προγράμματος με δύο παραδείγματα:
public void run() { /* * Pack and Weight - Value */ //int W[] = new int[]{15, 10, 2, 4}; int W[] = new int[]{12, 2, 1, 1, 4}; //int V[] = new int[]{30, 25, 2, 6}; int V[] = new int[]{4, 2, 1, 2, 10}; /* * Max Weight */ //int M = 37; int M = 15; int n = V.length; /* * Run the algorithm */ knapsackGreProc(W, V, M, n); }
Έχετε την έξοδο:
- Πρώτο Παράδειγμα:
Pack 0 - Weight 10.0 - Value 25.0 Pack 0 - Weight 10.0 - Value 25.0 Pack 0 - Weight 10.0 - Value 25.0 Pack 2 - Weight 4.0 - Value 6.0 Pack 3 - Weight 2.0 - Value 2.0 Max Value: 83.0
- Δεύτερο Παράδειγμα:
Pack 0 - Weight 4.0 - Value 10.0 Pack 0 - Weight 4.0 - Value 10.0 Pack 0 - Weight 4.0 - Value 10.0 Pack 1 - Weight 1.0 - Value 2.0 Pack 1 - Weight 1.0 - Value 2.0 Pack 1 - Weight 1.0 - Value 2.0 Max Value: 36.0
Αναλύστε το πρώτο παράδειγμα:
- Οι παράμετροι του προβλήματος είναι: n = 4; M = 37.
- Τα πακέτα: {i = 1; W[i] = 15; V[i] = 30; Κόστος = 2.0}; {i = 2; W[i] = 10; V[i] = 25; Κόστος = 2.5}; {i = 3; W[i] = 2; V[i] = 4; Κόστος = 1.0}; {i = 4; W[i] = 4; V[i] = 6; Κόστος = 1.5}.
- Ταξινομείτε τα πακέτα με τη σειρά μη αύξησης της αξίας του μοναδιαίου κόστους. Έχετε: {i = 2} -> {i = 1} -> {i = 4} -> {i = 3}.
Βήματα για την εφαρμογή αλγορίθμου για το πρώτο παράδειγμα:
- Ορισμός x1, x2, x3, x4 είναι ο αριθμός κάθε επιλεγμένου πακέτου, που αντιστοιχεί στο πακέτο {i = 2} -> {i = 1} -> {i = 4} -> {i = 3}.
- Η ρίζα του κόμβου N αντιπροσωπεύει την κατάσταση που δεν έχετε επιλέξει κανένα πακέτο. Επειτα:
- ΣυνολικήΤιμή = 0.
- M = 37 (όπως προτείνεται).
- UpperBound = 37 * 2.5 = 92.5, εκ των οποίων 37 είναι M και 2.5 είναι το κόστος μονάδας του πακέτου {i = 2}.
- Με το πακέτο {i = 2}, έχετε 4 δυνατότητες: επιλέξτε 3 πακέτο {i = 2} (x1 = 3); επιλέξτε 2 πακέτο {i = 2} (x1 = 2); επιλέξτε 1 πακέτο {i = 2} (x1 = 1) και όχι επιλέξτε πακέτο {i = 2} (x1 = 0). Σύμφωνα με αυτές τις 4 δυνατότητες, διακλαδίζετε τον ριζικό κόμβο N σε 4 παιδιά N[1], N[2], N[3] και N[4].
- Για τον θυγατρικό κόμβο N1, έχετε:
- TotalValue = 0 + 3 * 25 = 75, όπου 3 είναι ο αριθμός του πακέτου {i = 2} που έχει επιλεγεί και 25 είναι η τιμή κάθε πακέτου {i = 2}.
- M = 37 – 3 * 10 = 7, όπου 37 είναι η αρχική ποσότητα του σακιδίου, 3 είναι ο αριθμός του πακέτου {i = 2}, 10 είναι το βάρος κάθε πακέτου {i = 2}.
- UpperBound = 75 + 7 * 2 = 89, όπου 75 είναι TotalValue, 7 είναι το υπόλοιπο βάρος του σακιδίου και 2 είναι το κόστος μονάδας του πακέτου {i = 1}.
- Ομοίως, μπορείτε να υπολογίσετε τις παραμέτρους για τους κόμβους N[2], N[3] και N[4], στους οποίους το Upper Bound είναι 84, 79 και 74 αντίστοιχα.
- Μεταξύ των κόμβων N[1], N[2], N[3] και N[4], ο κόμβος N[1] έχει το μεγαλύτερο Upper Bound, επομένως θα διακλαδώσετε πρώτα τον κόμβο N[1] με την ελπίδα ότι θα υπάρξει καλό σχέδιο από αυτή την κατεύθυνση.
- Από τον κόμβο N[1], έχετε μόνο έναν θυγατρικό κόμβο N[1-1] που αντιστοιχεί σε x2 = 0 (λόγω του υπολειπόμενου βάρους του σακιδίου είναι 7, ενώ το βάρος κάθε πακέτου {i = 1} είναι 15) . Αφού προσδιορίσετε τις παραμέτρους για το κουμπί N[1-1] έχετε το Upper Bound του N[1-1] είναι 85.5.
- Συνεχίζετε τη διακλάδωση του κόμβου N[1-1]. Ο κόμβος N[1-1] έχει 2 παιδιά N[1-1-1] και N[1-1-2] που αντιστοιχούν σε x3 = 1 και x3 = 0. Αφού προσδιορίσετε τις παραμέτρους για αυτούς τους δύο κόμβους, βλέπετε ότι το Το ανώτερο όριο του N[1-1-1] είναι 84 και αυτό του N[1-1-2] είναι 82, επομένως συνεχίζετε τη διακλάδωση του κόμβου N[1-1-1].
- Ο κόμβος N[1-1-1] έχει δύο παιδιά, τα N[1-1-1-1] και N[1-1-1-2], που αντιστοιχούν σε x4 = 1 και x4 = 0. Πρόκειται για δύο κόμβους φύλλων (που αντιπροσωπεύει την επιλογή) γιατί για κάθε κόμβο έχει επιλεγεί ο αριθμός των πακέτων. Σε ποιον κόμβο N[1-1-1-1] αντιπροσωπεύει την επιλογή x1 = 3, x2 = 0, x3 = 1 και x4 = 1 για το 83, ενώ ο κόμβος N[1-1-1-2] αντιπροσωπεύει την επιλογή x1 = 3, x2 = 0, x3 = 1 και x4 = 01 στο 81. Άρα η προσωρινή μέγιστη τιμή εδώ είναι 83.
- Επιστρέφοντας στον κόμβο N[1-1-2], βλέπετε ότι το Άνω Όριο του N[1-1-2] είναι 82 < 83, επομένως περικόπτετε τον κόμβο N[1-1-2].
- Επιστρέφοντας στον κόμβο N2, βλέπετε ότι το Upper Bound του N2 είναι 84 > 83, οπότε συνεχίζετε τη διακλάδωση του κόμβου N2. Ο κόμβος N2 έχει δύο παιδιά N[2-1] και N[2-2] που αντιστοιχούν σε x2 = 1 και x2 = 0. Αφού υπολογίσετε τις παραμέτρους για N[2-1] και N[2-2], βλέπετε το Άνω Όριο του N[2-1] είναι 83 και αυτό του N[2-2] είναι 75.25. Καμία από αυτές τις τιμές δεν είναι μεγαλύτερη από 83, επομένως και οι δύο κόμβοι έχουν περικοπεί.
- Τέλος, οι κόμβοι N3 και N4 περικόπτονται επίσης.
- Έτσι, όλοι οι κόμβοι στο δέντρο είναι διακλαδισμένοι ή κομμένοι, οπότε η καλύτερη προσωρινή λύση είναι αυτή που πρέπει να αναζητήσετε. Αντίστοιχα, πρέπει να επιλέξετε 3 πακέτα {i = 2}, 1 πακέτο {i = 4} και ένα πακέτο {i = 3} με συνολική αξία 83, το συνολικό βάρος είναι 36.
Με την ίδια ανάλυση του δεύτερου παραδείγματος, έχετε το αποτέλεσμα: επιλέξτε πακέτο 4 (3 φορές) και πακέτο 5 (3 φορές).
Python3 κωδικός για Greedy Three
- Αρχικά, ορίζετε την κλάση KnapsackPackage.
class KnapsackPackage(object): """ Knapsack Package Data Class """ def __init__(self, weight, value): self.weight = weight self.value = value self.cost = value / weight def __lt__(self, other): return self.cost < other.cost
- Στη συνέχεια δημιουργείτε μια συνάρτηση για την εκτέλεση του αλγόριθμου Greedy Three.
class FractionalKnapsack(object): def __init__(self): def knapsackGreProc(self, W, V, M, n): packs = [] for i in range(n): packs.append(KnapsackPackage(W[i], V[i])) packs.sort(reverse = True) remain = M result = 0 i = 0 stopProc = False while (stopProc != True): if (packs[i].weight <= remain): remain -= packs[i].weight; result += packs[i].value; print("Pack ", i, " - Weight ", packs[i].weight, " - Value ", packs[i].value) if (packs[i].weight > remain): i += 1 if (i == n): stopProc = True print("Max Value:\t", result)
Επεξήγηση κωδικού:
- Αρχικοποιήστε το βάρος και την αξία για κάθε συσκευασία σακιδίου.
- Ταξινομήστε τα πακέτα σακιδίων ανά κόστος με φθίνουσα σειρά.
- Εάν επιλέξετε το πακέτο i.
- Αν επιλέξετε τον αριθμό του πακέτου i είναι αρκετό.
- Διακοπή κατά την περιήγηση σε όλα τα πακέτα.
Ιδού Python3 κώδικας για την εκτέλεση του παραπάνω προγράμματος με το πρώτο παράδειγμα:
if __name__ == "__main__": W = [15, 10, 2, 4] V = [30, 25, 2, 6] M = 37 n = 4 proc = FractionalKnapsack() proc.knapsackGreProc(W, V, M, n)
Έχετε την έξοδο:
Pack 0 - Weight 10 - Value 25 Pack 0 - Weight 10 - Value 25 Pack 0 - Weight 10 - Value 25 Pack 2 - Weight 4 - Value 6 Pack 3 - Weight 2 - Value 2 Max Value: 83
Κωδικός C# για Greedy Three
- Αρχικά, ορίζετε την κλάση KnapsackPackage.
using System; namespace KnapsackProblem { public class KnapsackPackage { private double weight; private double value; private double cost; public KnapsackPackage(double weight, double value) { this.weight = weight; this.value = value; this.cost = (double) value / weight; } public double Weight { get { return weight; } } public double Value { get { return value; } } public double Cost { get { return cost; } } } }
- Στη συνέχεια δημιουργείτε μια συνάρτηση για την εκτέλεση του αλγόριθμου Greedy Three.
using System; namespace KnapsackProblem { public class FractionalKnapsack { public FractionalKnapsack() { } public void KnapsackGreProc(int[] W, int[] V, int M, int n) { KnapsackPackage[] packs = new KnapsackPackage[n]; for (int k = 0; k < n; k++) packs[k] = new KnapsackPackage(W[k], V[k]); Array.Sort<KnapsackPackage>(packs, new Comparison<KnapsackPackage>( (kPackA, kPackB) => kPackB.Cost.CompareTo(kPackA.Cost))); double remain = M; double result = 0d; int i = 0; bool stopProc = false; while (!stopProc) { if (packs[i].Weight <= remain) { remain -= packs[i].Weight; result += packs[i].Value; Console.WriteLine("Pack " + i + " - Weight " + packs[i].Weight + " - Value " + packs[i].Value); } if (packs[i].Weight > remain) { i++; } if (i == n) { stopProc = true; } } Console.WriteLine("Max Value:\t" + result); } } }
Επεξήγηση κωδικού:
- Αρχικοποιήστε το βάρος και την αξία για κάθε συσκευασία σακιδίου.
- Ταξινομήστε τα πακέτα σακιδίων ανά κόστος με φθίνουσα σειρά.
- Εάν επιλέξετε το πακέτο i.
- Αν επιλέξετε τον αριθμό του πακέτου i είναι αρκετό.
- Διακοπή κατά την περιήγηση σε όλα τα πακέτα.
Εδώ είναι ο κώδικας C# για να εκτελέσετε το παραπάνω πρόγραμμα με το πρώτο παράδειγμα:
public void run() { /* * Pack and Weight - Value */ int[] W = new int[]{15, 10, 2, 4}; //int[] W = new int[] { 12, 2, 1, 1, 4 }; int[] V = new int[]{30, 25, 2, 6}; //int[] V = new int[] { 4, 2, 1, 2, 10 }; /* * Max Weight */ int M = 37; //int M = 15; int n = V.Length; /* * Run the algorithm */ KnapsackGreProc(W, V, M, n); }
Έχετε την έξοδο:
Pack 0 - Weight 10 - Value 25 Pack 0 - Weight 10 - Value 25 Pack 0 - Weight 10 - Value 25 Pack 2 - Weight 4 - Value 6 Pack 3 - Weight 2 - Value 2 Max Value: 83
Αντιπαράδειγμα Greedy Three
Ο αλγόριθμος του Greedy Three επιλύεται γρήγορα και μπορεί επίσης να είναι βέλτιστος σε ορισμένες περιπτώσεις. Ωστόσο, σε ορισμένες ειδικές περιπτώσεις, δεν δίνει τη βέλτιστη λύση. Εδώ έχετε ένα αντιπαράδειγμα:
- Οι παράμετροι του προβλήματος είναι: n = 3; M = 10.
- Τα πακέτα: {i = 1; W[i] = 7; V[i] = 9; Κόστος = 9/7}; {i = 2; W[i] = 6; V[i] = 6; Κόστος = 1}; {i = 3; W[i] = 4; V[i] = 4; Κόστος = 1}.
- Ο αλγόριθμος θα επιλέξει (πακέτο 1) με συνολική τιμή 9, ενώ η βέλτιστη λύση του προβλήματος είναι (πακέτο 2, πακέτο 3) με συνολική τιμή 10.
Εδώ είναι ο κώδικας java για την εκτέλεση του παραπάνω προγράμματος με το αντί-παράδειγμα:
public void run() { /* * Pack and Weight - Value */ int W[] = new int[]{7, 6, 4}; int V[] = new int[]{9, 6, 4}; /* * Max Weight */ int M = 10; int n = V.length; /* * Run the algorithm */ knapsackGreProc(W, V, M, n); }
Εδώ είναι το αποτέλεσμα:
Pack 0 - Weight 7.0 - Value 9.0 Max Value: 9.0
Αυτό οφείλεται στο πρόβλημα του Fractional Knapsack.