The problem is as follows.
Minimize the sum of absolute differences between a matching of $n$ values from two sets, $A=\{a_1,a_2,\cdots, a_n\}$ and the set $B=\{b_1, b_2,\cdots, b_m \}$, with $n\leq m$.
So, we can use two list of indexes $\ I$, $J$, such that $I\subseteq [n]$, $J\subset [m]$, and $|I|=|J|=n$. The notation is $[m] = \{1,2,3,\cdots, m\}$.
Therefore, our goal reduces to:
$$ \min_{k=1,2,\cdots, n} \{|a_{i_k} - b_{j_k}|\ : i_k\in [n],\ j_k\in J\}.$$
I found the problem above in this question (in other words) and trying to understand how the answer provided there, it attempts to solve the problem with dynamic programming.
This is what I understand:
- I believe we are building two indexes and are pairing them.
- We first sort boys by height
- Somehow we then construct a match, but it's not greedy, is it? it utilizes calculating the sum of the absolute difference in height. How was the pairing constructed?
This paragraph is key and I would love to understand it but I don't get it:
you can use dynamic programming to find the optimal matching by building up
optimal matchings that have the first j boys in sorted height order all
paired up somehow among the first k girls in sorted height order (where
j≤k), and using the optimal matchings for the values (j,k−1) and (j−1,k−1)to
decide the optimal matching for the values (j,k), based on whether you pair
up boy j with girl k or not.
So, the question is how the dynamic programing method is working here based on the answer given and pseudo code of the solution it would be helpful.