Program PHP untuk Masalah Jumlah Subset

Masalah Jumlah 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 elemennya ditambah kepada jumlah sasaran.

Program PHP untuk Masalah Jumlah Subset

Menggunakan 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 disediakan, 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 menambah sehingga 25.jadi output datang sebagai Menemui subset dengan jumlah yang diberikan dalam panggilan pertama. Tiada subset dengan jumlah yang diberikan dalam panggilan kedua.

Masa pseudo-polinomial 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 ialahSubsetSum($set, $n, $sum) mengembalikan benar, menunjukkan bahawa terdapat subset [8, 42] dalam set yang menjumlahkan sehingga jumlah sasaran 50. Oleh itu, output kod akan Ditemui subset dengan jumlah yang diberikan.

Kesimpulan

Kesimpulannya, terdapat dua pendekatan berbeza untuk menyelesaikan masalah jumlah subset. Penyelesaian pertama ialah pendekatan rekursif yang menyemak sama ada terdapat subset set yang diberikan dengan jumlah yang sama dengan jumlah sasaran. Ia menggunakan penjejakan ke 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 hasil perantaraan dan dengan cekap menentukan sama ada subset dengan jumlah yang diberikan wujud. Pendekatan ini mempunyai kerumitan masa O(n*sum), menjadikannya lebih cekap daripada penyelesaian rekursif. Kedua-dua pendekatan 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!