Storing water in buckets smartly - algorithm suggestions?

Question

I encountered this problem at work. I am reframing the problem (from its original context) so that it is easier to comprehend.

You have a few buckets with water-bearing capacities. You have water jugs that can only be emptied into certain buckets. The jar can partially be emptied into multiple "allowed" buckets.

You have to find out whether given the jug and bucket configuration, all the jug water can be transferred to the legal buckets without overflow.

Example:

Say you have bucket A, B & C. They have capacities 300, 400 and 500 units respectively.

Now you have 3 jugs J1, J2 & J3. They have 300, 500 & 200 units of water respectively.

1. J1 can be emptied into A & B
2. J2 can be emptied into A, B & C
3. J3 can be emptied into C

Note that this configuration can be solved. One possible solution configuration could look like this:

1. A - J1 completely emptied here - can't fill this bucket any more
2. B - J2 completely emptied here - can't fill this bucket any more
3. C - 100 units from J2 and 200 units from J3 leave this bucket with the ability to fill 500 - (100 + 200) = 200 units more

What is the best way to solve this? I suspect this might be a known algorithm. A little googling got me nowhere.

The tentative solution I have right now involves moving water between buckets (backtracking) when I need to pour water into a specific bucket(s). Note that I haven't fully flushed it out yet.

Answer 1

This can be treated as a max flow problem.

Create a source node, a sink node and nodes for each jug and each bucket, and add an edge from the source to each jug with capacity equal to the amount of water in that jug. Add edges with infinite capacity between allowed jug/bucket pairs and add an edge from each bucket to the sink node with capacity equal to the capacity of the bucket.

Now find the max flow. If it's equal to the total amount of water then you have a solution.