部分集合和問題用のPHPプログラム

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

サブセットと質問用の PHP プログラム

再帰的ソリューションを使用する

この例では、セットは [1, 7, 4, 9, 2] で、ターゲット合計は 16 と 25 です。ターゲット合計が 25 である 2 番目の呼び出しは false を返し、合計が 25 になるサブセットがないことを示します。したがって、出力は「最初の呼び出しで指定された合計を持つサブセットが見つかりました」となります。 2 番目の呼び出しには、指定された合計のサブセットはありません。

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

この例では、セットは [8, 15, 26, 35, 42, 59] で、ターゲット合計は 50 です。関数呼び出し isSubsetSum(

set,

n,

sum) は true を返し、セット内にサブセット [8, 42] があることを示します。これを合計すると、目標合計の 50 に等しくなります。したがって、コードは指定された合計を持つサブセットを見つけます。

要約すると、部分集合和問題を解決するには 2 つの異なる方法があります。最初の解決策は、合計がターゲット合計と等しい指定されたセットのサブセットが存在するかどうかを確認する再帰的アプローチです。バックトラッキングを使用して、考えられるすべての組み合わせを調査します。ただし、この解決策は、最悪の場合、時間の複雑さが指数関数的に増加する可能性があります。 2 番目の解決策は動的プログラミングを利用し、ボトムアップ方式で部分集合和の問題を解決します。中間結果を保存するテーブルを構築し、指定された合計を持つサブセットが存在するかどうかを効果的に判断します。このアプローチの時間計算量は O(n*sum) であり、再帰的解決策よりも効率的です。どちらの方法もサブセット和問題を解決するために使用でき、入力が大きい場合には動的計画法ソリューションの方が効率的です。

以上が部分集合和問題用のPHPプログラムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。