Compartilhamento de tecnologia

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

1. Problema

Você recebe um array não vazio contendo apenas números inteiros positivos. Determine se esta matriz pode ser dividida em dois subconjuntos para que a soma dos elementos dos dois subconjuntos seja igual.

2. Ideia de solução 1

Solução de programação dinâmica

Este problema não pode ser resolvido usando o algoritmo de retrocesso. Se a quantidade de dados for grande, o tempo limite será atingido. Podemos usar programação dinâmica.
Esta questão determina se a soma dos elementos das duas partes é igual quando o array é dividido em duas partes. Primeiro precisamos calcular a soma de todos os elementos do array e depois determinar se a soma é um número par: se não for um número par, significa que não pode ser dividido em duas partes completamente iguais e retornará falso diretamente.
Se for um número par, só precisamos determinar se existem alguns elementos cuja soma é igual a soma/2. Se for igual a soma/2, então o resto também deve ser igual a soma/2, o que significa que. podemos dividir o array em duas partes com elementos iguais.
Então o problema está muito claro neste momento, assumindo que soma/2 é a capacidade de uma mochila, só precisamos encontrar alguns elementos e colocá-los na mochila se a soma máxima dos elementos da mochila for igual à soma. /2, significa que podemos colocar o array Divide em duas partes iguais. Não é este o clássico problema da mochila 0-1? O problema básico da mochila na série de problemas da mochila pode ser encontrado em detalhes. Não repetirei a introdução aqui. Procuramos sua fórmula de recursão, definindo dp[i][j] para representar o valor máximo obtido ao colocar o i-ésimo item em uma mochila com capacidade j.
O valor do i-ésimo item é nums [i -1]:
Se nums [i -1]>j, significa que a capacidade da mochila não é suficiente e o i-ésimo item não pode ser colocado, portanto não podemos selecionar o i-ésimo item, então
dp[i][j]=dp[i -1][j]；
Se nums [i -1]<=j, significa que o j-ésimo item pode ser colocado na mochila. Podemos optar por colocá-lo ou não, basta pegar o valor máximo. capacidade da mochila. O valor máximo sim.
dp[i][j]=dp[i-1][j-nums[i-1]]+nums[i-1]
Se você não deixar ir
dp[i][j]=dp[i -1][j]；
Pegue o máximo dos dois

A fórmula recursiva final e o código são os seguintes:

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

Também podemos escrever assim. O array bidimensional dp é do tipo booleano dp[i][j] indica se a soma dos primeiros i elementos do array pode formar uma soma de j. 0] = verdadeiro, o que significa que os primeiros 0 elementos (ou seja, nenhum elemento) podem formar uma soma de 0.código mostrado abaixo

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

Vemos que ao calcular o array bidimensional acima, o valor atual está relacionado apenas à linha acima, então podemos alterá-lo para unidimensional. Observe que o segundo loop for deve ser flashback, caso contrário o valor anterior será substituído. e o resultado estará errado, observe mais de perto.
dp[j] = (dp[j] || dp[j - nums [i - 1]]);
Você pode entender que o valor no final da mesma linha depende do anterior. Caso não seja um flashback, o valor anterior é modificado, o que causará um erro no cálculo do posterior.Vamos dar uma olhada no código

#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. Ideia de solução 2

Solução de algoritmo DFS

Cada elemento pode ser selecionado ou não. Você só precisa determinar se a soma dos elementos em todas as suas combinações possíveis é igual a soma/2. Podemos pensar nisso como uma árvore binária. elemento atual, e o nó filho direito representa a seleção do elemento atual. O nó filho indica que o elemento atual não está selecionado, conforme mostrado na figura abaixo. indica que o elemento atual não está selecionado.

Vamos primeiro dar uma olhada no código de implementação preliminar

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

Mas, infelizmente, como a quantidade de cálculo é muito grande, a operação atingirá o tempo limite. Podemos otimizá-la e dar uma olhada no código.

#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. Ideia de solução 3

Solução de operação de bits

Operações de bits podem ser usadas aqui, mas a chave está em algumas restrições na questão, como uma matriz não vazia de números inteiros positivos, os elementos em cada matriz não excederão 100, o tamanho da matriz não excederá 200, etc. .
O princípio é muito simples. Só precisamos aplicar para um array bits[soma+1] de tamanho soma+1. Os números no array podem ser apenas 0 e 1. Podemos imaginá-lo como um bit binário muito longo, porque. int e O tipo long é muito curto, estamos usando um array aqui. Então, toda vez que um elemento da matriz é percorrido, como m, o bit binário é deslocado para a esquerda em m bits e, em seguida, é feito OR com o bit binário original. Finalmente, determine se bits[soma/2] é 1 e retorne verdadeiro se for 1.A descrição do texto não é muito direta. Tomemos o Exemplo 1 como exemplo para fazer um desenho.

Por fim, você encontrará uma regra, ou seja, desde que o resultado final da operação seja 1, ele pode ser combinado usando elementos do array. Enquanto for 0, não pode ser combinado usando elementos do array. processo acima, o código é fácil de escrever. Como só precisamos determinar se o valor do meio no bit binário é 1, só precisamos calcular o bit inferior, e o bit superior não precisa ser calculado, porque é movido para a esquerda, e o bit superior bit não terá nenhum impacto no valor médio, então podemos fazer isso aqui. Uma pequena otimização e, finalmente, vamos dar uma olhada no código.

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