0

この問題にはアルゴリズムが必要です:

n個の自然数x1、x2、...、xn、数S、およびkのセットが与えられます。合計 S を使用して、セットから選択された k 個の数値の合計 (数値は何度も選択できます) を形成します。

別の言い方をすると: S の可能なすべての組み合わせと境界をリストします: n<=256、x<=1000、k<=32

例えば

  problem instance: {1,2,5,9,11,12,14,15}, S=30, k=3
  There are 4 possible combinations
  S=1+14+15, 2+14+14, 5+11+15, 9+9+12.

これらの境界では、ブルートフォースを使用することはできませんが、動的計画法は良いアプローチだと思います。

スキームは次のとおりです。 テーブル t、t[m,v] = m 個の数によって形成される和 v の組み合わせの数。 

1. Initialize t[1,x(i)], for every i.   
2. Then use formula t[m,v]=Sum(t[m-1,v-x(i)], every i satisfied v-x(i)>0), 2<=m<=k.   
3. After obtaining t[k,S], I can trace back to find all the combinations.

ジレンマは、16=15+1 と 1+15 により t[2,16]=2 のように、t[m,v] が重複した交換可能な組み合わせによって増加する可能性があることです。さらに、1+14+15、1+15+14、...、2+14+14、14+2+14、...のため、最終結果 f[3,30] は大きくなります。

対称順列を取り除くには? 前もって感謝します。

4

1 に答える 1

2

xの要素を選択する方法に順序を課すことにより、順列を取り除くことができます。テーブルをトリプル=からの数によって形成されるt[m, v, n]合計の組み合わせの数にします。ここで観察します。これは、xでの出現とは逆の順序で被加数を生成するだけで、順列の問題を解決します。したがって、たとえば、15 + 14+1と14+14 + 2は生成されますが、14 + 15+1は生成されません。vmx1..xnt[m, v, n] = t[m, v, n-1] + t[m-1, v-x_n, n]

（おそらく、テーブル全体に入力する必要はないので、おそらく怠惰に計算する必要があります。実際、メモ化された再帰関数は、おそらくここで必要なものです。）

于 2012-10-31T04:03:17.313 に答える