」工欲善其事,必先利其器。「—孔子《論語.錄靈公》
首頁 > 程式設計 > 子集和問題的 PHP 程式

子集和問題的 PHP 程式

發佈於2024-11-07
瀏覽:605

PHP Program for Subset Sum Problem

子集和問題是電腦科學和動態規劃中的經典問題。給定一組正整數和一個目標和,任務是確定是否存在給定集合的子集,其元素總和等於目標和。

子集與問題的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 

輸出

Found a subset with given sum.

在提供的範例中,集合為 [8, 15, 26, 35, 42, 59],目標和為 50。 函數呼叫isSubsetSum($set, $ n, $sum) 傳回true,表示集合中存在子集[8, 42],其總和為50 。因此,程式碼的輸出為找到具有給定總和的子集。

結論

總之,有兩種不同的方法來解決子集和問題。第一個解決方案是遞歸方法,檢查給定集合中是否存在總和等於目標總和的子集。它利用回溯來探索所有可能的組合。然而,該解決方案在最壞的情況下可能具有指數時間複雜度。

第二種解決方案利用動態規劃並以自下而上的方式解決子集和問題。它構造一個表來儲存中間結果,並有效地確定是否存在具有給定總和的子集。這種方法的時間複雜度為 O(n*sum),比遞歸解決方案更有效。這兩種方法都可以用來解決子集和問題,動態規劃解決方案對於較大的輸入更有效。

版本聲明 本文轉載於:https://www.tutorialspoint.com/php-program-for-subset-sum-problem如有侵犯,請聯絡[email protected]刪除
最新教學 更多>

免責聲明: 提供的所有資源部分來自互聯網,如果有侵犯您的版權或其他權益,請說明詳細緣由並提供版權或權益證明然後發到郵箱:[email protected] 我們會在第一時間內為您處理。

Copyright© 2022 湘ICP备2022001581号-3