0

特定の合計を構成するリスト内の数値を見つける必要があります。

Sum: 500

Subtotals: 10 490 20 5 5

In the end I need: {10 490, 490 5 5}

この種の問題を何と呼びますか。それを効率的に解決するアルゴリズムはありますか？

4

2 に答える 2

3

これはナップザック問題であり、NP 完全問題です。つまり、既知の効率的なアルゴリズムはありません。

于 2013-07-26T10:16:09.297 に答える
1
  1. これはナップザックの問題ではありません。
  2. 最悪の場合、N 個の小計を使用すると、O(2^N) 個の解が存在する可能性があるため、最悪の場合のアルゴリズムはこれより優れたものにはなりません (したがって、問題は NP クラスにまったく属しません)。

Subtotals 配列に正でない要素がなく、どの要素も Sum よりも大きくないと仮定しましょう。小計の配列を並べ替え、最後に 0 を追加して末尾の合計の配列を作成できます。あなたの例では、次のようになります。

Subtotals:   (490, 20, 10,  5, 5)  
PartialSums: (530, 40, 20, 10, 5, 0)

ここで、任意の「残りの合計」S、位置 i、および「現在のリスト」L に対して、問題 E(S, i, L):
E(0, i, L) = (print L) があります。
E(S, i, L) | (PartialSums[i] < S) = (なし)。
E(S, i, L) = E(S, i+1, L), E(S-Subtotals[i], j, L||Subtotals[i])、j は Subtotals lesser の最初の要素のインデックス(S-Subtotals[i]) または i+1 のいずれか大きい方以上。
問題は E(Sum, 0, {}) です。

もちろん、重複には問題があります (リストに別の 490 番号があった場合、このアルゴリズムは 4 つの解を出力します)。それが必要でない場合は、ペアの配列 (値、多重度) を使用すると役立つ場合があります。

PS問題のサイズが十分に小さい場合は、動的計画法も検討できます。

  1. セット {0} から始めます。サイズが小計の配列と等しいセットの配列を作成します。
  2. 小計ごとに、小計値を追加して、前のセットから新しいセットを作成します。Sum より大きいすべての要素を削除します。それを前のセットとマージします（基本的に、可能なすべての合計のセットになります）。

  3. 最終セットに Sum がない場合、解決策はありません。それ以外の場合は、ソリューションを Sum から 0 にバックトラックし、前のセットに [value] と [value-subtotal] が含まれているかどうかを確認します。
    例：

    (10、490、20、5、5)

セット:

(0)
(0, 10)
(0, 10, 490, 500)
(0, 10, 20, 30, 490, 500) (510, 520 - discarded)
(0, 5, 10, 15, 20, 25, 30, 35, 490, 495, 500)
(0, 5, 10, 15, 20, 25, 30, 35, 40, 490, 495, 500)

前のセットから: [500-5] 前のセット、[495-5] 前のセット、[490-20] 前のセットにない ([490] は)、[490-490] は 0、結果の答え {5 、5、490}。

于 2013-07-27T07:44:56.080 に答える