0

それぞれが 0 個以上のポイントを含む一連のノードがあります。ノード間には重複するポイントがありますが、各ノードにはそのノードに固有のポイントが含まれる場合があります。

例えば：

  • ノード A
    • ポイント1
    • ポイント2
    • ポイント3
  • ノード B
  • ノード C
    • ポイント1
    • ポイント4
  • ノード D
    • ポイント2

等

特定の制限まで、最大数のポイントを含むノードの最小数を見つけるアルゴリズムまたは方法はありますか?

上記の例では、4 つの一意のポイントが必要な場合、ノード A とノード C、またはノード A とノード D を取得します。

現在、ノードのリストをポイントの数で降順​​に並べ替え (ノード A、ノード C、ノード D)、ポイントを持たないノード (ノード B) を破棄することで、この問題を解決しています。次に、一意のポイントの定義されたしきい値に達するまで、そのノードのリストを反復処理し、一意のポイントをカウントします (そして、どのノードが参照されているかを記録します)。したがって、上記の例では、結果はノード A とノード C になります。

価値のあることとして、私はこれをJavascriptで行っていますが、私の質問は「問題を解決する方法」であり、特定の言語とは関係がないと思います. 投稿先が間違っていたらすみません。

4

2 に答える 2

0

考えられるすべての組み合わせを構築して値を合計し、ターゲット値をフィルタリングして、結果セットを必要な制約に並べ替えることができます。

結果として上の項目を取ります。

var array = [3, 0, 2, 1],
    i,
    result = [],
    values,
    sum;

// filter zero values
array = array.filter(function (a) {
    return a;
});

// generate all possible combination and build sum
for (i = 0; i < 1 << array.length; i++) {
    sum = 0;
    values = array.filter(function (a, j) {
        if (i & (1 << j)) {
            sum += a;
            return true;
        }
    });
    // add only relevant items to the result set
    sum >= 4 && result.push({ values: values, sum: sum });
}

// sort by priority
result.sort(function (a, b) {
    return a.values.length - b.values.length || a.sum - b.sum;
});

console.log(result);
.as-console-wrapper { max-height: 100% !important; top: 0; }

于 2016-10-12T17:09:18.440 に答える