0/1 Σακίδιο Διόρθωση Προβλήματος με χρήση του Παραδείγματος Δυναμικού Προγραμματισμού

Τι είναι το πρόβλημα του σακιδίου;

The Πρόβλημα με σακίδιο είναι ένα κλασικό πρόβλημα συνδυαστικής βελτιστοποίησης. Ένα σούπερ μάρκετ n συσκευασίες (n ≤ 100). Συσκευασία i έχει βάρος W[i] ≤ 100 και τιμή V[i] ≤ 100. Ένας κλέφτης δεν μπορεί να μεταφέρει βάρος που υπερβαίνει τη χωρητικότητα M (M ≤ 100). Ποια δέματα πρέπει να πάρει ο κλέφτης για να μεγιστοποιήσει τη συνολική αξία;

εισόδου:

• Μέγιστο βάρος M και αριθμός συσκευασιών n.
• Πίνακας βάρους W[i] και αντίστοιχης τιμής V[i].

Παραγωγή:

• Μέγιστη συνολική τιμή που μπορεί να επιτευχθεί εντός της χωρητικότητας.
• Το ακριβές σύνολο δεμάτων που πρέπει να πάρει ο κλέφτης.

Ο αλγόριθμος Knapsack χωρίζεται σε δύο γνωστές παραλλαγές:

• 0/1 Πρόβλημα με το Σακίδιο λύνεται με Δυναμικό Προγραμματισμό. Κάθε πακέτο είτε λαμβάνεται ολόκληρο είτε αφήνεται πίσω — χωρίς κλασματικά κομμάτια και χωρίς διπλότυπα.
• Πρόβλημα κλασματικού σακιδίου λύνεται με μια Άπληστη Στρατηγική. Εδώ μπορείτε να πάρετε ένα κλάσμα οποιουδήποτε πακέτου για να γεμίσετε την υπόλοιπη χωρητικότητα.

Πώς να λύσετε το πρόβλημα του σακιδίου χρησιμοποιώντας το δυναμικό προγραμματισμό με Παράδειγμα

Η μέθοδος «διαίρει και βασίλευε» διαιρεί ένα μεγάλο πρόβλημα σε υποπροβλήματα και στη συνέχεια συνεχίζει να διαιρεί το πρόβλημα μέχρι να γίνει εύκολο κάθε υποπρόβλημα. Η απλή αναδρομή, ωστόσο, συχνά λύνει το ίδιο υποπρόβλημα πολλές φορές και σπαταλάει δουλειά.

Η βασική ιδέα του Δυναμικού Προγραμματισμού Knapsack είναι η αποθήκευση κάθε λυμένου υποπροβλήματος σε έναν πίνακα. Οι επαναλαμβανόμενες κλήσεις διαβάζουν την απάντηση αντί να την υπολογίζουν ξανά, μετατρέποντας μια εκθετική αναδρομή σε κώδικα πολυωνυμικού χρόνου.

Επίλυση Προβλήματος Σακιδίου χρησιμοποιώντας Δυναμικό Προγραμματισμό

Για να σχεδιάσετε μια λύση Δυναμικού Προγραμματισμού, ακολουθείτε τέσσερα βήματα:

• Λύστε πρώτα τα μικρότερα υποπροβλήματα.
• Παράγετε μια επαναλαμβανόμενη απάντηση που δομεί μια υπο-προβληματική απάντηση από μικρότερα.
• Αποθηκεύστε τις απαντήσεις των υποπροβλημάτων σε έναν πίνακα που υπολογίζεται από κάτω προς τα πάνω χρησιμοποιώντας την επαναληπτικότητα.
• Συγκεντρώστε την τελική απάντηση από τον πλήρως συμπληρωμένο πίνακα.

Αναλύστε το πρόβλημα του σακιδίου 0/1

Η βέλτιστη τιμή εξαρτάται από δύο ανεξάρτητους παράγοντες:

1. Πόσα πακέτα εξετάζονται ακόμη.
2. Το υπόλοιπο βάρος μπορεί ακόμα να χωρέσει το σακίδιο.

Επειδή η αντικειμενική συνάρτηση εξαρτάται από δύο ποσότητες, ο πίνακας επιλογών πρέπει να είναι δισδιάστατος. Έστω B[i][j] δηλώνει τη μέγιστη τιμή κατά την επιλογή μεταξύ συσκευασιών {1, …, i} με όριο βάρους j.

• Η τελική απάντηση είναι B[n][M], η καλύτερη συνολική τιμή σε όλα τα n πακέτα με χωρητικότητα M.
• Το συνολικό επιλεγμένο βάρος περιορίζεται πάντα από την τρέχουσα χωρητικότητα: B[i][j] ≤ j.

Παράδειγμα: εάν B[4][10] = 8, το καλύτερο συνολικό βάρος από τα πρώτα τέσσερα δέματα κάτω από τη χωρητικότητα 10 είναι 8. Μερικά από αυτά τα τέσσερα δέματα ενδέχεται να παραλειφθούν.

Τύπος για τον υπολογισμό του B[i][j]

