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?
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.
So the total complexity is $$$NM$$$? How do we do the general case?
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.