部分和問題を動的計画法で解く

問題
与えられた n 個の整数(集合A)と 整数 X があった時に、集合Aから任意の数の整数を選び、
その数の和(部分和)が、X に等しくなるようにしてください。


問  [3,7,8,12,13,18] の部分和が 27 になる部分集合を求めよ。
答  存在する。[7,8,12]

動的計画法(Dynamic Programming)という方法で、部分和問題(Subset Sum Problem)を解いています。


その手順は、以下の通りです。

  1.  配列pを初期化する p[0] = 0, それ以外は -1 をセット。
  2.  集合からひとつ要素を取り出し、n とする。
  3.  配列pを最後から見ていき、-1 以外のインデックスを i とする
  4.  n + i <= target で、p[n+i] == -1 ならば、p[n+i] に n を代入する。
  5.  1 に戻って処理を繰り返す。
という処理になります。

いくつかのWebサイトをみると bool型の配列を(target+1要素分)用意し、その数になる場合には、
true を入れることにより、解が存在するかどうかが分かるようにしていますが、ここでは、int型の
配列を用意し、最後に加えた値を入れるようにしています。
こうすることで、どの組み合わせで結果が得られたかが、後から分かるようになります。

例えば、3,7,1,2 の集合から 和が 9 になる解を求める場合を考えます。
初期状態は以下の通り。

      0   1   2   3   4   5   6   7   8   9
   +---+---+---+---+---+---+---+---+---+---+
 0)| 0 |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+---+

初期値の -1 は、ここでは空白で表しています。
配列のインデックスが部分和を表しています。与えられた数は、9 なので、
部分和が 9以下の場合を調べようといことです。

先に示した処理をすると、配列は、以下のように変化していきます。

      0   1   2   3   4   5   6   7   8   9
   +---+---+---+---+---+---+---+---+---+---+
 1)| 0 |   |   | 3 |   |   |   |   |   |   |    集合 [3] についての部分和問題を解いた結果
   +---+---+---+---+---+---+---+---+---+---+    和が 3 となる部分集合が存在する

     0   1   2   3   4   5   6   7   8   9
   +---+---+---+---+---+---+---+---+---+---+
 2)| 0 |   |   | 3 |   |   |   | 7 |   |   |    集合 [3,7]についての部分和問題を解いた結果
   +---+---+---+---+---+---+---+---+---+---+    和が 3, 7 となる部分集合が存在する

     0   1   2   3   4   5   6   7   8   9
   +---+---+---+---+---+---+---+---+---+---+
 3)| 0 | 1 |   | 3 | 1 |   |   | 7 | 1 |   |    集合 [3,7,1]についての部分和問題を解いた結果  
   +---+---+---+---+---+---+---+---+---+---+    和が 1,3,4,7,8 となる部分集合が存在する

     0   1   2   3   4   5   6   7   8   9
   +---+---+---+---+---+---+---+---+---+---+
 4)| 0 | 1 | 2 | 3 | 1 | 2 | 2 | 7 | 1 | 2 |    集合 [3,7,1,2]についての部分和問題を解いた結果
   +---+---+---+---+---+---+---+---+---+---+    和が 1,2,3,4,5,6,7,8,9 となる部分集合が存在する

 

これだけだと分かりにくいので、ちょっと補足をします。
最初の要素 3 に対して処理をした後の配列の内容は

      0   1   2   3   4   5   6   7   8   9
   +---+---+---+---+---+---+---+---+---+---+
 1)| 0 |   |   | 3 |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+---+

となっています。
p[3] に 3が入っていますが、これは、3 (要素の値)を加えると 3(インデックスの値)になった
という意味で、部分和が 3 になる部分集合は [3] であるということです。

配列の最終的な状態は、

      0   1   2   3   4   5   6   7   8   9
   +---+---+---+---+---+---+---+---+---+---+
 4)| 0 | 1 | 2 | 3 | 1 | 2 | 2 | 7 | 1 | 2 |
   +---+---+---+---+---+---+---+---+---+---+


となります。この配列には、-1 の要素がありませんので、
[3,7,1,2]という集合からは、部分和 X に対して、1 <= X <= 9 のすべてに対して、部分集合が存在することを
示しています。

例えば、p[6] には、2が入っていますが、これは、 2 を足すと 6 になること示しています。
つまり、6 = 4 + 2 となることを示しています。
そこで、部分和 4 を表す p[4] を見ると、値が 1なので、1 を足して 4 になったことが分かります。
つまり、4 = 3 + 1 です。そこでさらに、部分和 3 を示す p[3] を見ると、
p[3] は、 3 なので、3 = 0 + 3 となり、
6 = 3 + 1 + 2 となることが分かるわけです。
つまり、部分和 6 となる部分集合は [3,1,2]となります。

なお、部分和 9 が求めるターゲットなので、同様に p[9]からたどっていけば、7 + 2 で 9 が求まることが
分かります。

これから分かるように、ターゲットである p[target] が、 -1 から別の値に変化したら、
解が求まったことになりますから、処理をここでストップしています。

以下、C#+Silverlightのコードです。

■SubsetSumProblem.cs
  

■MainPage.cs
 

■MainPage.xaml