-2

リンクリストを合計が等しい2つのサブリストに分割しようとしています。これらのサブリストは、連続した要素で構成される必要はありません。

私はリンクされたリストを持っています

Eg.1
LinkedList={1,7,5,5,4}
should be divided into
LinkedList1={1,5,5}
LinkedList2={7,4}

どちらも要素の合計は 11 と同じです。

Eg.2
LinkedList={42,2,3,2,2,2,5,20,2,20}
This should be divided into two list of equal sum i.e 50.
LinkedList1={42,3,5}
LinkedList2={2,2,2,2,20,2,20}

誰かがこの問題を解決するための疑似コードを提供できますか?

これは私がこれまで考えてきたことです：

  1. 連結リストの要素を合計し、2 で割ります。

  2. ここで、linkedlist1 の合計が linkedlist/2 の合計より小さくなるまで、要素を linkedlist1 にプッシュし続けます。

  3. 等しくなく、linkedlist sum/2 より小さい場合は、次の要素に移動し、現在の要素を linkedlist2 にプッシュできます。

ただし、これは要素が特定の順序である場合にのみ機能します。

4

1 に答える 1

1

これはパーティションの問題として知られています。

この問題を解決するにはいくつかの方法がありますが、最も一般的な 2 つだけを以下に挙げます (いずれかの方法またはその他の方法の詳細については、ウィキペディアを参照してください)。

これは、動的プログラミングのアプローチで解決できます。これは、基本的に、要素と値ごとに、その要素を含めるか除外し、対応する値に合計されるサブセットがあるかどうかを調べることになります。より具体的には、次の再帰関係があります。

p(i, j)ifはtoとそうでない場合の合計Trueのサブセットです。{ x1, ..., xj }iFalse

p(i, j)Trueいずれかp(i, j − 1)がそうである場合、Trueまたはそうでない場合p(i − xj, j − 1)True
p(i, j)False

次にp(N/2, n)、サブセットが存在するかどうかを示します。

実行時間はO(Nn)、nが入力セット内の要素の数であり、 が入力セットN内の要素の合計です。

「おおよその」貪欲なアプローチ (必ずしも等しい合計パーティションを見つけるとは限りません) は非常に簡単です。セット内の各要素を最小の合計で配置するだけです。疑似コードは次のとおりです。

INPUT:  A list of integers S
OUTPUT: An attempt at a partition of  S into two sets of equal sum
1  function find_partition( S ):
2     A ← {}
3     B ← {}
4     sort  S in descending order
5     for i in S:
6        if sum(A) <= sum(B)
7           add element i to set A
8        else
9           add element i to set B
10    return {A, B}

実行時間はO(n log n)です。

于 2014-05-05T15:58:55.463 に答える