6

私はいくつかのアルゴリズムプログラミングの問題に取り組んできましたが、1つについて質問があります。問題は、この質問で参照されているものと同じです。USACO：サブセット（非効率的）

高Nには遅すぎるいくつかの（動的ではない）ソリューションをコーディングすることができました。少しごまかして、オンラインでいくつかのソリューションを検索する必要がありました。高速アルゴリズムは簡単ですが、答えを知っていても、問題から答えに至る方法がわかりません。等しい合計のサブセットが形成される方法でパターンを見ることができますが、それらのパターンとアルゴリズムソリューションの間のリンクはわかりません。

問題（上記のリンク）は次のとおりです。

1からN（1 <= N <= 39）までの連続する整数のセットが与えられた場合、合計が同じである2つのサブセットにセットを分割できる方法はいくつありますか？たとえば、{1,2,3}は一方向に分割できます：{1,2}{3}。

より大きなセットの場合、答えは0（N *（N + 1）/ 2が奇数の場合）であるか、次の単純なアルゴリズムによって与えられます。

  arr = array of int with (N*(N+1)/4)+1 elements
  arr[0]=1  // all other elements initialized to 0
  for i = 1 to N
    for j = N*(N+1) / 4 downto i
      add arr[j-i] to arr[j]
  subsetpaircount = arr[N*(N+1)/4] / 2

繰り返しになりますが、アルゴリズムがどのように機能するかを確認できます。printステートメントを挿入したので、アルゴリズムがどのように機能するかを「見る」ことができます。アルゴリズムの操作が、2セットのパーティションが生成されるさまざまな方法のパターンにどのようにリンクしているかがわかりません。

リンクされた質問の回答は関連があるかもしれませんが、それがどのように機能するかを接続することもできません：「これは多項式（x ^ 1 + 1 / x）（x ^ 2 + 1 / x ^ 2）...（x ^ n + 1 / x ^ n）。..。 "

誰かが私との関係を明確にしたり、この特定の問題を説明するいくつかの参考資料を教えてもらえますか？ありがとう。

4

2 に答える 2

7

セットS = {1,...,N}が等しい合計で2つのサブセットに分割されている場合、その合計はS;の合計の半分である必要があります。の合計はでSあるN(N+1)/2ため、パーティション内の各サブセットの合計はである必要がありますN(N+1)/4。また、整数であるN(N+1)/2必要があるため、偶数である必要があります。

したがって、質問は、合計が。であるSのサブセットの数を見つけることになりN(N+1)/4ます。各パーティションにはそのようなサブセットが2つ含まれており、2つのパーティションがサブセットを共有していないため、パーティションの総数はこの数のちょうど半分になります。

それだけは明らかなはずです。

ここで、任意のセットについて、S合計が、になるサブセットをリストします。このようなサブセットには最大値が必要であり、これはの要素である必要があります。最大値は、の最大要素であるか、の最大要素よりも小さい必要があります。これらの2つのサブセットのグループは異なるため、別々に列挙できます。の最大要素と呼びましょう。kkSSSSS Smax

2番目のグループは単純です。それは単純にそのサブセットの合計が。になります。サブセットリスターを再帰的に呼び出すことで、それらを見つけることができます。ただし、最初のグループはほぼ同じように単純です。グループ内の各セットにはが含まれ、残りの要素は合計が、になるセットであり、これも再帰的にリストできます。再帰を完了するために、が空集合の場合、が正確に1つの適格サブセット（空集合自体）があり、kが0でない場合、適格サブセットがないことに注意してください。再帰ごとにから1つの要素が削除されるため、最終的には終了条件に到達する必要があります。S - { Smax }kSmaxS - { Smax }k - SmaxSk = 0S

S上記の再帰関数で使用されるサブセットはから1までの数字にすぎないことは明らかです。したがって、完全に削除して、再帰を次のように記述できます。SmaxS

Subsets(min, max, k) =
  Subsets(min, max - 1, k)
  ⋃ { {max, P} | P ∈ Subsets(min, max - 1, k - max) }

ただし、パーティションの数だけが必要なので、少し単純化できます。

Count_Subsets(min, max, k) =
  Count_Subsets(min, max - 1, k)
  + Count_Subsets(min, max - 1, k - max)

終了条件を追加して、再帰を完了する必要があります。

If min > max, Count_Subsets(min, max, k) = 1 if k = 0; otherwise 0

（実際、再帰は1、kがに減少したときの値を意味することを示すのは簡単です。が0、未満の0場合は、終了条件をはるかに早く発生させることができます。）k0

これにより、カウントの単純な再帰が得られます。ただし、それ自体が2回呼び出されるため、逆方向に作業する方が適切です（「動的計画法」）。を計算するCount_Subsets(1, N, N*(N+1)/4)必要があります。これにはCount_Subsets(1, max, k)、1からNまでのmaxのすべての値、および0からN *（N + 1）/4までのkのすべての値の値を計算する必要があります。これを行うには、max = 0から開始し、min=Nに達するまで作業を進めます。これがまさにアルゴリズムの機能です。iはmax、であり、配列は0から。までのkの値のセットですN(N+1)/4。

ちなみに、上記の説明から明らかなように、ではなく、によってa[j]インクリメントする必要がありますa[j - i]a[j - 1]

于 2013-01-24T23:09:26.237 に答える
1

疑似コードに誤りがあり、混乱を引き起こしている可能性があると思います。私はラインを期待します

add arr[j-1] to arr[j]

することが

add arr[j-i] to arr[j]

これが事実であると仮定すると、この問題について考える方法は、i に対するループの各反復の開始時に、配列 arr[j] には、整数 1、2、 ...,i-1 で、選択した整数の合計が正確に j になるようにします。

開始時には、i=1 であるため、サブセットの唯一の選択肢は、合計が 1 に等しい空のサブセットです。

これが、arr[0]=1 (空のサブセットを使用して合計 0 を取得することを表す) であり、他のすべてのエントリが 0 である理由です (ゼロ以外の合計を取得する方法がないため)。

それ以降、反復の各パスは、番号 i をサブセットに追加することを検討します。合計 j を取得する方法の数は、i が含まれているかどうかによって異なります。

i が含まれていない場合、前と同じ数のウェイがあります (つまり、arr[j])。

i が含まれている場合、i を含む j の合計を得るには、合計 ji を持つ 1,..,i-1 のすべてのサブセットに i を追加する必要があります。設計上、インデックス ji を見ると、配列には正確にこの数値が含まれます。

したがって、j の合計を取得する方法の総数は arr[j]+arr[ji] になります。

i ループが完了すると、arr は、サブセットを選択して任意の合計を取得する方法の数を示します。1,2,..,n の合計は n*(n-1)/2 であることがわかっているため、この値の半分に達するサブセットの数を数えると、パーティションを等しい合計に数えることになります。

実際には、これは {1,2}/{3] と {3}/{1,2} を別々の解としてカウントするため、2 倍多くカウントされ、最終的な答えは 2 で除算されます。

于 2013-01-24T23:04:10.040 に答える