Condivisione della tecnologia

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

1. Problema

Ti viene fornito un array non vuoto di numeri contenente solo numeri interi positivi. Valuta se questo array può essere diviso in due sottoinsiemi in modo che la somma degli elementi dei due sottoinsiemi sia uguale.

2. Idea di soluzione 1

Soluzione di programmazione dinamica

Questo problema non può essere risolto utilizzando l'algoritmo di backtracking. Se la quantità di dati è elevata, scadrà. Possiamo usare la programmazione dinamica.
Questa domanda determina se la somma degli elementi delle due parti è uguale quando l'array è diviso in due parti. Per prima cosa dobbiamo calcolare la somma di tutti gli elementi dell'array, e poi determinare se la somma è un numero pari: se non è un numero pari, significa che non può essere diviso in due parti completamente uguali, e restituirà falso direttamente.
Se è un numero pari, dobbiamo solo determinare se ci sono alcuni elementi la cui somma è uguale a somma/2. Se è uguale a somma/2, allora anche il resto deve essere uguale a somma/2, il che significa che possiamo dividere l'array in due parti con elementi uguali.
Quindi il problema a questo punto è molto chiaro. Supponendo che sum/2 sia la capacità di uno zaino, dobbiamo solo trovare alcuni elementi e inserirli nello zaino se la somma massima degli elementi nello zaino è uguale a sum /2, significa che possiamo mettere l'array Divide in due parti uguali. Non è questo il classico problema dello zaino 0-1? Il problema base dello zaino nella serie di problemi con lo zaino può essere letto di seguito per i dettagli. Non ripeterò qui l'introduzione. Cerchiamo la sua formula di ricorsione e definiamo dp[i][j] per rappresentare il valore massimo ottenuto mettendo l'oggetto i-esimo in uno zaino con capacità j.
Il valore dell'i-esimo elemento è nums [i -1]:
Se nums [i -1]>j, significa che la capacità dello zaino non è sufficiente e non è possibile inserire l'i-esimo oggetto, quindi non possiamo selezionare l'i-esimo oggetto, quindi
dp[i][j]=dp[i -1][j];
Se nums [i -1]<=j, significa che il jesimo oggetto può essere messo nello zaino. Possiamo scegliere di metterlo o meno, basta prendere il valore massimo. Se lo mettiamo, occuperà parte dello capacità dello zaino Il valore massimo sì
dp[i][j]=dp[i-1][j-num[i-1]]+num[i-1]
Se non lasci andare
dp[i][j]=dp[i -1][j];
Prendi il massimo dei due

La formula ricorsiva finale e il codice sono i seguenti:

#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;
}

Possiamo anche scrivere così. L'array bidimensionale dp è di tipo booleano. dp[i][j] indica se la somma dei primi i elementi dell'array può formare una somma di j. 0]=true, il che significa che i primi 0 elementi (ovvero nessun elemento) possono formare una somma di 0.codice mostrato come di seguito

#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];
}

Vediamo che quando si calcola l'array bidimensionale sopra, il valore corrente è correlato solo alla riga precedente, quindi possiamo cambiarlo in unidimensionale. Nota che il secondo ciclo for deve essere flashback, altrimenti il ​​valore precedente verrà sovrascritto e il risultato sarà sbagliato, dai un'occhiata più da vicino
dp[j] = (dp[j] || dp[j - numeri [i - 1]]);
Puoi capire che il valore alla fine della stessa riga dipende da quello precedente. Se non si tratta di un flashback, il valore precedente viene modificato, il che causerà un errore nel calcolo di quello successivo.Diamo un'occhiata al codice

#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. Idea di soluzione 2

Soluzione dell'algoritmo DFS

Ogni elemento può essere selezionato o meno. Devi solo determinare se la somma degli elementi in tutte le sue possibili combinazioni è uguale a sum/2. Possiamo pensarlo come un albero binario elemento corrente e il nodo figlio destro rappresenta la selezione dell'elemento corrente. Il nodo figlio indica che l'elemento corrente non è selezionato, come mostrato nella figura seguente. Il nodo arancione indica che l'elemento corrente è selezionato e il nodo blu indica che l'elemento corrente non è selezionato.

Diamo prima un’occhiata al codice di implementazione preliminare

#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);
}

Ma sfortunatamente, poiché la quantità di calcolo è troppo grande, l'operazione scadrà. Possiamo ottimizzarla e dare un'occhiata al codice.

#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. Idea di soluzione 3

Soluzione operativa a bit

Qui è possibile utilizzare operazioni bit, ma la chiave sta in alcune restrizioni nella domanda, come un array non vuoto di interi positivi, gli elementi in ciascun array non supereranno 100, la dimensione dell'array non supererà 200, ecc. .
Il principio è molto semplice. Dobbiamo solo applicare un array bits[sum+1] di dimensione sum+1. I numeri nell'array possono essere solo 0 e 1. Possiamo immaginarlo come un bit binario molto lungo, perché int e il tipo lungo è troppo corto, qui stiamo usando un array. Quindi ogni volta che viene attraversato un elemento nell'array, come m, il bit binario viene spostato a sinistra di m bit e quindi eseguito tramite OR con il bit binario originale. Infine, determina se bits[sum/2] è 1 e restituisce true se è 1.La descrizione del testo non è molto semplice. Prendiamo l'Esempio 1 come esempio per disegnare un'immagine.

Infine, troverai una regola, ovvero finché il risultato finale dell'operazione è 1, può essere combinato utilizzando gli elementi dell'array. Finché è 0, non può essere combinato utilizzando gli elementi dell'array processo sopra, il codice è facile da scrivere. Poiché dobbiamo solo determinare se il valore medio nel bit binario è 1, dobbiamo solo calcolare il bit basso e non è necessario calcolare affatto il bit alto perché viene spostato a sinistra e quello alto bit non avrà alcun impatto sul valore medio, quindi possiamo farlo qui. Una piccola ottimizzazione e infine diamo un'occhiata al codice.

#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;
}