算法 - 通过盒子分发项目

Question

我正在开展个人项目并遇到了障碍。我不会完全按照原样来指定问题，因为这很难解释，相反，我会提出一个类似的问题，我相信可以像我的实际问题一样解决问题。想象一下：你有3件物品（A，B和C），这些物品只能放在特定的盒子里（1,2或3）。每个项目可以放置在0个或更多的框内。例如，设想的是，项目可以放置在这些框：

• 项A可以放置在箱1或2
• 项B只能被放置在盒2
• 项C只能放置在框3中。

这个想法是找出是否存在一个解决方案（不是解决方案本身），其中所有项目可以放在一个盒子里，而一个盒子只能放1个项目。例如，以上示例的可能解决方案可以是项目A - >框1，项目B - >框2，项目C - >框3.

这个想法是解决这个问题的任何N个项目和任何M个盒子。我一直在努力解决这个问题，但除了明显的暴力解决方案之外，我一直在努力。

任何指针在正确的方向？ :)

在此先感谢。

Answer 1

您有一个包含项目和框的二部图作为两组顶点，以及所有允许的展示位置的边。

您的问题被称为“最大二分配匹配”，并且已经过充分研究。 Hopcroft-Karp算法运行于O（E * sqrt（V））时间，例如：https://en.wikipedia.org/wiki/Hopcroft%E2%80%93Karp_algorithm

如果您将单个“源”顶点连接到每个项目顶点，并将每个顶点连接到单个“接收器“顶点，那么你的问题就成为最大流量问题，这个问题也得到了充分研究，并且经常用福特富尔克森算法解决：https://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm