Jadual Kandungan
Gunakan penyelesaian rekursif
Contoh
Output
Kesimpulan
Rumah pembangunan bahagian belakang tutorial php Program PHP untuk masalah jumlah subset

Program PHP untuk masalah jumlah subset

Sep 19, 2023 am 09:53 AM
php soalan koleksi kanak-kanak

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.";
?>
Salin selepas log masuk

Output

Found a subset with the given sum.
No subset with the given sum.
Salin selepas log masuk

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.";
?>
Salin selepas log masuk

Output

Found a subset with given sum.
Salin selepas log masuk

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!

Kenyataan Laman Web ini
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn

Tag artikel panas

Notepad++7.3.1

Notepad++7.3.1

Editor kod yang mudah digunakan dan percuma

SublimeText3 versi Cina

SublimeText3 versi Cina

Versi Cina, sangat mudah digunakan

Hantar Studio 13.0.1

Hantar Studio 13.0.1

Persekitaran pembangunan bersepadu PHP yang berkuasa

Dreamweaver CS6

Dreamweaver CS6

Alat pembangunan web visual

SublimeText3 versi Mac

SublimeText3 versi Mac

Perisian penyuntingan kod peringkat Tuhan (SublimeText3)

Panduan Pemasangan dan Naik Taraf PHP 8.4 untuk Ubuntu dan Debian Panduan Pemasangan dan Naik Taraf PHP 8.4 untuk Ubuntu dan Debian Dec 24, 2024 pm 04:42 PM

Panduan Pemasangan dan Naik Taraf PHP 8.4 untuk Ubuntu dan Debian

Tarikh dan Masa CakePHP Tarikh dan Masa CakePHP Sep 10, 2024 pm 05:27 PM

Tarikh dan Masa CakePHP

Konfigurasi Projek CakePHP Konfigurasi Projek CakePHP Sep 10, 2024 pm 05:25 PM

Konfigurasi Projek CakePHP

Muat naik Fail CakePHP Muat naik Fail CakePHP Sep 10, 2024 pm 05:27 PM

Muat naik Fail CakePHP

Penghalaan CakePHP Penghalaan CakePHP Sep 10, 2024 pm 05:25 PM

Penghalaan CakePHP

Bincangkan CakePHP Bincangkan CakePHP Sep 10, 2024 pm 05:28 PM

Bincangkan CakePHP

Cara Menyediakan Kod Visual Studio (Kod VS) untuk Pembangunan PHP Cara Menyediakan Kod Visual Studio (Kod VS) untuk Pembangunan PHP Dec 20, 2024 am 11:31 AM

Cara Menyediakan Kod Visual Studio (Kod VS) untuk Pembangunan PHP

Panduan Ringkas CakePHP Panduan Ringkas CakePHP Sep 10, 2024 pm 05:27 PM

Panduan Ringkas CakePHP

See all articles