1

Say I have N cup of waters, each cup with different volume 100ml, 250ml, 355ml, etc. and I have M bottles, each has unlimited volume.

I want to pour all water into the M bottles, and try to balance the water amount poured into different bottles. e.g. I have three cups cup_1 (volume 100ml), cup_2 (volume 100ml), cup_3 (volume 200ml), and I have 2 bottles. The ending result should be:

cup_1 -> bottle_1, cup_2 -> bottle_1, cup_3 -> bottle_2

or

cup_1 -> bottle_2, cup_2 -> bottle_2, cup_3 -> bottle_1

In either case, both bottles will end up with 200ml water, which is the best outcome.

What's the algorithm looks like? The brute force solution is to enumerate all possible combinations, but the time complexity is high. Is there a better way?

biqarboy
  • 852
  • 6
  • 15
budlover
  • 83
  • 7
  • Since all bottles have infinite capacity, would LCM of the cups work? – Phenomenal One Feb 19 '21 at 03:14
  • You have to be precise here. This can be interpreted with a number of different objective functions. What /exactly/ does "as close as possible" mean - what are you trying to minimize? (ie. when doing "brute force" how do you know which answer is best?) – BadZen Feb 19 '21 at 03:22
  • Hi, I mean try to pour similar amount of water into all bottles. e.g. the thing I try to minimize is, DIFF(most_water_amount_pour_to_a_bottle, least_water_amount_pour_to_a_bottle). – budlover Feb 19 '21 at 04:28
  • @budlover. you can try to put the average amount of water in all bottles = (sum of all water)/(number of bottles). And in each bottle try to pour a minimum number of cups and the volume should be close to the average. (greedy approach). – sonus21 Feb 19 '21 at 04:35
  • 2
    https://en.wikipedia.org/wiki/Multiway_number_partitioning – user3386109 Feb 19 '21 at 04:37
  • 1
    This is a harder version of [this](https://stackoverflow.com/questions/6597180/how-to-divide-a-set-into-two-subsets-such-that-difference-between-the-sum-of-num) problem and I believe there is no exact algorithm for this one. You should consider trying some approximation algorithm described [here](https://en.wikipedia.org/wiki/Multiway_number_partitioning). – biqarboy Feb 19 '21 at 05:37
  • You are missing something very important in your description of a problem. What is wrong with `cup1 -> bottle1`, `cup1 -> bottle2`, `cup1 -> bottle3`? (or, exaggerating, all bottles are originally empty, so leave them that way!). – user58697 Feb 19 '21 at 06:47
  • Thanks guys. Will this work? Sort N cup. Starts from the cup with MAX volume. Pour it into the bottle that has LEAST water so far. Repeat this. It works for my example (100ml, 100ml, 200ml, 2 bottles): 200ml -> bottle_1 100ml -> bottle_2 100ml -> bottle_2 Is there a case that it can fail? – budlover Feb 19 '21 at 18:33
  • An example where it fails is 4,3,3,2,2 with 2 bottles. The greedy algorithm puts 4 into the first bottle, then 3 and 3 into the second bottle, then 2 into the first. Now both bottles have 6 and there's one cup left over with 2. The correct solution is 7 in both bottles 4+3 and 3+2+2 – user3386109 Feb 19 '21 at 19:56

0 Answers0