Hello,

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.