-1

sumsubsetproblem についてwiki http://en.wikipedia.org/wiki/Subset_sum_problem#Pseudo-polynomial_time_dynamic_programming_solutionを読み、次の問題に適応できるかどうか疑問に思います。

n1 によって制限されたすべての可能なサブセット ss1、ss2 が必要です。n2 は 2 つのセット s1、s2 からの要素の数です。

S1 の要素を正の要素として使用し、s2 の要素を負の要素として使用して、サイズ n1 と n2 のサブセットの合計が 0 であるかどうかという質問に答えます。

ここでの私の特別な問題は、セットに 0 自体を含めることができることです。これらの要素をそれぞれ 1 または -1 に設定することでこれを解決できると思いました (1 は私の入力のメンバーではなく、(0,10,50,100,200,500) になります)。次の問題は、このアルゴリズムが私に「はい」か「いいえ」しか与えないことですが、私はこの答えをすでに知っています (前提条件です) 必要なのは結果です。

これはまだ十分に速いですか？OPがランタイムのリストを投稿したperl実装についてここで読んだことがあります.30要素の計算時間は30〜40秒で、私のニーズには遅すぎます.Javaで実装する必要があります.私が知っているように、perlよりもさらに遅い

よろしく

ダーク

4

1 に答える 1

0

S1 と S2 のそれぞれを順番に検討します。部分集合和の問題と同様に、S1 の要素の可能な部分集合を合計することによって計算できる数を示す配列を作成できます (S2 についても同様です)。S1 の 1 つまたは複数の要素を合計することによって結果ゼロを取得できるかどうかを示す追加のフラグを保持できます (S2 についても同様です)。

あとは、2 つの配列の結果を調べて、合計がゼロになる 2 つの数値を探し、両方のゼロ フラグが設定されているかどうかを確認するだけです。

これにかかる時間はわかりませんが、デスクトップ上の JVM には Just-In-Time コンパイラがあるため、デスクトップ上の JVM は Perl よりも高速であると予想されます。セット内の数値がとても違う。

于 2013-09-19T04:34:08.873 に答える