Κοινή χρήση τεχνολογίας

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

ένας,Δισδιάστατος πίνακας

1、εξίσωση μετάβασης κατάστασης：

• Μην βάζετε αντικείμενα : Συνάγεται από dp[i - 1][j], δηλαδή, η χωρητικότητα του σακιδίου είναι j και η μέγιστη τιμή του στοιχείου i δεν τοποθετείται σε αυτό αυτήν τη στιγμή, dp[i][j] είναι dp[i -. 1][j]. (Στην πραγματικότητα, όταν το βάρος του αντικειμένου i είναι μεγαλύτερο από το βάρος του σακιδίου j, το στοιχείο i δεν μπορεί να τοποθετηθεί στο σακίδιο, επομένως η τιμή στο σακίδιο παραμένει η ίδια όπως πριν.)
• Βάλτε το στοιχείο i: Συνάγεται από dp[i - 1][j - βάρος[i]], dp[i - 1][j - βάρος[i]] είναι η μέγιστη χωρητικότητα του σακιδίου χωρίς το στοιχείο i όταν η χωρητικότητα είναι j - βάρος[ τιμή i], τότε dp[i - 1][j - βάρος[i]] + τιμή[i] (η τιμή του στοιχείου i) είναι η μέγιστη τιμή που λαμβάνεται τοποθετώντας το στοιχείο i στο σακίδιο

Άρα ο αναδρομικός τύπος: dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - βάρος[i]] + τιμή[i]);

2. Αρχικοποίηση

(1) Ξεκινώντας από τον ορισμό του dp[i][j], εάν η χωρητικότητα του σακιδίου j είναι 0, δηλαδή dp[i][0], ανεξάρτητα από το ποια είδη επιλέγονται, η συνολική αξία του σακιδίου πρέπει να είναι 0.

(2) Εξίσωση μετάβασης κατάστασης dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - βάρος[i]] + τιμή[i]). φαίνεται ότι το i προέρχεται από το i-1, επομένως πρέπει να αρχικοποιηθεί όταν το i είναι 0.

dp[0][j], δηλαδή: το i είναι 0, όταν αποθηκεύεται το είδος 0, η μέγιστη τιμή που μπορεί να αποθηκεύσει ένα σακίδιο πλάτης κάθε χωρητικότητας.

Τότε είναι προφανές ότι όταν j < βάρος[0], η dp[0][j] θα πρέπει να είναι 0, επειδή η χωρητικότητα του σακιδίου είναι μικρότερη από το βάρος του αντικειμένου με αριθμό 0.

Όταν j >= βάρος[0], το dp[0][j] θα πρέπει να είναι τιμή[0], επειδή η χωρητικότητα του σακιδίου πλάτης είναι αρκετή για να χωρέσει το αντικείμενο με αριθμό 0.

for (int j = 0 ; j < weight[0]; j++) {
    dp[0][j] = 0;
}
// 正序遍历
for (int j = weight[0]; j <= bagweight; j++) {
    dp[0][j] = value[0];
}

(3) Άλλη αρχικοποίηση δείκτη:

dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - βάρος[i]] + τιμή[i])

dp[1][1] = max(dp[0][1], dp[0][1- βάρος[i]] + τιμή[i]) πρέπει να βρίσκεται στα αριστερά και πάνω από αυτό,

Επομένως, πρέπει να έχει αρχικοποιηθεί και μπορεί να ρυθμιστεί σε οποιαδήποτε τιμή για ευκολία, έχει αρχικοποιηθεί στο 0 από προεπιλογή.

2. Μονοδιάστατη (κυλιόμενη συστοιχία)

1. Στη μονοδιάστατη διάταξη dp, dp[j] σημαίνει: ένα σακίδιο με χωρητικότητα j μπορεί να μεταφέρει αντικείμενα με μέγιστη τιμή dp[j]

dp[j] = max(dp[j], dp[j - weight[i]] + value[i])

2. Αρχικοποίηση

(1) dp[0]=0, επειδή η μέγιστη τιμή των αντικειμένων που μεταφέρονται από ένα σακίδιο με χωρητικότητα 0 είναι 0.

(2) Ας υποθέσουμε ότι η αξία των στοιχείων είναι μεγαλύτερη από 0,Για να μην αντικαθίσταται από την αρχική τιμή, άρα dpΑρχικοποίηση πίνακαΌταν , είναι όλα αρχικά 0

3. Διαταγή διέλευσης

Τραβέρσα με αντίστροφη σειρά

Επεξήγηση 1: Η τιμή στο τέλος της λίστας πρέπει να προσδιοριστεί συγκρίνοντάς την με την προηγούμενη τιμή που λήφθηκε με τη διέλευση του προηγούμενου επιπέδου.

