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

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

1. Πρόβλημα

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

2. Ιδέα λύσης 1

Λύση δυναμικού προγραμματισμού

Αυτό το πρόβλημα δεν μπορεί να λυθεί χρησιμοποιώντας τον αλγόριθμο backtracking Εάν ο όγκος των δεδομένων είναι μεγάλος, θα λήξει. Μπορούμε να χρησιμοποιήσουμε δυναμικό προγραμματισμό.
Αυτή η ερώτηση καθορίζει εάν το άθροισμα των στοιχείων των δύο μερών είναι ίσο όταν ο πίνακας χωρίζεται σε δύο μέρη. Πρώτα πρέπει να υπολογίσουμε το άθροισμα όλων των στοιχείων του πίνακα και μετά να προσδιορίσουμε αν το άθροισμα είναι ζυγός αριθμός: αν δεν είναι ζυγός, σημαίνει ότι δεν μπορεί να χωριστεί σε δύο εντελώς ίσα μέρη και θα επιστρέψει ψευδής ευθέως.
Εάν είναι ζυγός αριθμός, χρειάζεται μόνο να προσδιορίσουμε αν υπάρχουν κάποια στοιχεία των οποίων το άθροισμα είναι ίσο με άθροισμα/2, τότε και τα υπόλοιπα πρέπει να είναι ίσα με άθροισμα/2, που σημαίνει ότι μπορούμε να χωρίσουμε τον πίνακα σε δύο μέρη με ίσα στοιχεία.
Τότε το πρόβλημα είναι πολύ σαφές αυτή τη στιγμή Αν υποθέσουμε ότι το άθροισμα/2 είναι η χωρητικότητα ενός σακιδίου, χρειάζεται μόνο να βρούμε ορισμένα στοιχεία και να τα βάλουμε στο σακίδιο πλάτης /2, σημαίνει ότι μπορούμε να βάλουμε τον πίνακα Divide σε δύο ίσα μέρη. Αυτό δεν είναι το κλασικό πρόβλημα με το σακίδιο 0-1; Το βασικό πρόβλημα με το σακίδιο μπορεί να διαβαστεί παρακάτω για λεπτομέρειες. Δεν θα επαναλάβω την εισαγωγή εδώ. Αναζητούμε τον τύπο αναδρομής του και ορίζουμε το dp[i][j] για να αναπαραστήσουμε τη μέγιστη τιμή που λαμβάνεται τοποθετώντας το i-ο στοιχείο σε ένα σακίδιο με χωρητικότητα j.
Η τιμή του i-ου στοιχείου είναι αριθμοί [i -1]:
Αν αριθμοί [i -1]>j, σημαίνει ότι η χωρητικότητα του σακιδίου δεν είναι αρκετή και το i-ο αντικείμενο δεν μπορεί να τοποθετηθεί, επομένως δεν μπορούμε να επιλέξουμε το i-ο στοιχείο, τότε
dp[i][j]=dp[i -1][j]；
Εάν το nums [i -1]<=j, σημαίνει ότι το jο αντικείμενο μπορεί να τοποθετηθεί στο σακίδιο Χωρητικότητα σακιδίου Η μέγιστη τιμή ναι
dp[i][j]=dp[i-1][j-αριθμοί[i-1]]+αριθμοί[i-1]
Αν δεν το αφήσεις
dp[i][j]=dp[i -1][j]；
Πάρτε το μέγιστο από τα δύο

Ο τελικός αναδρομικός τύπος και ο κώδικας είναι οι εξής:

#include <vector>
 
