1

これは、要素に制約がある順序集合の組み合わせをいくつ見つけるかという問題に関するものです。

例として：

a+b+c+d+e=635、これは...

[0-90] + [1-120] + [50-150] + [20-200] + [30-250] = 635

数学スタック交換で回答されたように、1 つのソリューションは複数の合計を使用します。

https://math.stackexchange.com/questions/159197/combinatorics-using-constraints-and-ordered-set

このタイプの問題を解決するための手順または疑似コードの一般的なアイデアを教えてください。

どうもありがとうございました！

4

2 に答える 2

0

ネストされた一連の for ループは、それを行う最も簡単な方法です。

擬似コード:

let combinations = 0;
for a = 0 to 90
    for b = max(a+1, 1) to 120
        for c = max(b+1, 50) to 150
            for d = max(c+1, 20) to 200
                let e = 635 - a - b - c - d;
                if max(d+1, 50) <= e <= 250
                    let combinations = combinations + 1

アップデート

上記は少し最適化できますが、最終的には一般的な解決策ではなく、特定の解決策になります。

これは常に true であることがわかります。そのため、への代入で呼び出し(a+1) >= 1を取り除くことができます。同様に、は常に真であるため、 への代入を単純化できます。 maxb(c+1) >= 20d

の最大可能値が 540 であることもわかりますa + b + c + d。これにより、 の最小可能値は 95 になりeます。これは、記載されている の下限よりも大きいためe、確認する必要がありe >= (d+1)ます。

最終的には次のようになります。

let combinations = 0;
for a = 0 to 90
    for b = a+1 to 120
        for c = max(b+1, 50) to 150
            for d = c+1 to 200
                let e = 635 - a - b - c - d;
                if d+1 <= e <= 250
                    let combinations = combinations + 1
于 2012-06-18T06:20:47.627 に答える
0

数学交換ページに投稿されたソリューションを見てください。各シグマ記号はネストされたforループです。最も内側の項xは として与えられifます。したがって、アルゴリズムは if を囲む 4 つのネストされたループである必要があります。

于 2012-06-18T06:06:21.860 に答える