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

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

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

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

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

配列pを初期化する p[0] = 0, それ以外は -1 をセット。
集合からひとつ要素を取り出し、n とする。
配列pを最後から見ていき、-1 以外のインデックスを i とする
n + i <= target で、p[n+i] == -1 ならば、p[n+i] に n を代入する。
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

using System.Collections.Generic;
using System.Linq;

namespace SubsetSumProblem {
    // 部分和問題を動的計画法で解く
    public class SubsetSumProblem {
        private int[] _nums;
        // numsの要素は、正整数とする
        public SubsetSumProblem(int[] nums) {
            this._nums = nums.OrderBy(n => n).ToArray();
        }

private int[] _work;
        public int[] Solve(int target) {
            _work = new int[target + 1];
            _work[0] = 0;
            for (int i = 1; i <= target; i++)
                _work[i] = -1;
            foreach (var n in _nums) {
                for (int i = target; i >= 0; i--) {
                    if (_work[i] == -1)
                        continue;
                    if (i + n <= target && _work[i + n] == -1)
                        _work[i + n] = n;
                }
                if (_work[target] != -1)
                    break;
            }
            return ToResult(_work, target);
        }

// 作業用の配列から、部分集合を求める
        private int[] ToResult(int[] work, int target) {
            List<int> result = new List<int>();
            if (work[target] != -1) {
                while (target > 0) {
                    result.Add(work[target]);
                    target = target - work[target];
                }
            }
            return (result as IEnumerable<int>).Reverse().ToArray();
        }
    }
}

■MainPage.cs

■MainPage.xaml