Quite honestly, I would duck-and-dodge the problem since there is probably no measurable advantage to an “optimal solution.” I’d say, just choose at random any bin that is big-enough to hold the next object. Any garden-variety random number generator is designed to provide a fairly-even distribution of generated values, so the odds are quite good that the actual distribution obtained for any particular backup will be favorable.
You could also, of course, add a second “back-fill” pass to the algorithm, which examined the initial random result to see if it is obviously-screwy, as in a particular bucket being (say ...) “more than some-n standard deviations away from the mean,” in which case you might, for example, make a random number of attempts to successfully “steal” a randomly-selected item (that will fit ...) from a randomly-chosen bucket in order to drop it into the bucket(s) that are coming-up “short.”
A little bit of simulation should help you determine whether your chosen compromise-algorithm is “good enough for peace work.”