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.
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.
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments