CODEWITHSUNDEEP
algorithmdata-structures
hsf
hsf

Reputation: 88

Algorithms - Distributing items through boxes

I am working on a personal project and hit a roadblock. I will not specify the problem exactly as is, because it would be hard to explain, instead I'll present a similar problem that I believe can be solved the same way as my actual problem.

Imagine this: you have 3 items (A, B, and C), and these items can only fit in certain boxes (1, 2, or 3). Each item can be placed inside 0 or more of the boxes. For example, imagine that the items could placed in these boxes:

The idea is to figure out if a solution exists (not the solution itself) where all items can be placed in a box, and a box can only hold 1 item. For example, a possible solution for the above example could be Item A -> Box 1, Item B -> Box 2, Item C -> Box 3.

The idea is to solve this for any N number of items and any M number of boxes. I've been trying to solve this throughout the night but, aside from the obvious bruteforce solution I've been struggling a bit.

Any pointers in the right direction? :)

Thanks in advance.

Upvotes: 0

Views: 89

Answers (1)

Matt Timmermans
Matt Timmermans

Reputation: 59263

You have a bipartite graph with items and boxes as the two sets of vertices, and edges for all the allowed placements.

Your problem is called "maximum bipartite matching", and is well-studied. The Hopcroft-Karp algorithm runs in O(E*sqrt(V)) time, for example: https://en.wikipedia.org/wiki/Hopcroft%E2%80%93Karp_algorithm

If you connect a single "source" vertex to every item vertex, and connect every box vertex to a single "sink" vertex, then your problem becomes a maximum flow problem, which is also well-studied and often solved with the Ford Fulkerson algorithm: https://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm

Upvotes: 4

Related Questions