**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).*