Distribute repeated values into bins as evenly as possible

Question

Preface

I've asked a very similar question already on stack overflow in a different wording and gotten a working answer under the assumption that there is no way to go through all possibilities (np-hard).

After doing further research (because this is my bottleneck atm), I stumbled upon this similar question, but again, there's the assumption of the problem beeing np-hard and it's not exactly what I'm looking for. However, it seems the question is a better fit on this site, than SO (correct me if I'm wrong).

I'm pretty sure this can be solved "brute force" (aka optimal) with the correct algorithm in small time for the given constraints. More to that later.

Problem

I have a small set of repeating values e.g.

values = 10 x [18] (ten times the value 18); 5 x [30], 6 x [55]

of which I need to distribute as many as possible evenly across a fixed number of bins with a maximum difference between the bins (maximum difference between the sum of elements in the bins, see below).

Constraints:

The reason I think this can be brute forced are my constraints. I will never have a great number of bins (at the moment the maximum is 3, let's assume it might be 4 or 5 though). The maximum difference between the bins is atm fixed at 2, we can assume it stays there if that helps because I can set this arbitrarily if needed.

Example

For a small example, lets set values = [[18,18,18,18,18],[30,30,30]], number_of_bins = 2 and max_difference_between_bins = 2.

The algorithm to distribute them would be something along the lines

for remainder in range(0,8) #try distributing all packages first, 
 # then one less, then two less, etc.
    generate possible distributions for values in bins
    add the distributions to check differences, if any difference 
      # is below the threshhold of max max_difference_between_bins, break

Trying it out:

Remainder = 0

Distribute 5 times 18 into two bins:

(0,90),(18,72),(36,36),(72,18),(90,0)

Distribute 3 times 30 into two bins:

(0,90),(30,60),(60,30),(90,0)

See that the example is bad because it works out in the first run, anyways, adding them yields:

(0,90) -> (0,180),(30,150),(60,120),(90,90)
(18,72)-> (18,162),(48,132),(78,102)(108,72)
(36,36)-> (36,126),(66,96),(96,66)(126,36)
(72,18)-> (72,108),(102,78),(132,48),(162,18)
(90,0) -> (90,90),(120,60),(150,30),(180,0)

As you can see, half of them are obsolete because they are duplicates.

If there hadn't been a solution (90,90) this would then continue in the next run with trying the same for values = [[18,18,18,18],[30,30,30]] and values = [[18,18,18,18,18],[30,30]] and remainder = [18] or remainder = [30].

Runtime

So for a really big example of say 70 values with 5 different sizes distributed across 3 bins, the possible solutions should be for the first run:

Say 50 values of the same size are distributed across 3 bins, then we get 50+3-1 over 3 = 1326 possibilites or 316251 for 5 bins (right?) (supposing the bins are differentiable, which they don't need to be, but then we would have to upscale later for the combination with the other values).

Distributing the other 20 with say 8, 5, 4, 3 values each thats 45, 21, 15, 10 values. Multiplicated, that's 190 million possibilities. However, most of those combinations can't possibly be a good solution. Some depth search or divide and conquer should be able to break them down.

Of course, those are then multiplied by 5 for the first run with a remainder of 1, by 120 for a run with a remainder of 2, etc. But those solutions can also be generated from the old solutions and again, it should be possible to go through only a fraction of them.

Question

Is basically, how do I get a solution for this in small time? Pseudocode or even python would be great, but not necessary, I can figure the coding out myself.

We can make many assumptions for the number of different values and maximum number of values you want, so if you think the part about reducing it from 190 million times whatever solutions is too big, I'm fine with going down to, for example, maximum 3 bins, maximum 3 different values occuring a maximum of, say, 20 times together (so not 20 times this, 20 times that, but rather 10 times this, 5 times that, 5 times the other).

Answer 1

After an epiphany, I solved the problem myself now. To generate all solutions quite efficiently I have used the following algorithm:

Find all groups of possible bins with any combination of occurences of the values smaller or equal to their maximum occurence that have a sum smaller than (the sum of all values divided by the number of bins + the maximum difference between bins).

Bins include for example [],[18],[18,18],[18,18,18],[30],[30,18], etc.

Calculate the sum of each bin.

Combine only those bins with each other that have a sum that varies by less than the maximum difference.

Chose all combinations as solutions where the number of values in all their bins equals the maximum number of values. if none, reduce maximum number of values and add a value to remainder.

Tested for 3 bins and up to like 50 values, runtime is almost instant in python.