Take a look at these two questions:
- A Set of Water Jug Challenges
- Pouring problem
Now I'm asking for a generalised solution to that problem.
I define the problem as follows:
You are required to measure exactly $n$ litres of water.
You have $j$ jugs.
Each jug has volume $v_m$ where $m$ is the jug-number ($1$ to $j$).
You have an infinitely large tub of water.
There is no indication on the jugs saying how much liquid is in them, and you can't judge it by eye. You do know for sure when they are empty and when they are full.
Question(s):
For what sets of values ($n$, $j$, $v_1$ to $v_j$) is this solvable?
For cases which are solvable, what algorithm can be used to find the solution?
This is intended to be a math/algorithm problem, rather than a lateral thinking problem, so 'creative' solutions such as "I use the infinitely-large tub of water to solve the world's drought problems, am elected world president for my services to humanity, and keep the jugs as a souvenir" may be upvoted if they're witty/entertaining but won't be marked as correct.
NB: Searching the entire possible space of jug-pouring actions is clearly a solution. But it isn't a very interesting or elegant one.
See also:
No comments:
Post a Comment