How to solve the optimal matching problem ?

Правка en3, от AjaySabarish, 2021-04-03 21:11:02

There are M objects of type 1 and N objects of Type 2. Given $$$Cost[i][j]$$$ where $$$i$$$ is an object of Type 1, and $$$j$$$ is an object of Type 2. What is the minimum total cost achievable after every type 1 object is mapped with exactly one type 2 object?

Total cost is defined as the summation of the individual costs incurred due to matching.

$$$M <= N$$$.

Example :

Type 1 : $$$A B$$$

Type 2 : $$$C D$$$

$$$cost[A][C] = 100$$$

$$$cost[A][D] = 10$$$

$$$cost[B][C] = 10$$$

$$$cost[B][D] = 100.$$$

It's optimal to match $$$(A, D)$$$ and $$$(B, C)$$$, the total cost incurred is 20.

I thought of a bit masking + DP approach, but the complexity is exponential, is there a better approach?

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский AjaySabarish 2021-04-03 21:11:02 26
en2 Английский AjaySabarish 2021-04-03 21:08:28 12
en1 Английский AjaySabarish 2021-04-03 21:07:51 682 Initial revision (published)