I came across the following algorithm puzzle while interviewing for computer programmer job with a top internet giant.
There are $n=4$ bags with each bag able to carry a maximum of $k=500$ Kilogram weight before it breaks. Then there are many marbles which can attain any weight from $0.001$KG to $500$KG (probability of two marbles having exactly same weight is very low). Each of the $4$ bags is filled with enough marbles to weigh between $400$KG and $495$KG. Write an algorithm to move marbles across the bags so that with minimum number of moves the $4$ bags attain almost equal weight (as much as is possible). Generalize the solution for $n$ and $k$.
Any insight on what is the best algorithm to deal taking all edge cases into account.