farmersrice's blog

By farmersrice, history, 16 months ago, In English

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?

 
 
 
 
  • Vote: I like it
  • +11
  • Vote: I do not like it

»
16 months ago, # |
  Vote: I like it +10 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    So the total complexity is $$$NM$$$? How do we do the general case?

    • »
      »
      »
      16 months ago, # ^ |
        Vote: I like it +23 Vote: I do not like it

      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.