Dado um conjunto de inteiros não negativos e uma soma de valores , determine se há um subconjunto do conjunto fornecido com soma igual à soma fornecida .
Exemplo:

Input:  set[] = {3, 34, 4, 12, 5, 2}, sum = 9
Output:  True  //There is a subset (4, 5) with sum 9.

<?php
// A recursive solution for subset sum problem
  
// Returns true if there is a subset of set
// with sun equal to given sum
function isSubsetSum($set, $n, $sum)
{
    // Base Cases
    if ($sum == 0)
        return true;
    if ($n == 0 && $sum != 0)
        return false;
      
    // If last element is greater
    // than sum, then ignore it
    if ($set[$n - 1] > $sum)
        return isSubsetSum($set, $n - 1, $sum);
      
    /* else, check if sum can be 
       obtained by any of the following
        (a) including the last element
        (b) excluding the last element */
    return isSubsetSum($set, $n - 1, $sum) || 
        isSubsetSum($set, $n - 1, 
                    $sum - $set[$n - 1]);
}
  
// Driver Code
$set = array(3, 34, 4, 12, 5, 2);
$sum = 9;
$n = 6;
  
if (isSubsetSum($set, $n, $sum) == true)
    echo"Found a subset with given sum";
else
    echo "No subset with given sum";
      
// This code is contributed by Anuj_67 
?>

<?php
// A Dynamic Programming solution for 
// subset sum problem
  
// Returns true if there is a subset of
// set[] with sun equal to given sum
function isSubsetSum( $set, $n, $sum)
{
    // The value of subset[i][j] will
    // be true if there is a subset of
    // set[0..j-1] with sum equal to i
    $subset = array(array());
  
    // If sum is 0, then answer is true
    for ( $i = 0; $i <= $n; $i++)
        $subset[$i][0] = true;
  
    // If sum is not 0 and set is empty,
    // then answer is false
    for ( $i = 1; $i <= $sum; $i++)
        $subset[0][$i] = false;
  
    // Fill the subset table in bottom
    // up manner
    for ($i = 1; $i <= $n; $i++)
    {
        for ($j = 1; $j <= $sum; $j++)
        {
            if($j < $set[$i-1])
                $subset[$i][$j] = 
                      $subset[$i-1][$j];
            if ($j >= $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 <= n; i++)
    {
    for (int j = 0; j <= sum; j++)
        printf ("%4d", subset[i][j]);
    printf("n");
    }*/
  
    return $subset[$n][$sum];
}
  
// Driver program to test above function
$set = array(3, 34, 4, 12, 5, 2);
$sum = 9;
$n = count($set);
  
if (isSubsetSum($set, $n, $sum) == true)
    echo "Found a subset with given sum";
else
    echo "No subset with given sum";
  
// This code is contributed by anuj_67.
?>

Artigo contribuído por:

GeeksforGeeks

Vote na dificuldade

<button class="btn" data-gfg-action="article-difficulty" data-rating="1">Fácil</button> <button class="btn" data-gfg-action="article-difficulty" data-rating="2">Normal</button> <button class="btn" data-gfg-action="article-difficulty" data-rating="3">Médio</button> <button class="btn" data-gfg-action="article-difficulty" data-rating="4">Duro</button> <button class="btn" data-gfg-action="article-difficulty" data-rating="5">Especialista</button>

Aprimorado por:

• nidhi_biet

Tags de artigo:

• Programas PHP

Reportar problema