【C#】部分和問題(subset-sum problem)を解いてみる

はじめに

今回は部分和問題(subset-sum problem)を解いてみたいと思います。

最初にネタバレをしてしまいますが、具体的にはbit全探索を用いた方法と動的計画法を用いた2種類を紹介していきます。

アルゴリズムの教科書なんかでもよく出てくる問題なので、マスターしてみるのも面白いかもしれません。

早速みていきましょう。

問題

入力：n個の正の整数 $a_1, a_2, ... , a_n$ ，正の整数b
出力： $a_1, a_2, ... , a_n$ のいくつかを足し合わせてbができればYES，なければNO

具体例１
入力：a = {1, 2, 3, 4}，b = 5
出力：YES (2+3とか1+4とか)

具体例２
入力：a = {1, 2, 3, 4}，b = 11
出力：NO

解答例１

まずはbit全探索という手法を使って解いてみたいと思います。
www.hanachiru-blog.com

bit全探索について以前記事を書いたのでそちらを参照してみてください。

/// <summary>
/// 部分和問題
/// </summary>
/// <param name="items">コレクション</param>
/// <param name="target">一致する値</param>
/// <returns>いくつかの要素を足し合わせてtargetを作れるか</returns>
public static bool SubsetSum(IEnumerable<int> items, long target)
{
    var nums = items.ToArray();

    foreach (var item in BitFullSearch(nums.Length))
    {
        long sum = 0;

        // 選んだ整数のみ足し合わせる
        for (int i = 0; i < nums.Length; i++)
        {
            if (item[i]) sum += nums[i];
        }

        if (sum == target) return true;
    }

    return false;
}

/// <summary>
/// bit全探索
/// </summary>
public static IEnumerable<bool[]> BitFullSearch(int n)
{
    if (n <= 0)
    {
        yield return new bool[] { };
        yield break;
    }

    for (int i = 0; i < Math.Pow(2, n); i++)
    {
        var array = new bool[n];
        for (int j = 0; j < n; j++)
        {
            var targetBit = (i >> j) & 1;
            if (targetBit == 1) array[j] = true;
        }

        yield return array;
    }
}

最初に挙げた例を用いてテストをしてみましょう。

static void Main(string[] args)
{
    var a = new int[] { 1, 2, 3, 4 };
    var b = 5;

    Console.WriteLine(SubsetSum(a, b));     // True

    b = 11;

    Console.WriteLine(SubsetSum(a, b));     // False
}

解答例１の考察

アルゴリズムの性能をみるための指標として計算量をみてみましょう。

bit全探索は $o(2^n)$ で動作することが知られています。またそのループ(foreach)の中で要素が含まれているかを線形に探索している(nの配列の数調べる)ので， $o(n)$ かかります。

これらを加味すると，全体の最悪計算量は $o(n2^n)$ だと導けます。

これは比較的重めのアルゴリズムだと考えられ，nの個数が40個ぐらいだと数日間ぐらいかかってしまってもおかしくはないのでしょう。

解答例２

次に動的計画法を使って解いていきたいと思います。

また動的計画法の詳細はこちらがとてもわかりやすく解説されているので参照してみてください。
典型的な DP (動的計画法) のパターンを整理 Part 1 ～ナップサック DP 編～ - Qiita

public class SubsetSum
{
    private int[] _items;

    public SubsetSum(IEnumerable<int> items)
    {
        _items = items.ToArray();
    }

    public bool Solve(int target)
    {
        var n = _items.Length;

        bool[][] dp = new bool[n + 1].Select(t => new bool[target + 1]).ToArray();

        // dp初期化
        dp[0][0] = true;

        // dpループ
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j <= target; j++)
            {
                dp[i + 1][j] = dp[i][j];
                if (j >= _items[i]) dp[i + 1][j] = dp[i][j - _items[i]];
            }
        }

        return dp.Last().Last();
    }
}

中身的には解答例1より難しいですかね。

これも簡単なテストをしてみるとこんな感じ。

static void Main(string[] args)
{
    var a = new int[] { 1, 2, 3, 4 };
    var b = 5;

    var ssum = new SubsetSum(a);

    Console.WriteLine(ssum.Solve(b));       // True

    b = 11;

    Console.WriteLine(ssum.Solve(b));       // False
}