匹配大小的动态规划（最小差异）

Question

我发现 this problem 试图使用动态规划来最小化比赛中 n 名男孩和 m 名女孩的身高绝对差异。

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

我不明白如何使用 link 中提到的循环：

(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

请帮助我实施 link 中提出的解决方案。

Answer 1

你可以把这个问题变成一个二分图，其中女孩和男孩之间的边是他们身高之间的绝对差异，就像这样 abs(hG - hB)。然后您可以使用二分匹配算法来求解最小匹配。有关更多信息，请参阅此处 http://www.geeksforgeeks.org/maximum-bipartite-matching/

Answer 2

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

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

所以我们有一个由 2 个索引表示的状态，我们称它们为 i 和 j，其中 i 表示男孩，j 表示女孩，然后在每个状态 (i, j) 我们可以移动到状态 (i, j+1)，即当前 ith 男孩不选择当前 jth 女孩或者可以移动到状态 (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;
}

Output : 4

Link 到 Ideone 上的解决方案：http://ideone.com/K5FZ9x

上述解决方案的 DP table 输出：

 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] 状态。

匹配大小的动态规划（最小差异）

Dynamic Programming for Matching Size (least difference)

algorithm

recurrence

pseudocode

dynamic-programming