2

私は2つの配列を持っています：

a1 = [x,y] 
b1 = [a,b,c]

私はそれらの「最適なもの」を見つけようとしています。1つの配列の各アイテムは、2番目の配列のアイテムと一致する可能性があり、アイテムは一致しない可能性があります。配列はソートされており、アイテムは順不同で一致することはできません。あれは：

some valid orderings = [xa, yb, c], [a, x, yb, c], [a, x, b, c, y]  
some invalid orderings = [ya, xb, c], [b, x, a, c, y]

「最適なマッチング」は、コスト関数によって定義されます。これは、各ペアの場合はc（a、b）、各シングルトンの場合はc（a）です。

どうすればこれを行うことができますか？

4

1 に答える 1

2

配列のサイズが n と m だとします。2D 配列 dp[ n ][ m ] を保存します。ここで、dp[ i ][ j ] は、最初の配列の最初の i 要素と 2 番目の配列の j 要素に対する同じ問題の解です。動的計画法を機能させるには、次の式を使用します。

  1. dp[ 0 ][ 0 ] = 0
  2. dp[ i ][ j ] = max( dp[ i - 1 ][ j - 1 ] + c( a[ i ], b[ j ] ), // a[ i ] と b[ j ]
                              dpのペアを作成[ i - 1 ][ j ] + c( a[ i ] ), // a[ i ] をシングルトーンとして取得
                              dp[ i ][ j - 1 ] + c( b[ j ] ), // b[ を取得j ] シングルトーンとして
                              dp[ i - 1 ][ j - 1 ] + c( a[ i ] ) + c( b[ j ] ) // a[ i ] と b[ j ] の両方をシングルトーンとして取る
  3. dp[ n-1 ][ m-1 ] が答えです

ステップ 2 で、i = 0 の場合は dp[ i ][ j - 1 ] + c( b[ j ] ) のみを使用し、j = 0 の場合は dp[ i - 1 ][ j ] + c( a[ i ] ) を使用します。 .

于 2013-02-13T19:25:21.190 に答える