PHP 用于子集和问题

子集和问题是计算机科学和动态规划中的经典问题。给定一组正整数和一个目标和，任务是确定是否存在给定集合的子集，其中的元素相加等于目标和。

PHP程序用于子集和问题

使用递归解决方案

示例

<?php
// A recursive solution for the subset sum problem
// Returns true if there is a subset of the set
// with a sum equal to the given sum
function isSubsetSum(set,n, sum)
{
   // Base Cases
   if (sum == 0)
      return true;
   if (n == 0 &&sum != 0)
      return false;
   // If the last element is greater than the sum, then ignore it
   if (set[n - 1] > 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<br>";
else
   echo "No subset with the given sum<br>";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.";
?>

输出

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

在提供的例子中，集合是[1, 7, 4, 9, 2]，目标和是16和25。第二次调用目标和是25，返回false，表示没有子集的和为25。所以输出结果为第一次调用找到了一个和为给定值的子集。第二次调用没有找到和为给定值的子集。

动态规划的伪多项式时间

示例

<?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 isubset = 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");
    }*/
    returnsubset[n][sum];
}
// Driver program to test above function
set = array(8,15,26,35,42,59);sum = 50;
n = count(set);
if (isSubsetSum(set,n, $sum) == true)
    echo "Found a subset with given sum.";
else
    echo "No subset with given sum.";
?>

输出

Found a subset with given sum.

在提供的示例中，集合是[8, 15, 26, 35, 42, 59]，目标和为50。函数调用isSubsetSum（ set， n， $ sum）返回true，表示集合中存在一个子集[8, 42]，它们的和等于目标和50.因此，代码的输出将是Found a subset with the given sum.

结论

总之，解决子集和问题有两种不同的方法。第一种方法是使用递归的方法，检查给定集合中是否存在和等于目标和的子集。它利用回溯法来探索所有可能的组合。然而，这种解决方案在最坏情况下可能具有指数时间复杂度。

第二种解决方案利用动态规划以自底向上的方式解决子集和问题。它构建一个表格来存储中间结果，并高效地确定是否存在和为给定值的子集。这种方法的时间复杂度为O(n*sum)，比递归解决方案更高效。这两种方法都可以用来解决子集和问题，对于较大的输入，动态规划解决方案更加高效。