Επεξήγηση 2: Υπάρχει μόνο ένα σακίδιο πλάτης 01 για κάθε σακίδιο πλάτης Το αν αυτή η τσάντα είναι τοποθετημένη ή όχι σχετίζεται με την κατάσταση της προηγούμενης τσάντας Το δεξί είναι μια κατάσταση σε εκκρεμότητα της τρέχουσας τσάντας Στον κωδικό, ο αριθμός στα αριστερά απαιτείται για τον προσδιορισμό του πίνακα στα δεξιά, επομένως ο αριθμός στα αριστερά δεν μπορεί να καταστραφεί πριν υπολογιστεί ο αριθμός στα δεξιά.

Επεξήγηση 3: Για δύο διαστάσεις, τα αποτελέσματα για κάθε έναν από τους νέους αριθμούς dp προέρχονται από πάνω και αριστερά, στην πραγματικότητα, αυτό θα πρέπει να συμβαίνει σε μία διάσταση, αλλά σε μία διάσταση, αν εξακολουθεί να είναι από αριστερά προς τα δεξιά η πραγματική μου αριστερά Οι αριθμοί έχουν ενημερωθεί ( Η αριστερή πλευρά δεν είναι πλέον η «αρχική» αριστερή πλευρά!Αυτό θα προκαλέσει διπλή καταμέτρηση ), ακόμα κι αν το επάνω μέρος εξακολουθεί να είναι το αρχικό επάνω μέρος, ο αριθμός που προκύπτει είναι εσφαλμένος.Και αν περάσουμε από δεξιά προς τα αριστερά στο στρώμα του σακιδίου (εσωτερικό στρώμα), τότε το στοιχείο στα αριστερά θα είναι πάνταΔεν θα αντικατασταθεί με νέες τιμές λόγω της προηγούμενης λειτουργίας μου., ώστε να μπορεί να ληφθεί η σωστή τιμή.

3. Εφαρμογή

1. Δίνεται ένας μη κενός πίνακας που περιέχει μόνο θετικούς ακέραιους αριθμούς. Είναι δυνατόν να χωρίσουμε αυτόν τον πίνακα σε δύο υποσύνολα έτσι ώστε το άθροισμα των στοιχείων στα δύο υποσύνολα να είναι ίσο;

Σημείωση: Τα στοιχεία σε κάθε πίνακα δεν θα υπερβαίνουν τα 100 και το μέγεθος του πίνακα δεν θα υπερβαίνει τα 200

Παράδειγμα 1:

• Εισαγωγή: [1, 5, 11, 5]
• Έξοδος: true
• Εξήγηση: Ο πίνακας μπορεί να χωριστεί σε [1, 5, 5] και [11]

αναλύει:

Το αντικείμενο είναι i,

Το βάρος είναι nums[i], η τιμή είναι επίσης nums[i] και ο όγκος του σακιδίου είναι άθροισμα/2.

Παρόμοιο με το σακίδιο 01

Εξίσωση μετάβασης κατάστασης:

dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])

// 开始 01背包
for(int i = 0; i < nums.size(); i++) {
    for(int j = target; j >= nums[i]; j--) {
        dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
    }
}
// 集合中的元素正好可以凑成总和target
if (dp[target] == target) return true;

2. Υπάρχει ένας σωρός από πέτρες και το βάρος κάθε πέτρας είναι θετικός ακέραιος.

Κάθε γύρο, διάλεξε δύο πέτρες και σπάσε τα μαζί. Ας υποθέσουμε ότι τα βάρη των λίθων είναι x και y, και x <= y. Τότε τα πιθανά αποτελέσματα της σύνθλιψης είναι τα εξής:

Αν x == y, τότε και τα δύο πετρώματα θα συνθλιβούν τελείως.

Αν x != y, τότε η πέτρα βάρους x θα θρυμματιστεί εντελώς, και η πέτρα βάρους y θα έχει νέο βάρος yx.

Στο τέλος, το πολύ να μείνει μόνο μια πέτρα. Επιστρέφει το μικρότερο δυνατό βάρος αυτής της πέτρας. Εάν δεν έχουν μείνει πέτρες, επιστρέφεται το 0.

Παράδειγμα:

• Είσοδος: [2,7,4,1,8,1]
• Έξοδος: 1

αναλύει:

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

Στη συνέχεια, χωρίστε το σε δύο σωρούς από πέτρες Το συνολικό βάρος ενός σωρού από πέτρες είναι dp[στόχος] και το συνολικό βάρος του άλλου σωρού είναι άθροισμα - dp[στόχος].

Κατά τον υπολογισμό του στόχου, στόχος = άθροισμα / 2 επειδή είναι στρογγυλοποιημένος προς τα κάτω, επομένως το άθροισμα - dp[στόχος] πρέπει να είναι μεγαλύτερο ή ίσο με dp[στόχος]

Τότε το ελάχιστο βάρος της πέτρας που απομένει μετά τη σύγκρουση είναι (άθροισμα - dp[στόχος]) - dp[στόχος]

for (int i = 0; i < stones.length; i++) {
//采用倒序
    for (int j = target; j >= stones[i]; j--) {
        dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
    }
}
//结果
sum - 2 * dp[target];

παρατίθεται από:Κώδικες Τυχαίες Σημειώσεις