Compartir tecnología

【1.5】Programación dinámica: solución para particionar subconjuntos de sumas iguales

2024-07-12

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

1. Problema


Se le proporciona una matriz de números no vacía que contiene solo números enteros positivos. Juzgue si esta matriz se puede dividir en dos subconjuntos para que la suma de los elementos de los dos subconjuntos sea igual.

2. Idea de solución 1

Solución de programación dinámica

Este problema no se puede resolver utilizando el algoritmo de retroceso. Si la cantidad de datos es grande, expirará. Podemos utilizar programación dinámica.
Esta pregunta determina si la suma de los elementos de las dos partes es igual cuando la matriz se divide en dos partes. Primero debemos calcular la suma de todos los elementos de la matriz y luego determinar si la suma es un número par: si no es un número par, significa que no se puede dividir en dos partes completamente iguales y devolverá falso directamente.
Si es un número par, solo necesitamos determinar si hay algunos elementos cuya suma es igual a suma/2. Si es igual a suma/2, entonces el resto también debe ser igual a suma/2, lo que significa que. Podemos dividir la matriz en dos partes con elementos iguales.
Entonces el problema es muy claro en este momento. Suponiendo que suma/2 es la capacidad de una mochila, solo necesitamos encontrar algunos elementos y ponerlos en la mochila si la suma máxima de los elementos en la mochila es igual a la suma. /2, significa que podemos dividir el array en dos porciones iguales. ¿No es este el clásico problema de la mochila 0-1? El problema básico de la mochila en la serie de problemas de la mochila se puede leer a continuación para obtener más detalles. No repetiré la introducción aquí. Buscamos su fórmula de recursividad y definimos dp[i][j] para representar el valor máximo obtenido al poner el i-ésimo artículo en una mochila con capacidad j.
El valor del elemento i-ésimo es nums [i -1]:
Si nums [i -1]>j, significa que la capacidad de la mochila no es suficiente y el i-ésimo artículo no se puede colocar, por lo que no podemos seleccionar el i-ésimo artículo, entonces
dp[i][j]=dp[i -1][j]；
Si nums [i -1] <= j, significa que el elemento j se puede poner en la mochila. Podemos elegir ponerlo o no, solo tomamos el valor máximo. Si lo ponemos, ocupará parte del. Capacidad de la mochila. El valor máximo sí.
dp[i][j]=dp[i-1][j-nums[i-1]]+nums[i-1]
Si no te sueltas
dp[i][j]=dp[i -1][j]；
Toma el máximo de los dos.

La fórmula y el código recursivos finales son los siguientes:

  1. #include <vector>
  2.  
  3. bool canPartition(std::vector<int>& nums) {
  4.     // 计算数组中所有元素的和
  5.     int sum = 0;
  6.     for (int num : nums) {
  7.         sum += num;
  8.     }
  9.     // 如果sum是奇数，说明数组不可能分成完全相等的两份
  10.     if ((sum & 1) == 1) {
  11.         return false;
  12.     }
  13.     // sum除以2
  14.     int target = sum >> 1;
  15.     int length = nums.size();
  16.     std::vector<std::vector<int>> dp(length + 1, std::vector<int>(target + 1, 0));
  17.     for (int i = 1; i <= length; ++i) {
  18.         for (int j = 1; j <= target; ++j) {
  19.             // 下面是递推公式
  20.             if (j >= nums[i - 1]) {
  21.                 dp[i][j] = std::max(dp[i - 1][j], dp[i - 1][j - nums[i - 1]] + nums[i - 1]);
  22.             } else {
  23.                 dp[i][j] = dp[i - 1][j];
  24.             }
  25.         }
  26.     }
  27.     // 判断背包最大是否能存放和为target的元素
  28.     return dp[length][target] == target;
  29. }

También podemos escribir así. La matriz bidimensional dp es de tipo booleano. dp [i] [j] indica si la suma de los primeros i elementos de la matriz puede formar una suma de j. 0] = verdadero, lo que significa que los primeros 0 elementos (es decir, ningún elemento) pueden formar una suma de 0.El código se muestra a continuación.

  1. #include <vector>
  2.  
  3. bool canPartition(std::vector<int>& nums) {
  4.     // 计算数组中所有元素的和
  5.     int sum = 0;
  6.     for (int num : nums) {
  7.         sum += num;
  8.     }
  9.     // 如果sum是奇数，说明数组不可能分成完全相等的两份
  10.     if ((sum & 1) == 1) {
  11.         return false;
  12.     }
  13.     // sum除以2得到target
  14.     int target = sum >> 1;
  15.     int length = nums.size();
  16.     std::vector<std::vector<bool>> dp(length + 1, std::vector<bool>(target + 1, false));
  17.     // base case
  18.     dp[0][0] = true;
  19.     for (int i = 1; i <= length; ++i) {
  20.         for (int j = 0; j <= target; ++j) {
  21.             // 递推公式
  22.             if (j >= nums[i - 1]) {
  23.                 dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
  24.             } else {
  25.                 dp[i][j] = dp[i - 1][j];
  26.             }
  27.         }
  28.     }
  29.     // 返回能否找到和为target的子集
  30.     return dp[length][target];
  31. }

