There are sources with the following volumes: $p_1, ..., p_n$. Every source volume is greater than $0$.
There are destinations with the following volumes: $q_1, ..., q_m$. Every destination volume is greater than $0$.
There is the following condition $p_1+...+p_n = q_1+...+q_m$.
Every source transfers its whole volume to one or more destinations, so that the destination is filled up.
For example, if we have $n=3,\ m=2$ and $p_1 = 2,\ p_2 = 3,\ p_3=7; q_1=8,\ q_2=4$ sources can fill the destinations as follows: $p_1,\ p_2,\ p_3 fill\ q_1$ and what is left from $p_3$ after filling $q_1$ should $fill\ q_2$.
The price of one source filling is $1$. That means, that in the example above the filling price would be $4$ - we would pay for three fillings of $q_1$ and one filling of $q_2$.
My task is to come up with the algorithm which would produce such a distribution of the sources among destinations that the price would be the lowest possible. And the algorithm should have a better (at least constant amount of steps better) performance than a greedy algorithm (going through all distributions and choosing one of them).
The task is solely for learning purposes. I am just interested in algorithms and optimizations and got the task from the lecturer for my leisure time.
I am sure I will have no problems with showing that the algorithm at least by a constant better than a greedy algorithm for the task.
My problem is that I can not come up with the algorithm or at least prove its correctness. Here is what I come up with so far: I think it would be nice to sort destinations, then iterate over every destination in ascending destination volume order and assign the largest subset (the subset with the most elements in it) of sources possible to it. But I can not prove the correctness of the solution.
Will be glad to get any help here. Whether it is a prove of the correctness of my solution or a totally different solution, or at least a hint in which direction should I seek.
Here are some references I think may help to tackle the task: https://en.wikipedia.org/wiki/Transportation_theory_(mathematics) https://en.wikipedia.org/wiki/Knapsack_problem