(There’s no need to write the algorithm, I just need help with the greedy choice).

Problem: you are given bottles numbered 1 to n. Each bottle i has a capacity of Ci and currently contains Li. We want to poor water between the bottles so that as many bottles as possible will be filled (Li = Ci) but doing so while moving a minimal amount of water. Write a greedy algorithm that will print instructions on how to do so (poor x liters from bottle i into bottle j). Prove correctness of your algorithm, and give its time complexity.

I’m having trouble solving this problem. We need to write a greedy algorithm, and so the solution is of the type: “take bottle with certain property x and poor as much as you can (until it’s empty or until the other bottle is full) into bottle with certain property y”. But putting in all of the simple properties don’t seem to work and can be refuted with a counter example. Any ideas?


Here is the "greedy" idea.

Suppose you need to choose one bottle to fill completely with minimal amount of water. Which bottle will you choose?

Once you have chosen one bottle and fill it completely with water, the situation you are in now is just as before but one bottle less. You can apply the "greedy" choice again. And so on.

  • 2
    $\begingroup$ choosing the bottle with least left remaining water does not always give the optimal solution. For example, say you have three given bottles written in the form (Ci,Li): (1000,900), (500,200) ,(400,100). than the optimal solution is to take the bottle with 900 and poor it into the others. $\endgroup$ – user92484 Jan 5 '19 at 20:53
  • $\begingroup$ My hint, in fact, could stand. "Minimal amount of water" can mean "minimal amount of water including the existing water in the bottle". If we interpret it as "minimal amount of water in addition to the existing water in the bottle", it may be a bad idea since, as you indicated, we could have bottles of the form (7, 5), (4, 2), (3,0). $\endgroup$ – John L. Jan 6 '19 at 2:04
  • $\begingroup$ However, even if interpreted usefully, this hint is not enough to guide the second requirement, as many bottles as possible will be filled (Li = Ci) but doing so while moving a minimal amount of water. $\endgroup$ – John L. Jan 6 '19 at 2:14
  • $\begingroup$ Is the second requirement NP-complete? I am checking ... $\endgroup$ – John L. Jan 6 '19 at 2:16

Assume you have 100 empty one litre bottles and 50 filled two litre bottles. So what is your optimal solution, having 50 filled bottles by doing nothing or having 100 filled bottles by pouring 100 litres into the empty bottles? I assume the latter.

You have a fixed amount of water. To have as many filled bottles as possible, you sort the bottles by capacity and find the largest n such that the n smallest bottles can be filled. There may be some water left, but not enough to fill bottle #n+1.

Now comes the hard part: You may have many choices to pick the filled bottles. Say you have bottles filled with 100.999 litres total, and the smallest 200 bottles have a capacity of 1 litre to 1.010 litres total, other bottles are 2 litres or more. You may have a huge number of choices which 100 bottles to fill. I think this is equivalent to the knapsack problem, therefore NP-complete.

  • $\begingroup$ yes, you must fill the maximal number of bottles but while doing so move the minimal amount of water. In your example, are all the small bottles empty? $\endgroup$ – user92484 Jan 5 '19 at 21:22
  • $\begingroup$ In my example they all have a bit of water in them. So you have 200 bottles with some water in them. You’d try to fill the bottles with lots of water in them, but you can’t fill all the bigger bottles because you don’t have enough water to fill 100 large bottles. In many practical cases you may get an optimal solution easily, but if I balance the sizes and what’s in the bottles just right, I can make it really hard. $\endgroup$ – gnasher729 Jan 6 '19 at 12:50

The answer builds off of gnasher's answer. (The problem as a whole is not NP-complete, though.)

You have a starting configuration of water, and and at the end you're going to fill as many bottles as you can, and they will all be the smallest bottles. There might be some water left in other larger bottles, but that's okay as long as none of it's enough to fill a whole nother bottle.

So, there are sort of two goals: -Fill water into small bottles (most in need of filling) -Empty the large bottles first (least in need of filling).

So if you take your largest bottle with water, then it's definitely not going to be full in the final state, so you can use it to start filling other bottles. Pour from it into the smallest, second smallest, etc. until it's empty. Then go with the second largest bottle. And so on.

This is greedy in that you're not planning, just moving immediately the most useless part to the most useful.

It's correct because, for all the water that you pour, you would have needed to fill at least that much anyway: you need to have that small bottle full in the final solution anyway, so you're not wasting anything.

Of course you do have to stop early enough! If you don't have enough "spare" water to fill the next-smallest bottle, then stop!

This can also be finnicky if you have ties for largest bottle, then you have to choose which one to pour from first, in case one can get filled up and it has more already in there. You will still eventually end up with as many filled as possible, but if you aren't careful you could pour water inefficiently between equally large bottles.

  • $\begingroup$ Counter example: given three bottles (1000,900), (500,200), (300,200). The optimal thing is to take the middle bottle and fill up the other two. It seems like the greedy choice should be based on some expensive check about the bottles. I can’t seem to find it... what do you think? $\endgroup$ – user92484 Jan 6 '19 at 5:50
  • $\begingroup$ “They will all be the smallest bottles” - wrong. They will be the largest possible number of bottles. If there is enough water to fill n smallest bottles but not n+1, there can be many ways to fill n bottles that are not the smallest. $\endgroup$ – gnasher729 Jan 7 '19 at 7:31

The problem is NP-complete, shown by reducing the knapsack problem to it.

Take the knapsack problem: Given are n items with weight 0 < w_i <= 1, and value v_i > 0. Pick items with total weight <= 1, maximising the total value of items picked. Let the total value of all items be V, and the total weight W <= n.

We now take n bottles of capacity 1 + w_i filled with w_i + v_i / 2V and n empty bottles of capacity 1, plus another bottle of capacity 2n and filled with n - W + 1/2. Total amount of fluid is n+1. We can fill n bottles but not n + 1.

If we decide to fill bottle i then we need to pour 1 - v_i/2V, filling an empty bottle requires pouring 1. When we optimise the bottle filling problem, we fill n bottles with the sum of w_i <= 1, and the sum of 1- v_i/2V minimised, so the sum of v_i is maximised, solving the knapsack problem.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy