El problema de la suma de subconjuntos es un problema clásico en informática y programación dinámica. Dado un conjunto de números enteros positivos y una suma objetivo, la tarea es determinar si existe un subconjunto del conjunto dado cuyos elementos suman la suma objetivo.

Programa PHP para problemas de suma de subconjuntos

Usando una solución recursiva

Ejemplo

 $sum)
      return isSubsetSum($set, $n - 1, $sum);
   // Check if the sum can be obtained by either including or excluding the last element
   return isSubsetSum($set, $n - 1, $sum) ||
      isSubsetSum($set, $n - 1, $sum - $set[$n - 1]);
}
// Driver Code
$set = array(1, 7, 4, 9, 2);
$sum = 16;
$n = count($set);
if (isSubsetSum($set, $n, $sum) == true)
   echo "Found a subset with the given sum
";
else
   echo "No subset with the given sum
";
$sum = 25;
$n = count($set);
if (isSubsetSum($set, $n, $sum) == true)
   echo "Found a subset with the given sum.";
else
   echo "No subset with the given sum.";
?>

Producción

Found a subset with the given sum.
No subset with the given sum.

En el ejemplo proporcionado, el conjunto es [1, 7, 4, 9, 2] y las sumas objetivo son 16 y 25. La segunda llamada con una suma objetivo de 25 devuelve falso, lo que indica que no hay ningún subconjunto eso suma 25, por lo que el resultado fue Encontrado un subconjunto con la suma dada en la primera llamada. No hay subconjunto con la suma dada en segunda convocatoria.

Tiempo pseudopolinomial usando programación dinámica

Ejemplo

= $set[$i-1])
				$subset[$i][$j] =
					$subset[$i-1][$j] ||
					$subset[$i - 1][$j -
							$set[$i-1]];
		}
	}
	/* // uncomment this code to print table
	for (int i = 0; i 

Producción

Found a subset with given sum.

En el ejemplo proporcionado, el conjunto es [8, 15, 26, 35, 42, 59] y la suma objetivo es 50. La llamada a la función esSubsetSum($set, $ n, $sum) devuelve verdadero, lo que indica que existe un subconjunto [8, 42] en el conjunto que suma la suma objetivo de 50. Por lo tanto, la salida del código sería Encontré un subconjunto con la suma dada.

Conclusión

En conclusión, existen dos enfoques diferentes para resolver el problema de la suma de subconjuntos. La primera solución es un enfoque recursivo que comprueba si hay un subconjunto del conjunto dado con una suma igual a la suma objetivo. Utiliza retroceso para explorar todas las combinaciones posibles. Sin embargo, esta solución puede tener una complejidad temporal exponencial en el peor de los casos.

La segunda solución utiliza programación dinámica y resuelve el problema de la suma de subconjuntos de manera ascendente. Construye una tabla para almacenar resultados intermedios y determina de manera eficiente si existe un subconjunto con la suma dada. Este enfoque tiene una complejidad temporal de O(n*sum), lo que lo hace más eficiente que la solución recursiva. Ambos enfoques se pueden utilizar para resolver el problema de la suma de subconjuntos, siendo la solución de programación dinámica más eficiente para entradas más grandes.