bool canPartition(std::vector<int>& nums) {
    // 计算数组中所有元素的和
    int sum = 0;
    for (int num : nums) {
        sum += num;
    }
    // 如果sum是奇数，说明数组不可能分成完全相等的两份
    if ((sum & 1) == 1) {
        return false;
    }
    // sum除以2
    int target = sum >> 1;
    int length = nums.size();
    std::vector<std::vector<int>> dp(length + 1, std::vector<int>(target + 1, 0));
    for (int i = 1; i <= length; ++i) {
        for (int j = 1; j <= target; ++j) {
            // 下面是递推公式
            if (j >= nums[i - 1]) {
                dp[i][j] = std::max(dp[i - 1][j], dp[i - 1][j - nums[i - 1]] + nums[i - 1]);
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    // 判断背包最大是否能存放和为target的元素
    return dp[length][target] == target;
}

Μπορούμε επίσης να γράψουμε έτσι Ο δισδιάστατος πίνακας dp είναι δυαδικού τύπου dp[i][j]. 0]=true, που σημαίνει Τα πρώτα 0 στοιχεία (δηλαδή, κανένα στοιχείο) μπορούν να σχηματίσουν άθροισμα 0.ο κωδικός εμφανίζεται όπως παρακάτω

#include <vector>
 
bool canPartition(std::vector<int>& nums) {
    // 计算数组中所有元素的和
    int sum = 0;
    for (int num : nums) {
        sum += num;
    }
    // 如果sum是奇数，说明数组不可能分成完全相等的两份
    if ((sum & 1) == 1) {
        return false;
    }
    // sum除以2得到target
    int target = sum >> 1;
    int length = nums.size();
    std::vector<std::vector<bool>> dp(length + 1, std::vector<bool>(target + 1, false));
    // base case
    dp[0][0] = true;
    for (int i = 1; i <= length; ++i) {
        for (int j = 0; j <= target; ++j) {
            // 递推公式
            if (j >= nums[i - 1]) {
                dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    // 返回能否找到和为target的子集
    return dp[length][target];
}

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

#include <vector>
 
bool canPartition(std::vector<int>& nums) {
    // 计算数组中所有元素的和
    int sum = 0;
    for (int num : nums) {
        sum += num;
    }
    // 如果sum是奇数，说明数组不可能分成完全相等的两份
    if ((sum & 1) == 1) {
        return false;
    }
    // sum除以2得到target
    int target = sum >> 1;
    int length = nums.size();
    std::vector<bool> dp(target + 1, false);
    // base case
    dp[0] = true;
    for (int i = 0; i < length; ++i) {
        // 注意这里j要倒序
        for (int j = target; j >= nums[i]; --j) {
            // 递推公式
            dp[j] = dp[j] || dp[j - nums[i]];
        }
    }
    // 返回能否找到和为target的子集
    return dp[target];
}

3. Ιδέα λύσης 2

Λύση αλγορίθμου DFS

Κάθε στοιχείο μπορεί να επιλεγεί ή όχι Χρειάζεται μόνο να προσδιορίσετε αν το άθροισμα των στοιχείων σε όλους τους πιθανούς συνδυασμούς του είναι ίσο με το άθροισμα/2 τρέχον στοιχείο και ο δεξιός θυγατρικός κόμβος αντιπροσωπεύει την επιλογή του τρέχοντος στοιχείου Ο θυγατρικός κόμβος υποδεικνύει ότι το τρέχον στοιχείο δεν είναι επιλεγμένο, όπως φαίνεται στο παρακάτω σχήμα υποδεικνύει ότι το τρέχον στοιχείο δεν έχει επιλεγεί.

Ας ρίξουμε μια ματιά στον προκαταρκτικό κώδικα υλοποίησης πρώτα

#include <vector>
 
bool dfs(const std::vector<int>& nums, int target, int index) {
    // target等于0，说明存在一些元素的和等于sum/2，直接返回true
    if (target == 0) return true;
    // 如果数组元素都找完了，或者target小于0，直接返回false
    if (index == nums.size() || target < 0) return false;
    // 选择当前元素和不选择当前元素两种情况
    return dfs(nums, target - nums[index], index + 1) || dfs(nums, target, index + 1);
}
 
bool canPartition(std::vector<int>& nums) {
    // 计算数组中所有元素的和
    int sum = 0;
    for (int num : nums) sum += num;
    // 如果sum是奇数，说明数组不可能分成完全相等的两份
    if ((sum & 1) == 1) return false;
    // 调用dfs函数
    return dfs(nums, sum >> 1, 0);
}

Αλλά δυστυχώς, επειδή ο υπολογισμός είναι πολύ μεγάλος, θα λήξει το χρονικό διάστημα της λειτουργίας Μπορούμε να το βελτιστοποιήσουμε και να ρίξουμε μια ματιά στον κώδικα.

#include <vector>
 
bool dfs(const std::vector<int>& nums, int index, int target, std::vector<std::vector<int>>& map) {
    // target等于0，说明存在一些元素的和等于sum/2，直接返回true
    if (target == 0) return true;
    // 如果数组元素都找完了，或者target小于0，直接返回false
    if (index >= nums.size() || target < 0) return false;
    // 如果此子问题已经被计算过，直接返回结果
    if (map[index][target] != -1) return map[index][target] == 1;
    // 选择当前元素
    bool select = dfs(nums, index + 1, target - nums[index], map);
    // 不选择当前元素
    bool unSelect = dfs(nums, index + 1, target, map);
    // 存储结果，并返回
    map[index][target] = select || unSelect ? 1 : 0;
    return select || unSelect;
}
 
bool canPartition(std::vector<int>& nums) {
    // 计算数组中所有元素的和
    int sum = 0;
    for (int num : nums) sum += num;
    // 如果sum是奇数，说明数组不可能分成完全相等的两份
    if (sum % 2 != 0) return false;
    // sum除以2
    int target = sum / 2;
    std::vector<std::vector<int>> map(nums.size(), std::vector<int>(target + 1, -1));
    return dfs(nums, 0, target, map);
}

4. Ιδέα λύσης 3

Λύση λειτουργίας bit

Οι λειτουργίες bit μπορούν να χρησιμοποιηθούν εδώ, αλλά το κλειδί βρίσκεται σε ορισμένους περιορισμούς στην ερώτηση, όπως ένας μη κενός πίνακας θετικών ακεραίων, τα στοιχεία σε κάθε πίνακα δεν θα υπερβαίνουν τα 100, το μέγεθος του πίνακα δεν θα υπερβαίνει τα 200 κ.λπ. .
Η αρχή είναι πολύ απλή Χρειάζεται να κάνουμε αίτηση μόνο για bit πίνακα[άθροισμα+1] μεγέθους άθροισμα +1. int και Ο τύπος long είναι πολύ σύντομος, εδώ χρησιμοποιούμε έναν πίνακα. Στη συνέχεια, κάθε φορά που διασχίζεται ένα στοιχείο του πίνακα, όπως το m, το δυαδικό bit μετατοπίζεται προς τα αριστερά κατά m bit και στη συνέχεια OR με το αρχικό δυαδικό bit. Τέλος, προσδιορίστε εάν τα bits[sum/2] είναι 1 και επιστρέψτε true εάν είναι 1.Η περιγραφή του κειμένου δεν είναι πολύ απλή. Ας πάρουμε το Παράδειγμα 1 ως παράδειγμα για να σχεδιάσουμε μια εικόνα.

Τέλος, θα βρείτε έναν κανόνα, δηλαδή, εφόσον το τελικό αποτέλεσμα της λειτουργίας είναι 1, μπορεί να συνδυαστεί χρησιμοποιώντας στοιχεία στον πίνακα, εφόσον είναι 0, δεν μπορεί να συνδυαστεί χρησιμοποιώντας στοιχεία στον πίνακα παραπάνω διαδικασία, ο κώδικας είναι εύκολο να γραφτεί. Επειδή χρειάζεται μόνο να προσδιορίσουμε εάν η μεσαία τιμή στο δυαδικό bit είναι 1, χρειάζεται μόνο να υπολογίσουμε το χαμηλό bit και το υψηλό bit δεν χρειάζεται να υπολογιστεί καθόλου, επειδή μετακινείται προς τα αριστερά και το υψηλό bit δεν θα έχει καμία επίδραση στη μεσαία τιμή, οπότε μπορούμε να το κάνουμε εδώ Λίγη βελτιστοποίηση και, τέλος, ας δούμε τον κώδικα.

#include <vector>
 
bool canPartition(std::vector<int>& nums) {
    // 计算数组中所有数字的和
    int sum = 0;
    for (int n : nums) {
        sum += n;
    }
    // 如果sum是奇数，直接返回false
    if ((sum & 1) == 1) {
        return false;
    }
    int len = sum / 2;
    // 这里bits的长度是len+1，因为我们只需要计算低位就行了，没必要计算所有的
    std::vector<char> bits(len + 1, 0);
    bits[0] = 1;
    for (int num : nums) {
        for (int j = len - num; j >= 0; j--) {
            bits[j + num] |= bits[j];
        }
        // 判断中位数如果是1，说明可以分成两种相等的子集，直接返回true，不需要再计算了
        if ((bits[len] & 1) != 0) {
            return true;
        }
    }
    return false;
}