Program PHP untuk masalah jumlah subset

Jumlah masalah subset ialah masalah klasik dalam sains komputer dan pengaturcaraan dinamik. Memandangkan set integer positif dan jumlah sasaran, tugasnya adalah untuk menentukan sama ada wujud subset set yang diberikan yang jumlah elemennya sama dengan jumlah sasaran.

Program PHP untuk subset dan soalan

Gunakan penyelesaian rekursif

Contoh

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

Output

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

Dalam contoh yang diberikan, set ialah [1, 7, 4, 9, 2] dan jumlah sasaran ialah 16 dan 25. Panggilan kedua dengan jumlah sasaran 25 mengembalikan palsu, menunjukkan bahawa tiada subset yang berjumlah 25. Jadi outputnya Ditemui subset dengan jumlah yang diberikan dalam panggilan pertama. Tiada subset jumlah yang diberikan dalam panggilan kedua.

Masa pseudopolynomial menggunakan pengaturcaraan dinamik

Contoh

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

Output

Found a subset with given sum.

Dalam contoh yang diberikan, set ialah [8, 15, 26, 35, 42, 59] dan jumlah sasaran ialah 50. Panggilan fungsi isSubsetSum($set, $n, $sum) mengembalikan benar, menunjukkan bahawa terdapat subset [8, 42] dalam set yang menjumlahkan sehingga jumlah sasaran 50. Jadi kod akan mencari subset dengan jumlah yang diberikan.

Kesimpulan

Ringkasnya, terdapat dua cara berbeza untuk menyelesaikan masalah jumlah subset. Penyelesaian pertama ialah pendekatan rekursif yang menyemak sama ada terdapat subset set yang diberikan yang jumlahnya sama dengan jumlah sasaran. Ia menggunakan penjejakan belakang untuk meneroka semua kombinasi yang mungkin. Walau bagaimanapun, penyelesaian ini mungkin mempunyai kerumitan masa eksponen dalam kes yang paling teruk.

Penyelesaian kedua menggunakan pengaturcaraan dinamik dan menyelesaikan masalah jumlah subset dengan cara bawah ke atas. Ia membina jadual untuk menyimpan keputusan perantaraan dan dengan cekap menentukan sama ada terdapat subset dengan jumlah tertentu. Pendekatan ini mempunyai kerumitan masa O(n*sum) dan lebih cekap daripada penyelesaian rekursif. Kedua-dua kaedah boleh digunakan untuk menyelesaikan masalah jumlah subset, dengan penyelesaian pengaturcaraan dinamik menjadi lebih cekap untuk input yang lebih besar.

Atas ialah kandungan terperinci Program PHP untuk masalah jumlah subset. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!