2

我有两个数组，例如：

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

我正在尝试找到它们的“最佳匹配”。一个数组中的每个项目都可以匹配第二个数组中的一个项目，并且项目可以不匹配。数组已排序，项目不能乱序匹配。那是：

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。存储一个二维数组 dp[ n ][ m ]，其中 dp[ i ][ j ] 是第一个数组的前 i 个元素和第二个数组的 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 回答