部分集合和問題は、コンピューター サイエンスと動的プログラミングにおける古典的な問題です。正の整数のセットと目標合計が与えられた場合、タスクは、要素の合計が目標合計に達する、指定されたセットのサブセットが存在するかどうかを判断することです。

部分集合和問題用の 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 の 2 番目の呼び出しは false を返し、サブセットがないことを示します。合計は 25 になります。そのため、出力は「最初の呼び出しで指定された合計を持つサブセットが見つかりました」として返されました。 2 番目の呼び出しに指定された合計を持つサブセットがありません。

動的計画法を使用した擬似多項式時間

例

= $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 です。関数呼び出しは SubsetSum($set, $ n, $sum) は true を返し、合計が目標の合計 50 になるサブセット [8, 42] がセット内に存在することを示します。したがって、コードの出力は次のようになります。指定された合計を持つサブセットが見つかりました。

結論

結論として、部分集合和問題を解決するには 2 つの異なるアプローチがあります。最初の解決策は、合計が目標合計と等しい指定されたセットのサブセットがあるかどうかを確認する再帰的アプローチです。バックトラッキングを利用して、考えられるすべての組み合わせを探索します。ただし、このソリューションは、最悪の場合、時間の複雑さが指数関数的に増加する可能性があります。

2 番目の解決策は動的計画法を利用し、ボトムアップ方式で部分集合和の問題を解決します。中間結果を保存するテーブルを構築し、指定された合計を持つサブセットが存在するかどうかを効率的に判断します。このアプローチの時間計算量は O(n*sum) であるため、再帰的ソリューションよりも効率的です。どちらのアプローチもサブセット和問題を解決するために使用でき、入力が大きい場合には動的計画法ソリューションの方が効率的です。