Το πρόβλημα του κλασματικού σακιδίου στη C++ αναφέρεται στον προσδιορισμό ενός τρόπου πλήρωσης μιας τσάντας με αντικείμενα δεδομένου βάρους και κέρδους με τέτοιο τρόπο ώστε η τσάντα να περιέχει τη μέγιστη τιμή χωρίς να υπερβαίνει το μέγιστο όριο.
Πώς να λύσετε το πρόβλημα του κλασματικού σακιδίου στη C++
Δεδομένου ενός συνόλου αντικειμένων, το καθένα με το δεδομένο βάρος και κέρδος, προσδιορίστε κάθε αριθμό αντικειμένων με τέτοιο συνδυασμό ώστε το συνολικό βάρος των αντικειμένων να είναι μικρότερο από το μέγιστο όριο της τσάντας, αλλά η τιμή πρέπει να διατηρείται όσο το δυνατόν μεγαλύτερη.
Αλγόριθμος για την υλοποίηση του προβλήματος του κλασματικού σακιδίου
Η λειτουργία του αλγορίθμου Knapsack μπορεί να γίνει κατανοητή μέσα από τα ακόλουθα σημεία:
- Πάρτε δύο σειρές βάρους και κέρδους.
- Ορίστε τη μέγιστη τιμή σάκου σε W.
- Προσδιορίστε την πυκνότητα λαμβάνοντας τον λόγο και των δύο παραμέτρων.
- Ταξινομήστε τα στοιχεία με φθίνουσα σειρά πυκνότητας.
- Προσθέστε τιμές μέχρι να γίνει <=W.
Η άπληστη προσέγγιση για την επίλυση του προβλήματος του κλασματικού σακιδίου
Η άπληστη προσέγγιση στοχεύει να κάνει ιδανικές επιλογές σε κάθε βήμα, οδηγώντας στην ιδανική λύση στο τέλος. Επιλύει προβλήματα βήμα προς βήμα οδηγώντας σε συμπεράσματα αντί να καταλήγει μόνο στο τέλος. Αυτός είναι ένας πηγαίος κώδικας για την υλοποίηση μιας λύσης στο πρόβλημα του κλασματικού σακιδίου στη C++:
#include
χρησιμοποιώντας χώρο ονομάτων std ;
struct Αντικείμενο {
ενθ αξία, βάρος ;
Αντικείμενο ( ενθ αξία, ενθ βάρος )
: αξία ( αξία ) , βάρος ( βάρος )
{
}
} ;
bool cmp ( struct Αντικείμενο x, struct Αντικείμενο y )
{
διπλό Α'1 = ( διπλό ) Χ. αξία / Χ. βάρος ;
διπλό Α2 = ( διπλό ) και. αξία / και. βάρος ;
ΕΠΙΣΤΡΟΦΗ Α'1 > Α2 ;
}
διπλό κλασματικό σακίδιο ( struct Αντικείμενο αρ [ ] ,
ενθ ΣΕ, ενθ Μέγεθος )
{
είδος ( arr, arr + μέγεθος, cm ) ;
ενθ curWeight = 0 ;
διπλό τελική αξία = 0,0 ;
Για ( ενθ Εγώ = 0 ; Εγώ < Μέγεθος ; Εγώ ++ ) {
αν ( curWeight + αρ [ Εγώ ] . βάρος <= ΣΕ ) {
curWeight + = αρ [ Εγώ ] . βάρος ;
τελική αξία + = αρ [ Εγώ ] . αξία ;
}
αλλού {
ενθ παραμένει = ΣΕ - curWeight ;
τελική αξία + = αρ [ Εγώ ] . αξία
* ( ( διπλό ) παραμένει
/ αρ [ Εγώ ] . βάρος ) ;
Διακοπή ;
}
}
ΕΠΙΣΤΡΟΦΗ τελική αξία ;
}
ενθ σε = 60 ;
Αντικείμενο αρ [ ] = { { 100 , είκοσι } ,
{ 380 , 40 } ,
{ 140 , 10 } ,
{ 180 , 30 } } ;
ενθ Μέγεθος = μέγεθος του ( αρ ) / μέγεθος του ( αρ [ 0 ] ) ;
cout << 'Μέγιστο κέρδος ='
<< κλασματικό σακίδιο ( arr, v, μέγεθος ) ;
ΕΠΙΣΤΡΟΦΗ 0 ;
}
Σε αυτόν τον κώδικα, ορίζεται μια δομή αντικειμένου που έχει αποθηκευμένες τιμές βάρους και κέρδους. Το bool cmp() χρησιμοποιείται για να γίνει σύγκριση μεταξύ δύο αντικειμένων με βάση την αναλογία βάρους και τιμής δύο αντικειμένων. Ο πίνακας είναι διατεταγμένος με φθίνουσα σειρά και η τιμή συνεχίζει να προστίθεται μέχρι να φτάσει στο μέγιστο. Εάν η τρέχουσα τιμή είναι επιτρεπτή και εντός του ορίου, προστίθεται, διαφορετικά η μειωμένη αναλογία της προστίθεται στη σακούλα. Το μέγεθος του βάρους και της αξίας εισάγεται στον κύριο κωδικό και το μέγιστο κέρδος εκτυπώνεται στην έξοδο.
Το μέγιστο κέρδος που αποθηκεύτηκε στο σνακ είναι 580.
συμπέρασμα
Το πρόβλημα του κλασματικού σακιδίου στη C++ αναφέρεται στον προσδιορισμό ενός τρόπου πλήρωσης μιας τσάντας με αντικείμενα δεδομένου βάρους και κέρδους με τέτοιο τρόπο ώστε η τσάντα να περιέχει τη μέγιστη τιμή χωρίς να υπερβαίνει το μέγιστο όριο. Αυτό μπορεί να επιτευχθεί με την άπληστη προσέγγιση που στοχεύει να κάνει ιδανικές επιλογές σε κάθε βήμα, οδηγώντας στην ιδανική λύση στο τέλος.