0

重複の可能性:
リスト内の合計が特定の数になる数を見つけるアルゴリズム

質問：

[1,2,3,4,6,8,10,12] というリストがあります。これらの数値を合計して新しい数値 16 を計算したいと考えています。

ルール:

1) すべての数字を使用する必要はありません。6 + 10 で問題ありません。

2) 数値は複数回使用できます。12+2+1+1 は問題ありません。

3) 順序の問題、12 + 6 と 6 + 12 は 2 つの異なる組み合わせです。

すべての組み合わせの数値のリストを合計するアルゴリズムを見ましたが、これは同じではありません。

アルゴリズムについてあまり知りません。これが特定のアルゴリズムに適合する場合は、私に知らせてください。または、いくつかの python コード / 疑似コードをいただければ幸いです。

4

1 に答える 1

4

まず、目的の数に合計されるサブセットがあるかどうかを見つけることでさえ、NP完全であり、サブセット合計問題として知られているため、そのための既知の多項式解はないことに注意してください。

さて、特定の問題に関して、ここにいくつかのオプションがあります：

まず、もちろん「すべてのサブセットを生成して合計をチェックする」方法があります。要素がすべて非負である場合、実際にそれらを開発する前に、分枝限定法を使用して可能性の大部分を終了できることに注意してください（でサブセットXを見つけsum(X) == s、数を探している場合n < s-あなたは確信することができますを含むセットXは解決策を見つけられません）。次のようなもの：

findSubsets(list,sol,n):
  if (list.empty() and n == 0): #found a feasible subset!
     print sol 
     return
  else if (n < 0): #bounding non feasible solutions
     return 
  else if (list.empty()): #a solution that sums to a smaller number then n
     return
  e <- list.removeAndReturnFirst()
  sol <- sol.add(e)
  findSubsets(list,sol,n-e)
  sol <- sol.removeLast()
  findSubsets(list,sol,n)
  list.addFirst(e) #cleanup, return the list to original state

はアイテムのリストであり、findSubsets(list,[],n)は目的の番号であり、は空のリストです。を使用して呼び出します。listn[]

必要に応じて簡単に並列化できることに注意してください。調査した2つのサブセット間で実際の同期は必要ありません。

リストに整数のみが含まれている場合のもう1つの方法は、動的計画法を使用してサブセット和問題を解くことです。マトリックスができたら、テーブルに戻ってテーブルからすべての要素を再作成できます。この同様の質問では、ナップザックDPソリューションからリストを取得する方法について説明しています。2つの問題の原則はほとんど同じです。

于 2012-12-05T07:53:13.873 に答える