NP完全問題の1つである部分和問題を腕ずくで解くプログラム

subsum

import std.stdio;
import std.algorithm;
import std.conv;
import std.array;
import std.c.stdlib;

/// 数列の最大要素数
immutable MAX_NUMS = size_t.sizeof * 8;

/**
 * メイン関数
 *
 *  Params:
 *      args = コマンドライン引数。数列と部分和になるか判定する数を指定する。
 */
void main(string[] args) {
    // コマンドライン引数から入力を得る
    auto input = map!(to!int)(args[1 .. $]);
    if(input.length < 2) {
        // 引数少なすぎ
        stderr.writeln("too few arguments.");
        exit(-1);
        return;
    } else if(input.length > MAX_NUMS + 1) {
        // 引数多すぎ
        stderr.writeln("too many arguments.");
        exit(-1);
        return;
    }

    // 数列と判定対象の値に分ける
    immutable nums = array(input[0 .. $ - 1]);
    immutable n = input[$ - 1];
    writefln("nums: %s", nums);
    writefln("n: %s", n);

    // 数列の全組み合わせについて処理する
    foreach(flags; 1 .. (1UL << nums.length)) {
        // フラグの立っている数の合計を出す
        int sum = 0;
        eachFlaggedNumber!(v => sum += v)(flags, nums);

        // 合計値がnであれば答えとして出力する
        if(sum == n) {
            int[] answer;
            eachFlaggedNumber!(v => answer ~= v)(flags, nums);
            writefln("answer: %s", answer);
        }
    }
}

/// 数列のうちフラグの立っている値をfで処理する
void eachFlaggedNumber(alias f)(size_t flags, const(int)[] nums) {
    foreach(i, n; nums) {
        if((flags & (1UL << i)) != 0) {
            f(n);
        }
    }
}

使用方法

コマンドライン引数に数列と判定対象の値を指定する。(最後の数字が判定対象の値)

出力結果

数列がnums、判定対象の値がn、nになる数の組み合わせがanswerとして出力される。
解が複数あればその分answerが出てくる。解なしの場合は出てこない。

# 例：1〜10までで55を求める
./subsum 1 2 3 4 5 6 7 8 9 10 55
nums: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
n: 55
answer: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

#1〜10までで56を求めるが、解なし
./subsum 1 2 3 4 5 6 7 8 9 10 56
nums: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
n: 56

#1〜10までで3を求める。解が2つある
./subsum 1 2 3 4 5 6 7 8 9 10 3 
nums: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
n: 3
answer: [1, 2]
answer: [3]