(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?