• W[i], V[i] είναι το βάρος και η αξία του πακέτου i, όπου το i βρίσκεται στο {1, …, n}.
• M είναι το μέγιστο βάρος που μπορεί να μεταφέρει ένα σακίδιο πλάτης.

Βασική περίπτωση με ένα πακέτο: για κάθε χωρητικότητα j ≥ W[1]:

B[1][j] = W[1]

Για τη γενική περίπτωση, αποφασίστε εάν θα συμπεριλάβετε το πακέτο i στην χωρητικότητα j:

• Αν το πακέτο i είναι παραλείφθηκε, B[i][j] ισούται με την καλύτερη τιμή χρησιμοποιώντας πακέτα {1, …, i-1} υπό χωρητικότητα j:

B[i][j] = B[i - 1][j]

• Αν το πακέτο i είναι λαμβάνεται (επιτρέπεται μόνο όταν W[i] ≤ j), B[i][j] ισούται με V[i] συν την καλύτερη τιμή από τα πακέτα {1, …, i-1} υπό χωρητικότητα j – W[i]:

B[i][j] = V[i] + B[i - 1][j - W[i]]

Πάρτε τον μεγαλύτερο από τους δύο υποψηφίους.

Βάση Δυναμικού Προγραμματισμού

Ο συνδυασμός των δύο περιπτώσεων δίνει την πλήρη επανάληψη:

B[i][j] = max(B[i - 1][j], V[i] + B[i - 1][j - W[i]])

Η βασική περίπτωση είναι B[0][j] = 0 για κάθε j, επειδή τα μηδενικά πακέτα δίνουν μηδενική τιμή ανεξάρτητα από τη χωρητικότητα.

Υπολογίστε τον Πίνακα Επιλογών

Δημιουργήστε το B χρησιμοποιώντας την επαναλαμβανόμενη διαδικασία. Μόλις συμπληρωθεί το B, ο ίδιος πίνακας οδηγεί το trace-back που ανακατασκευάζει τα επιλεγμένα πακέτα. Ο Πίνακας Β έχει n + 1 γραμμές και M + 1 στήλες:

• Η σειρά 0 είναι η βασική περίπτωση, γεμάτη με μηδενικά.
• Χρησιμοποιήστε τη γραμμή 0 για να υπολογίσετε τη γραμμή 1, τη γραμμή 1 για να υπολογίσετε τη γραμμή 2 και συνεχίστε μέχρι να ολοκληρωθεί η γραμμή n.

Πίνακας Επιλογών

Trace

Μόλις ολοκληρωθεί το Β, επικεντρωθείτε στο B[n][M], η βέλτιστη συνολική τιμή σε όλα τα n πακέτα με χωρητικότητα M.

• If Β[n][M] = Β[n-1][M], το πακέτο n δεν επιλέχθηκε, οπότε συνεχίστε tracαπό B[n-1][M].
• If Β[n][M] ≠ Β[n-1][M], επιλέχθηκε το πακέτο n, άρα συνεχίστε tracαπό B[n-1][M – W[n]].

Επαναλάβετε μέχρι να φτάσετε στη σειρά 0 του πίνακα.

Αλγόριθμος για την αναζήτηση του πίνακα επιλογών για την εύρεση των επιλεγμένων πακέτων

Σημείωση: όποτε B[i][j] = B[i-1][j], το πακέτο i δεν είναι επιλεγμένο. Η τιμή B[n][M] είναι η βέλτιστη συνολική τιμή που συσκευάζεται στο σακίδιο.

Βήματα για tracτα επιλεγμένα πακέτα:

• Βήμα 1: Ξεκινήστε από i = n, j = M.
• Βήμα 2: Σαρώστε τη στήλη j από κάτω προς τα πάνω μέχρι να βρείτε μια γραμμή i όπου B[i][j] > B[i-1][j]. Σημειώστε το πακέτο i ως επιλεγμένο: Select[i] = true.
• Βήμα 3: Ενημερώστε το j = j – W[i]. Αν j > 0, επιστρέψτε στο Βήμα 2, διαφορετικά προχωρήστε στο Βήμα 4.
• Βήμα 4: Εκτυπώστε κάθε πακέτο που έχει επισημανθεί ως επιλεγμένο.

Java Code

Ο ακόλουθος Java η μέθοδος συμπληρώνει το B[][] από κάτω προς τα πάνω, εκτυπώνει τον πίνακα για έλεγχο και, στη συνέχεια, tracτα επιλεγμένα πακέτα.

public void knapsackDyProg(int W[], int V[], int M, int n) {
    int B[][] = new int[n + 1][M + 1];

    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= M; j++) {
            B[i][j] = 0;
        }

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= M; j++) {
            B[i][j] = B[i - 1][j];

            if ((j >= W[i - 1]) && (B[i][j] < B[i - 1][j - W[i - 1]] + V[i - 1])) {
                B[i][j] = B[i - 1][j - W[i - 1]] + V[i - 1];
            }

            System.out.print(B[i][j] + " ");
        }
        System.out.print("\n");
    }

    System.out.println("Max Value:\t" + B[n][M]);
    System.out.println("Selected Packs: ");

    int j = M;
    while (n != 0) {
        if (B[n][j] != B[n - 1][j]) {
            System.out.println("\tPackage " + n + " with W = " + W[n - 1] + " and Value = " + V[n - 1]);
            j = j - W[n - 1];
        }
        n--;
    }
}

