部分和問題とは
与えられた N個の整数(集合A)と 整数 X があった時に、集合Aから任意の数の整数を選び、その数の和（部分和）が、X に等しくなるようにするという問題です。
例
問: [3, 7, 8, 12, 13, 18] の部分和が 27 になる部分集合を求めよ。
答: 存在する。[7, 8, 12]
動的計画法で解く
動的計画法(Dynamic Programming)という方法で、部分和問題(Subset Sum Problem)を解いています。
動的計画法というのは、決まったアルゴリズムがあるわけではありません。
- 問題を小さな問題(部分問題)に分割する
- その小さな問題を解いた結果を、次の部分問題に利用する
という手法を言います。
なお、この部分和問題(Subset Sum Problem)を解く手順は、以下の通りです。
- 配列pを用意する。サイズは、部分和+1とする (ここでは部分和をtargetと表す)。
- 配列pを初期化する
p[0] = 0, それ以外は -1 をセット。 - 集合からひとつ要素を取り出し、m とする。
- 配列pを最後から見ていき、-1 以外の時に、4の処理を行う (この時のインデックスをiとする)
-
i + m <= targetで、p[i+m] == -1ならば、p[i+m] に m を代入する。 -
p[target] != -1ならば、解が見つかったので、処理を終了する。p[target] == -1ならば 2. に戻って処理を繰り返す。
という処理になります。
いくつかのWebサイトをみると bool型の配列を（target+1要素分）用意し、その数になる場合には true を入れることにより、解が存在するかどうかが分かるようにしていますが、ここでは、int型の配列を用意し、最後に加えた値を入れるようにしています。こうすることで、どの組み合わせで結果が得られたかが後から分かるようになります。
4の処理の意味を簡単に説明します。
i + m <= targetの判断は、部分和(i+m)がtarget以下であるということです。
p[i+m] != -1 が成り立つということは、部分和がi+mとなるものがすでに見つかっていることを示しています。
p[i+m] に m を代入するということは、i+mの部分和が存在するということを示します。
例えば、i = 3, m = 1の時には、p[4] = 1となります。これは、部分和4となる部分集合が存在し、その一つの要素は 1 であることを意味しています。
例えば、3,7,1,2 の集合から 和が 9 になる解を求める場合を考えます。
初期状態は以下の通り。
0 1 2 3 4 5 6 7 8 9
+---+---+---+---+---+---+---+---+---+---+
0)| 0 | | | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+
初期値の -1 は、ここでは空白で表しています。
配列のインデックスが部分和を表しています。与えられた数は 9 なので、部分和が 9以下の場合を調べようといことです。
先に示した処理をすると、配列は、以下のように変化していきます。
m = 3の処理
要素が-1でないインデックスは、0です。p[0+3]を見ると-1ですので、p[0+3]にmの値3を入れいます。
0 1 2 3 4 5 6 7 8 9
+---+---+---+---+---+---+---+---+---+---+
1)| 0 | | | 3 | | | | | | | 集合 [3] についての部分和問題を解いた結果
+---+---+---+---+---+---+---+---+---+---+ 和が 3 となる部分集合が存在する
m = 7の処理
要素が-1でない一番大きいインデックスは3です。しかし、3+7 <= 9 ではないので、次のインデックスを見つけます。0が見つかります。なので、p[0+7]にmの値7を入れいます。
0 1 2 3 4 5 6 7 8 9
+---+---+---+---+---+---+---+---+---+---+
2)| 0 | | | 3 | | | | 7 | | | 集合 [3,7]についての部分和問題を解いた結果
+---+---+---+---+---+---+---+---+---+---+ 和が 3, 7 となる部分集合が存在する
m = 1の処理
要素が-1でない一番大きいインデックスは7です。しかし、7+1 <= 9 なので、p[7+1]にmの値1を入れいます。
次の要素が-1でないインデックスは3ですから、p[3+1]にmの値1を入れます。さらに同様にして、p[0+1]にmの値1を入れます。
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 となる部分集合が存在する
m = 2の処理
どうようにして、p[7+1], p[4+2], p[3+2], p[0+2] に、mの値2を入れます。
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 となり、部分和が 3 となる部分集合は、[3] ということです。これらのことから、6 = 3 + 1 + 2 となることが分かるわけです。
よって、部分和が 6 となる部分集合は [3, 1, 2]です。
なお、例で示した問題では、部分和 9 が求めるターゲットなので、同様に p[9]からたどっていけば、7 + 2 で 9 が求まることが分かります。
これから分かるように、ターゲットである p[target] が -1 から別の値に変化したら、解が求まったことになりますから、処理をここでストップしています。
作成したC#のコード
C#のコードを以下に示します。
using System;
using System.Linq;
namespace SubsetSumProblemApp {
class Program {
// ここは問題の本質じゃないbので手抜き
static void Main(string[] args) {
// 問題の集合と部分和を入力する
Console.Write("集合=> ");
var strs = Console.ReadLine().Split(',');
int[] nums = strs.Select(s => int.Parse(s.Trim())).ToArray();
// 一つの集合に対して、複数のターゲットを調べることができる
while (true) {
Console.Write("ターゲット=> ");
var line = Console.ReadLine();
if (line == "")
break;
int target = int.Parse(line);
// 問題を解く
var ssp = new SubsetSumProblem(nums);
var ans = ssp.Solve(target);
if (ans.Length > 0) {
// 解が見つかったので、解を表示する。
var ansStrings = ans.Select(n => n.ToString()).ToArray();
var text = string.Join(" + ", ansStrings) + " = " + target;
Console.WriteLine(text);
} else {
Console.WriteLine("解は存在しません");
}
}
Console.ReadLine();
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
namespace SubsetSumProblemApp {
// 部分和問題を動的計画法で解く
public class SubsetSumProblem {
private int[] _nums;
// numsの要素は、正整数とする
public SubsetSumProblem(int[] nums) {
this._nums = nums.ToArray();
}
private int[] _work;
public int[] Solve(int target) {
// 0. 配列pを用意する。サイズは、部分和(target)+1 とする。
_work = new int[target + 1];
// 1. 配列_workを初期化する _work[0] = 0, それ以外は -1 をセット。
_work[0] = 0;
for (int i = 1; i <= target; i++)
_work[i] = -1;
// 2. 集合からひとつ要素を取り出し、m とする。
foreach (var m in _nums) {
for (int i = target; i >= 0; i--) {
// 3. 配列pを最後から見ていき、-1 以外の時に、4の処理を行う
if (_work[i] == -1)
continue;
// 4. i + m <= target で、_work[i+m] == -1 ならば、_work[i+m] に m を代入する。
if (i + m <= target && _work[i + m] == -1)
_work[i + m] = m;
}
// 5. _work[target] != -1 ならば、解が見つかったので、処理を終了する。
// _work[target] == -1 ならば 1.に戻って処理を繰り返す。
if (_work[target] != -1)
break;
}
return ToResult(_work, target);
}
// 作業用の配列から、部分集合を求める
private int[] ToResult(int[] work, int target) {
var 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();
}
}
}
実行例
集合=> 3, 7, 8, 12, 13, 18
ターゲット=> 27
7 + 8 + 12 = 27
ターゲット=> 29
3 + 8 + 18 = 29
ターゲット=> 36
3 + 8 + 12 + 13 = 36
ターゲット=> 47
解は存在しません
ターゲット=> 51
8 + 12 + 13 + 18 = 51
ターゲット=>
集合=> 3,6,4,8,1,9,10,12,7,11,20,31
ターゲット=> 71
3 + 6 + 4 + 8 + 1 + 9 + 10 + 12 + 7 + 11 = 71
ターゲット=> 12
4 + 8 = 12
ターゲット=> 100
6 + 4 + 8 + 9 + 10 + 12 + 20 + 31 = 100
ターゲット=> 105
3 + 4 + 8 + 1 + 9 + 10 + 12 + 7 + 20 + 31 = 105
ターゲット=> 19
6 + 4 + 8 + 1 = 19
ターゲット=> 200
解は存在しません
ターゲット=>
この記事は、Gushwell's C# Programming Pageで公開したものをに加筆・修正したものです。