Balancing integer bins to have a certain summation

139 Views Asked by At

Assume that we have bins

$$ B_1, B_2 ..., B_n $$

There exists integer bin values $$ V_1, V_2 ..., V_n $$

Let $$ Total_{V} =\sum_{i=1}^{n} V_i$$

There then exists weights ( $ W $) of each bin to its total Where $$W_i = \frac{V_i}{Total_{v}} $$


Given a new total of bin values $Total_{new}$

I am trying to find the ideal values $$ V'_1, V'_2 ..., V'_n $$ Where $$ \sum_{i=1}^{n} V'_i = Total_{new}$$ and $$ \sum_{i=1}^{n} (W_i - W'_i)$$ is minimized as much as possible.

Put simply, I am trying to take an array of integers and balance them in such a way that their summation is equal to some new provided integer and their new values are as similar as possible to distribution as before.

For example given integers 1,2,3,4 and a goal of 100 the new set of integers would be 10,20,30,40. This is an perfect/easy solution because the old ratios between $\frac{1}{10},\frac{2}{10},\frac{3}{10},\frac{4}{10}$ and $\frac{10}{100},\frac{20}{100},\frac{30}{100},\frac{40}{100}$ are identical.

A non-ideal solution would be given integers 100 and 101 and a goal of 200, the result would be 100 and 100. These ratios are not identical but are as close as possible $\frac{100}{201},\frac{101}{201}$ and $\frac{100}{200},\frac{100}{200}$

A more extreme example would be 10, 1, 10, 10, 15000 with an end goal of 17000. The new set of integers would be like 11, 1, 11, 11, 16966

The method I have devised so far goes through an iterative approach of finding remainders and distributing: https://dotnetfiddle.net/vP5rtN (This only works on an new total that is greater than the old total, that is, it only adds to the bin values and never subtracts)

I am interested in the mathematical ideal approach to this problem.