Dynamic Programming for Matching Size (least difference)

Question

I found this problem which seeks to use dynamic programming to minimize the absolute difference between height for n boys and m girls in a match.

If I understand it correctly we will be sorting the first j boys and k girls by height (ascending? or descending?) where j<=k. Why is j <=k?

I do not understand how I can use the recurrence mentioned in the link:

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

to find the optimal matching for the values (j,k), based on whether you pair up boy j with girl k or not.

I'm clearly misunderstanding some things here but my goal is to write pseudo code for this solution. Here are my steps:

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

Please help me to implement the solution proposed in the link.

Answer 1

As stated in the answer you provided, there is always a better matching available if there is a cross edge between two matchings, when the heights are sorted for all the boys and all the girls in ascending order.

So a Dynamic programming solution with complexity of O(n*m) is possible.

So we have a state represented by 2 indexes, lets call them i and j, where i refers for boys and j refers to the girls, then at each state (i, j) we can make a move to the state (i, j+1), i.e. the current ith boy does not choose the current jth girl or the move can be made to the state (i+1, j+1), i.e. the current jth girl is chosen by the current ith boy and we choose the minimum between these two choices at every level.

This can be easily implemented using a DP solution.

Reccurrence :

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

Below is the code in c++ for recursive DP Solution :

#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 to solution on Ideone : http://ideone.com/K5FZ9x

The DP table output of the above solution :

 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 

The answer is stored in the DP[0][0] state.