算法 - 通過盒子分發項目

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