Vemos que al calcular la matriz bidimensional anterior, el valor actual solo está relacionado con la fila anterior, por lo que podemos cambiarlo a unidimensional. Tenga en cuenta que el segundo bucle for debe ser un flashback; de lo contrario, se sobrescribirá el valor anterior. y el resultado será incorrecto, mire más de cerca.
dp[j] = (dp[j] || dp[j - nums [i - 1]]);
Se puede entender que el valor al final de la misma línea depende del anterior. Si no es un flashback, se modifica el valor anterior, lo que provocará un error en el cálculo del posterior.Echemos un vistazo al código.

  1. #include <vector>
  2.  
  3. bool canPartition(std::vector<int>& nums) {
  4.     // 计算数组中所有元素的和
  5.     int sum = 0;
  6.     for (int num : nums) {
  7.         sum += num;
  8.     }
  9.     // 如果sum是奇数，说明数组不可能分成完全相等的两份
  10.     if ((sum & 1) == 1) {
  11.         return false;
  12.     }
  13.     // sum除以2得到target
  14.     int target = sum >> 1;
  15.     int length = nums.size();
  16.     std::vector<bool> dp(target + 1, false);
  17.     // base case
  18.     dp[0] = true;
  19.     for (int i = 0; i < length; ++i) {
  20.         // 注意这里j要倒序
  21.         for (int j = target; j >= nums[i]; --j) {
  22.             // 递推公式
  23.             dp[j] = dp[j] || dp[j - nums[i]];
  24.         }
  25.     }
  26.     // 返回能否找到和为target的子集
  27.     return dp[target];
  28. }

3. Idea de solución 2

Solución de algoritmo DFS

Cada elemento se puede seleccionar o no. Solo necesita determinar si la suma de los elementos en todas sus combinaciones posibles es igual a suma/2. Podemos pensar en ello como un árbol binario. El nodo secundario izquierdo representa la selección. elemento actual, y el nodo secundario derecho representa la selección del elemento actual. El nodo secundario indica que el elemento actual no está seleccionado, como se muestra en la figura siguiente. El nodo naranja indica que el elemento actual está seleccionado y el nodo azul. indica que el elemento actual no está seleccionado.

Primero echemos un vistazo al código de implementación preliminar.

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

Pero desafortunadamente, debido a que la cantidad de cálculo es demasiado grande, la operación se agotará. Podemos optimizarla y echar un vistazo al código.

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

4. Idea de solución 3

Solución de operación de bits

Aquí se pueden usar operaciones de bits, pero la clave radica en algunas restricciones en la pregunta, como una matriz no vacía de números enteros positivos, los elementos en cada matriz no excederán 100, el tamaño de la matriz no excederá 200, etc. .
El principio es muy simple. Solo necesitamos solicitar una matriz de bits [suma + 1] de tamaño suma + 1. Los números en la matriz solo pueden ser 0 y 1. Podemos imaginarlo como un bit binario muy largo, porque. int y El tipo largo es demasiado corto, aquí estamos usando una matriz. Luego, cada vez que se atraviesa un elemento de la matriz, como m, el bit binario se desplaza hacia la izquierda m bits y luego se aplica una operación OR con el bit binario original. Finalmente, determine si bits [suma/2] es 1 y devuelva verdadero si es 1.La descripción del texto no es muy sencilla. Tomemos el ejemplo 1 como ejemplo para hacer un dibujo.

Finalmente, encontrará una regla, es decir, siempre que el resultado final de la operación sea 1, se puede combinar usando elementos en la matriz. Mientras sea 0, no se puede combinar usando elementos en la matriz. proceso anterior., el código es fácil de escribir. Debido a que solo necesitamos determinar si el valor medio en el bit binario es 1, solo necesitamos calcular el bit bajo, y no es necesario calcular el bit alto en absoluto, porque se mueve hacia la izquierda y el bit alto bit no tendrá ningún impacto en el valor medio, así que podemos hacerlo aquí. Una pequeña optimización y finalmente veamos el código.

  1. #include <vector>
  2.  
  3. bool canPartition(std::vector<int>& nums) {
  4.     // 计算数组中所有数字的和
  5.     int sum = 0;
  6.     for (int n : nums) {
  7.         sum += n;
  8.     }
  9.     // 如果sum是奇数，直接返回false
  10.     if ((sum & 1) == 1) {
  11.         return false;
  12.     }
  13.     int len = sum / 2;
  14.     // 这里bits的长度是len+1，因为我们只需要计算低位就行了，没必要计算所有的
  15.     std::vector<char> bits(len + 1, 0);
  16.     bits[0] = 1;
  17.     for (int num : nums) {
  18.         for (int j = len - num; j >= 0; j--) {
  19.             bits[j + num] |= bits[j];
  20.         }
  21.         // 判断中位数如果是1，说明可以分成两种相等的子集，直接返回true，不需要再计算了
  22.         if ((bits[len] & 1) != 0) {
  23.             return true;
  24.         }
  25.     }
  26.     return false;
  27. }

Perfil personal

Se ha dedicado a la investigación de tecnología durante más de 30 años y domina varios lenguajes como java, linux, javascript, php, css, etc. Ha realizado muchas contribuciones en el campo del código abierto. Estación de documentación para desarrolladores para compartir algunos problemas en el desarrollo de tecnología para referencia futura.

Mi informacion de contacto

Correo