If I have 2 arrays of frames, namely, A and B. Each element of an array represents a frame.
and a function calc_sim(frame_i, frame_j) that measures the similarity between two frames.
frame_i and frame_j are matched if their similarity is above 50%.
How can one measure the maximum number of matched pairs between the arrays A and B (of course knowing that if an element is already in a pair, it can’t be used again)?
A greedy solution won’t work here because choosing a frame may affect badly other frames, and the only optimal solution I can think of is trying all the possibilities which is O(n!).
Is there a better solution or is it an NP problem?
Thanks in advance.