-2

次の問題のアルゴリズムを Javascript で書きたいと思います。

次の配列 [1,2,3,4,6] が与えられた場合、配列内の他の要素と等しいサブセットの数を指定します。

例えば：

1+2 = 3
1+3 = 4
2+4 = 6
1+2+3 = 6

答え: 4 つのサブセット

配列内の他の要素と等しい数のペアの合計を計算できます。ただし、配列内の他の要素と等しい 2 つ以上の要素 (1+2+3) の合計を見つけることができません。

このためのアルゴリズムをどのように記述しますか? ありがとう！

4

1 に答える 1

1

これは、把握しやすいはずの非常に単純なソリューションです。これは非常に高速なアルゴリズムではありませんが、短い配列の場合はうまく機能することに注意してください。

アイデアは、すべての組み合わせに対してビット マスクを生成し、各マスクに対して、ビット マスク文字列の 1 で示される配列に数値を追加することです。

console.log("Number of subsets: " + getNumberOfSubsets([1, 2, 3, 4, 6], 2));

function getNumberOfSubsets(numbers, minimumNumbersInSubset) {
    var numberOfBits = Math.pow(2, numbers.length);
    var numOfSubsets = 0;

    for (var i=0;i<numberOfBits;i++) {
        var bitField = i.toString(2);
        while(bitField.length < numbers.length) {
            bitField = "0" + bitField;
        }

        var sum = 0;
        var addedNumbers = [];
        for (j=0;j<bitField.length;j++) {
            if (bitField.charAt(j) == "1") {
                sum += numbers[j];
                addedNumbers.push(numbers[j]);
            }
        }

        if (addedNumbers.length >= minimumNumbersInSubset && numbers.indexOf(sum) !== -1) {
            numOfSubsets += 1;
            console.log("Iteration " + i + ": " +
                        bitField+", " + (addedNumbers.join("+") + "=" + sum));
        }
    }

    return numOfSubsets;
}

コンソールに次のように出力して、成功した組み合わせを示します。

Iteration 10: 01010, 2+4=6
Iteration 20: 10100, 1+3=4
Iteration 24: 11000, 1+2=3
Iteration 28: 11100, 1+2+3=6
Number of subsets: 4

ここに jsfiddle があります: http://jsfiddle.net/9HhSs/

于 2013-09-16T21:06:58.640 に答える