假设我有两个集合：（n_1，n2，…）和（m_1，m_2，…）以及一个匹配函数match（n，m），它返回从0到1的值。我想找到两个集合之间的映射，以便满足以下约束：
- 每个元素在相反的集合中最多必须有一个匹配的元素
- 不匹配的元素将与虚拟元素配对，成本为1
- 当应用于所有元素时，匹配函数的和是最大的
- 我在正式表达这一点时遇到了困难，但如果你按照它们的原始顺序将每个集合平行排列，并在匹配的元素之间画一条线，那么这些线都不会交叉。E.x.[n_1<->m_2，n2<-->m_3]是有效映射，但[n_1&llt；->m_ 2，n2<->m-1]不是
（我相信前三个是标准的加权二分匹配约束，但我指定了它们，以防我误解了加权二分匹配对）
这对于指数时间（相对于集合的大小）中的穷举搜索来说是相对直接的，但我希望存在多项式时间（理想情况下为O（（|n|*|m|）^3）或更好）的解。
我已经搜索了大量关于"分配问题"/"加权二分匹配"的内容，并看到了具有不同约束的变体，但没有找到匹配的变体，也没有找到添加了排序约束的变体。你对我该如何解决这个问题有什么想法吗？或者也许是一个粗略的证明，它在多项式时间内是不可解的（就我的目的而言，还原为NP完全也可行）？
这个问题已经在"最大权重不交叉匹配"的名称下进行了研究。有一个简单的二次时间动态程序。设M（a，b）是n1，…，na和M1，..，Mb上的最优匹配的值。我们有复发
M（0，b）=-b
M（a，0）=-a
M（a，b）=最大{M（a-1，b-1）+匹配（a，b），M（a-1，b）-1，M（a、b-1）-1}。
通过追溯argmaxes，您可以从其值中恢复最佳解决方案。
如果匹配的条目数量明显少于大于-1的二次方，则有一种算法在有用条目数量上以时间线性的方式运行（Khoo和Cong，用于MCM设计的快速多层通用区域路由器）。