### farmersrice's blog

By farmersrice, history, 16 months ago,

You have $N$ cups, each containing some amount of water. Each cup is identical and has maximum capacity $M$ milliliters. In one operation, you may select any two cups $a$ and $b$, which represents pouring water from cup $a$ to cup $b$. If the sum of the cups' volume is less than or equal to $M$, cup $a$ ends up empty and cup $b$ contains all the volume of the cups. If the sum of the cups' volume is greater than $M$, then cup $b$ ends up filled to capacity $M$ and cup $a$ contains the remainder of the water. Suppose the total volume of water in all cups is $V$. The question is: What is the minimum number of operations necessary to create $\left \lfloor{\frac{V}{M}}\right \rfloor$ cups of water that are filled to maximum capacity?

No constraints, the problem is original and comes from a real life scenario. My hypothesis is that as long as you merge small to large then it will take the same number of operations, which is also optimal — but I can't think of how to prove this. Any ideas?

• +11

 » 16 months ago, # |   +10 Let us have $N$ nonempty cups with the total volume $V = 2M$. In this case the minimal possible answer is $N - 2$. To achieve this score we have to split the set of cups into two subsets, each with the total volume $M$. In any other case the answer would be $N - 1$. So we have to solve a knapsack problem.
•  » » 16 months ago, # ^ |   0 So the total complexity is $NM$? How do we do the general case?
•  » » » 16 months ago, # ^ |   +23 Let's just replace $2$ by $K$. We will get $V = KM$, and to achieve the answer $N - K$ we have to split the set of cups into $K$ subsets, each having total volume $M$. And this is exactly a bin packing problem. And what I'm trying to say: I think that problem that you described don't have a polynomial solution.