O problema da soma de subconjuntos é um problema clássico em ciência da computação e programação dinâmica. Dado um conjunto de inteiros positivos e uma soma alvo, a tarefa é determinar se existe um subconjunto do conjunto dado cujos elementos somam a soma alvo.

Programa PHP para problema de soma de subconjuntos

Usando solução recursiva

Exemplo

 $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.";
?>

Saída

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

No exemplo fornecido, o conjunto é [1, 7, 4, 9, 2] e as somas alvo são 16 e 25. A segunda chamada com uma soma alvo de 25 retorna falso, indicando que não há subconjunto isso soma 25.então a saída veio como Encontrado um subconjunto com a soma fornecida na primeira chamada. Nenhum subconjunto com a soma fornecida na segunda chamada.

Tempo pseudo-polinomial usando programação dinâmica

Exemplo

= $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 

Saída

Found a subset with given sum.

No exemplo fornecido, o conjunto é [8, 15, 26, 35, 42, 59] e a soma alvo é 50. A chamada de função isSubsetSum($set, $ n, $sum) retorna verdadeiro, indicando que existe um subconjunto [8, 42] no conjunto que soma a soma alvo de 50. Portanto, a saída do código seria Encontrou um subconjunto com a soma fornecida.

Conclusão

Concluindo, existem duas abordagens diferentes para resolver o problema da soma do subconjunto. A primeira solução é uma abordagem recursiva que verifica se existe um subconjunto de um determinado conjunto com uma soma igual à soma alvo. Ele utiliza retrocesso para explorar todas as combinações possíveis. No entanto, esta solução pode ter uma complexidade de tempo exponencial no pior caso.

A segunda solução utiliza programação dinâmica e resolve o problema da soma dos subconjuntos de baixo para cima. Ele constrói uma tabela para armazenar resultados intermediários e determina com eficiência se existe um subconjunto com a soma fornecida. Esta abordagem tem uma complexidade de tempo de O(n*sum), tornando-a mais eficiente que a solução recursiva. Ambas as abordagens podem ser usadas para resolver o problema da soma dos subconjuntos, sendo a solução de programação dinâmica mais eficiente para entradas maiores.