資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學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 的子集。因此，輸出為“第一次呼叫中找到了具有給定和的子集。第二次呼叫中沒有具有給定和的子集。”
使用動態規劃的偽多項式時間演算法
示例
<?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)，使其比遞迴解法更有效。兩種方法都可以用來解決子集和問題，而動態規劃解法對於較大的輸入更有效。
更新於：2023年8月1日
211 次瀏覽
廣告