解決子集和問題的 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。因此輸出為 Found a subset with the給定 sum in first call。第二次呼叫中沒有給定總和的子集。

使用動態規劃的偽多項式時間

範例

<?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(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)，比遞歸解決方案更有效率。這兩種方法都可以用來解決子集和問題，動態規劃解決方案對於較大的輸入更有效。

以上是解決子集和問題的 PHP 程式的詳細內容。更多資訊請關注PHP中文網其他相關文章！