algorithm - 匹配大小的动态规划(最小差异)

Question

我找到了 this problem它寻求使用动态规划来最小化一场比赛中 n 名男孩和 m 名女孩的高度绝对差异。

如果我理解正确，我们将按高度(升序？或降序？)对前 j 个男孩和 k 个女孩进行排序，其中 j<=k。为什么j <= k？

我不明白如何使用链接中提到的重复:

(j,k−1) and (j−1,k−1)

根据您是否将男孩 j 与女孩 k 配对，找到值 (j,k) 的最佳匹配。

我显然误解了这里的一些东西，但我的目标是为这个解决方案编写伪代码。这是我的步骤:

1. Sort heights Array[Boys] and Array[Girls]
2. To pair Optimally for the least absolute difference in height, simply pair in order so Array[Pairs][1] = Array[Boys][1] + Array[Girls][1]
3. Return which boy was paired with which girl

请帮助我实现链接中提出的解决方案。

Answer 1

如您提供的答案中所述，当所有男孩和所有女孩的高度按升序排序时，如果两个匹配之间存在交叉边，则总有更好的匹配可用。

因此，复杂度为 O(n*m) 的动态规划解决方案是可能的。

所以我们有一个由 2 个索引表示的状态，我们称它们为 i 和 j，其中 i 表示男孩和 j 指的是女孩，那么在每个状态 (i, j) 我们可以移动到状态 (i, j+1) ，即当前第i个男孩不选择当前第j个个女孩或者移动到状态(i+1, j+1) ，即当前 jth 女孩被当前 ith<​​ 男孩选择，我们在每个级别选择这两个选择中的最小值。

这可以使用 DP 解决方案轻松实现。

重复率:

DP[i][j] = minimum(
                    DP[i+1][j+1] + abs(heightOfBoy[i] - heightofGirl[j]),
                    DP[i][j+1] 
               );

以下是递归 DP 解决方案的 C++ 代码:

#include<bits/stdc++.h>
#define INF 1e9

using namespace std;

int n, m, htB[100] = {10,10,12,13,16}, htG[100] = {6,7,9,10,11,12,17}, dp[100][100];

int solve(int idx1, int idx2){
    if(idx1 == n) return 0;
    if(idx2 == m) return INF;

    if(dp[idx1][idx2] != -1) return dp[idx1][idx2];

    int v1, v2;

    //include current
    v1 = solve(idx1 + 1, idx2 + 1) + abs(htB[idx1] - htG[idx2]);

    //do not include current
    v2 = solve(idx1, idx2 + 1);

    return dp[idx1][idx2] = min(v1, v2);
}


int main(){

    n = 5, m = 7;
    sort(htB, htB+n);sort(htG, htG+m);
    for(int i = 0;i < 100;i++) for(int j = 0;j < 100;j++) dp[i][j] = -1;
    cout << solve(0, 0) << endl;
    return 0;
}

输出:4

Ideone 解决方案链接:http://ideone.com/K5FZ9x

上述方案的DP表输出:

 4        4        4        1000000000      1000000000      1000000000       1000000000       
-1        3        3        3               1000000000      1000000000       1000000000       
-1       -1        3        3               3               1000000000       1000000000       
-1       -1       -1        2               2               2                1000000000       
-1       -1       -1       -1               1               1                1 

答案存储在 DP[0][0] 状态中。