DESTOON B2B网站管理系统
下载
DESTOON B2B网站管理系统是一套完善的B2B(电子商务)行业门户解决方案。系统基于PHP+MySQL开发，采用B/S架构，模板与程序分离，源码开放。模型化的开发思路，可扩展或删除任何功能；创新的缓存技术与数据库设计，可负载千万级别数据容量及访问。
子集和问题是计算机科学和动态规划中的一个经典问题。给定一组正整数和一个目标和，任务是确定是否存在给定集合的子集，其元素之和等于目标和。
子集和问题的 PHP 程序
使用递归解决方案
示例
$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.";
?>
输出
Found a subset with the given sum. No subset with the given sum.
在提供的示例中，集合为 [1, 7, 4, 9, 2]，目标和为 16 和 25。目标和为 25 的第二次调用返回 false，表示不存在子集加起来为 25。因此输出为 Found a subset with the给定 sum in first call。第二次调用中没有给定总和的子集。
使用动态规划的伪多项式时间
示例
= $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(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。因此，代码将找到具有给定总和的子集。
结论
总之，有两种不同的方法来解决子集和问题。第一个解决方案是递归方法，检查给定集合中是否存在总和等于目标总和的子集。它利用回溯来探索所有可能的组合。然而，该解决方案在最坏的情况下可能具有指数时间复杂度。
第二种解决方案利用动态规划并以自下而上的方式解决子集和问题。它构造一个表来存储中间结果，并有效地确定是否存在具有给定总和的子集。这种方法的时间复杂度为 O(n*sum)，比递归解决方案更有效。这两种方法都可以用来解决子集和问题，动态规划解决方案对于较大的输入更有效。
