Μια παραλλαγή στο πρόβλημα Knapsack: πώς να επιλύσετε το πρόβλημα Partition Equal Subset Sum στην Java

Προηγουμένως, έγραψα για την επίλυση του προβλήματος Knapsack (KP) με δυναμικό προγραμματισμό. Μπορείτε να το διαβάσετε εδώ.

Σήμερα θέλω να συζητήσω μια παραλλαγή του KP: το πρόβλημα του ίσου υποσυνόλου διαμέρισης Πρώτα είδα αυτό το πρόβλημα στο Leetcode - αυτό ήταν που με ώθησε να μάθω και να γράψω για το KP.

Αυτή είναι η δήλωση προβλήματος (αναπαράγεται εν μέρει χωρίς παραδείγματα):

Λαμβάνοντας υπόψη έναν μη κενό πίνακα που περιέχει μόνο θετικούς ακέραιους αριθμούς, βρείτε αν ο πίνακας μπορεί να χωριστεί σε δύο υποσύνολα έτσι ώστε το άθροισμα των στοιχείων και στα δύο υποσύνολα να είναι ίσο.

Για την πλήρη δήλωση προβλήματος, με περιορισμούς και παραδείγματα, δείτε το πρόβλημα Leetcode.

Δυναμικός προγραμματισμός

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

Λύση

Θα τοποθετήσουμε τη λύση μας σε μια μέθοδο που επιστρέφει ένα boolean - true εάν ο πίνακας μπορεί να διαχωριστεί σε ίσα υποσύνολα και ψευδώς διαφορετικά

Βήμα 1: Προστασία από το περίεργο άθροισμα του πίνακα

Σημαντικά, εάν όλοι οι αριθμοί του πίνακα προσθέτουν έως ένα περίεργο άθροισμα, μπορούμε να επιστρέψουμε ψευδείς. Συνεχίζουμε μόνο εάν ο πίνακας προσθέτει ένα ομαλό άθροισμα.

Βήμα 2: Δημιουργία πίνακα

Στη συνέχεια, δημιουργούμε τον πίνακα.

Οι σειρές πίνακα αντιπροσωπεύουν το σύνολο στοιχείων πίνακα που πρέπει να ληφθούν υπόψη, ενώ οι στήλες πίνακα δείχνουν το άθροισμα στο οποίο θέλουμε να φτάσουμε. Οι τιμές του πίνακα είναι απλώς δυαδικές τιμές, υποδεικνύοντας εάν ένα άθροισμα (στήλη) μπορεί να φτάσει με ένα σύνολο στοιχείων πίνακα (σειρά).

Συγκεκριμένα, η σειρά i αντιπροσωπεύει ένα σύνολο στοιχείων πίνακα από τους δείκτες 0 έως ( i -1). Ο λόγος για αυτήν την μετατόπιση του 1 είναι επειδή η σειρά 0 αντιπροσωπεύει ένα κενό σύνολο στοιχείων. Επομένως, η σειρά 1 αντιπροσωπεύει το πρώτο στοιχείο πίνακα (ευρετήριο 0), η σειρά 2 αντιπροσωπεύει τα δύο πρώτα στοιχεία πίνακα (δείκτες 0-1) και ούτω καθεξής. Συνολικά, δημιουργούμε n + 1σειρές, συμπεριλαμβανομένων των 0.

Θέλουμε μόνο να γνωρίζουμε αν μπορούμε να αθροίσουμε ακριβώς το ήμισυ του συνολικού αθροίσματος του πίνακα. Επομένως, χρειάζεται μόνο να δημιουργήσουμε totalSum / 2 + 1στήλες, συμπεριλαμβανομένων των 0.

Βήμα 3: Πλήρωση του πίνακα

Μπορούμε αμέσως να αρχίσουμε να συμπληρώνουμε τις καταχωρήσεις για τις βασικές περιπτώσεις στον πίνακα μας - σειρά 0 και στήλη 0.

Στην πρώτη σειρά, κάθε καταχώριση - εκτός από την πρώτη - πρέπει να είναι false. Θυμηθείτε ότι η πρώτη σειρά αντιπροσωπεύει ένα κενό σύνολο. Φυσικά, δεν μπορούμε να καταλήξουμε σε κανένα ποσό στόχου - αριθμός στήλης - εκτός από το 0.

Στην πρώτη στήλη, κάθε καταχώριση πρέπει να είναι true. Μπορούμε πάντα, ασήμαντα, να φτάσουμε σε ένα στοχευμένο άθροισμα 0, ανεξάρτητα από το σύνολο των στοιχείων με τα οποία πρέπει να εργαστούμε.

Βήμα 4: Δημιουργία του πίνακα (η ουσία του προβλήματος)

Κάποια εγγραφή στον πίνακα στη σειρά i και στη στήλη j είναι true(εφικτή) εάν πληρούται μία από τις ακόλουθες τρεις προϋποθέσεις:

  1. η καταχώριση στη σειρά i -1 και στη στήλη j είναι true. Θυμηθείτε τι αντιπροσωπεύει ο αριθμός σειράς. Επομένως, εάν είμαστε σε θέση να επιτύχουμε ένα συγκεκριμένο άθροισμα με ένα υποσύνολο των στοιχείων που έχουμε επί του παρόντος, μπορούμε επίσης να επιτύχουμε αυτό το άθροισμα με το τρέχον σύνολο στοιχείων μας - απλώς χωρίς τη χρήση των επιπλέον στοιχείων. Αυτό είναι ασήμαντο. Ας το πούμε αυτό prevRowIsTrue.
  2. Το τρέχον στοιχείο είναι ακριβώς το άθροισμα που θέλουμε να επιτύχουμε. Αυτό είναι επίσης ασήμαντο. Ας το πούμε αυτό isExactMatch.
  3. Εάν δεν πληρούνται οι παραπάνω δύο προϋποθέσεις, έχουμε έναν ακόμη τρόπο για να επιτύχουμε το ποσό-στόχο. Εδώ, χρησιμοποιούμε το τρέχον στοιχείο - το πρόσθετο στοιχείο στο σύνολο στοιχείων στην τρέχουσα σειρά μας σε σύγκριση με το σύνολο στοιχείων στην προηγούμενη σειρά - και ελέγχουμε ότι μπορούμε να επιτύχουμε το υπόλοιπο του αθροίσματος στόχου. Ας το πούμε αυτό canArriveAtSum.

Ας αποσυσκευάσουμε την κατάσταση 3. Μπορούμε να χρησιμοποιήσουμε το τρέχον στοιχείο μόνο εάν είναι μικρότερο από το συνολικό ποσό που στοχεύουμε. Εάν είναι ίσοι, η προϋπόθεση 2 θα ικανοποιηθεί. Εάν είναι μεγαλύτερο, δεν μπορούμε να το χρησιμοποιήσουμε. Επομένως, το πρώτο βήμα είναι να διασφαλιστεί ότι το τρέχον στοιχείο <σύνολο στόχου.

Αφού χρησιμοποιήσουμε το τρέχον στοιχείο μας, μένουμε με το υπόλοιπο του ποσού στόχου μας. Στη συνέχεια, ελέγχουμε εάν αυτό είναι εφικτό ελέγχοντας την αντίστοιχη καταχώρηση στην παραπάνω σειρά.

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

Βήμα 5: Επιστροφή της απάντησης

Επιστρέφουμε απλά return mat[nums.length][totalSum / 2].

Κωδικός εργασίας

Ευχαριστώ για την ανάγνωση!