Λειτουργία knapsackDyProg() σε Java

Επεξήγηση του κώδικα:

1. Κατανομή πίνακα B[][] και αρχικοποιήστε κάθε κελί στο 0.
2. Συμπληρώστε το B[][] από κάτω προς τα πάνω χρησιμοποιώντας την επανάληψη από την προηγούμενη ενότητα.
3. Ξεκινήστε κάθε κελί με την τιμή «παράλειψη πακέτου i» B[i-1][j].
4. Εάν η επιλογή του πακέτου i είναι εφικτή και δίνει μια αυστηρά καλύτερη τιμή, αντικαταστήστε το κελί.
5. Tracμεταφέρετε τα επιλεγμένα στοιχεία από τη σειρά n πίσω στη σειρά 0.
6. Όποτε επιλέγεται το πακέτο n, μειώνεται η υπολειπόμενη χωρητικότητα κατά W[n-1].

Σημείωση διόρθωσης: η παράμετρος μεταλλαγμένου αρχικού αποσπάσματος M ενώ ακόμα διαβάζω B[n][M]Η ασφαλέστερη έκδοση παραπάνω χρησιμοποιεί ξεχωριστό κέρσορα j των trace.

The Java Ο οδηγός εκτελεί τον αλγόριθμο σε δύο επεξεργασμένα παραδείγματα:

public void run() {
    // First Example
    // int W[] = new int[]{3, 4, 5, 9, 4};
    // int V[] = new int[]{3, 4, 4, 10, 4};
    // int M = 11;

    // Second Example
    int W[] = new int[]{12, 2, 1, 1, 4};
    int V[] = new int[]{4, 2, 1, 2, 10};
    int M = 15;

    int n = V.length;
    knapsackDyProg(W, V, M, n);
}

Έξοδος για το πρώτο παράδειγμα:

0 0 0 3 3 3 3 3 3 3 3 3
0 0 0 3 4 4 4 7 7 7 7 7
0 0 0 3 4 4 4 7 7 8 8 8
0 0 0 3 4 4 4 7 7 10 10 10
0 0 0 3 4 4 4 7 8 10 10 11
Max Value:	11
Selected Packs:
	Package 5 with W = 4 and Value = 4
	Package 2 with W = 4 and Value = 4
	Package 1 with W = 3 and Value = 3

Έξοδος για το δεύτερο παράδειγμα:

0 0 0 0 0 0 0 0 0 0 0 0 4 4 4 4
0 0 2 2 2 2 2 2 2 2 2 2 4 4 6 6
0 1 2 3 3 3 3 3 3 3 3 3 4 5 6 7
0 2 3 4 5 5 5 5 5 5 5 5 5 6 7 8
0 2 3 4 10 12 13 14 15 15 15 15 15 15 15 15
Max Value:	15
Selected Packs:
	Package 5 with W = 4 and Value = 10
	Package 4 with W = 1 and Value = 2
	Package 3 with W = 1 and Value = 1
	Package 2 with W = 2 and Value = 2

Χρονική και χωρική πολυπλοκότητα του σακιδίου πλάτης 0/1

• Χρονική πολυπλοκότητα: O(n · M) — οι δύο ένθετοι βρόχοι σαρώνουν n στοιχεία σε καταστάσεις χωρητικότητας M+1.
• Πολυπλοκότητα χώρου: O(n · M) για τον πλήρη πίνακα, αναγώγιμο σε O(M) από το keeping μόνο η προηγούμενη σειρά όταν tracΔεν απαιτείται ηλεκτρονική επιστροφή.

Ο χρόνος εκτέλεσης είναι ψευδο-πολυώνυμο: πολυωνυμικό στην τιμή του M αλλά εκθετικό στα bits που χρησιμοποιούνται για την κωδικοποίηση του M. Αυτός είναι ο λόγος για τον οποίο το 0/1 Knapsack παραμένει NP-hard παρόλο που ο Δυναμικός Προγραμματισμός είναι αποτελεσματικός στην πράξη.

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

• Φόρτωση φορτίου, συσκευασία εμπορευματοκιβωτίων και παραλαβή από την αποθήκη εντός ορίων βάρους.
• Κατανομή προϋπολογισμού σε επενδυτικά έργα με σταθερό κόστος και αναμενόμενη απόδοση.
• Προβλήματα μείωσης αποθεμάτων στην κατασκευή που δεν μπορούν να διαχωρίσουν μεμονωμένα κομμάτια.
• Σχήματα κρυπτογραφίας όπως το Merkle-Hellman που βασίζονται στη σκληρότητα του σακιδίου πλάτης.
• Χρονοπρογραμματισμός με περιορισμούς πόρων στο cloud computing και τοποθέτηση εργασιών CPU.
• Επιλογή χαρακτηριστικών στη μηχανική μάθηση με σταθερό προϋπολογισμό χαρακτηριστικών.

Συχνές Ερωτήσεις