# Approximate bin-packing?

Let $$X_1,...X_n$$ denote some bins, and $$w_1,...w_m$$ some positive real numbers, where $$m \in \mathbb{N}$$, and the order matters, so e.g. we can't switch the position of $$w_n$$ and $$w_1$$. The goal is to take a subset of $$\{w_1,...w_m\}$$ and assign it for each bin, i.e. $$\{w_1,...w_{i1}\}$$ would go to bin 1, $$\{w_{i_1+1},... w_{i_2}\}$$ would go to bin 2,...$$\{w_{i_{n-1}+1},...w_{m}\}$$ would go into bin $$n$$, such that each bin contains "roughly" an equal sum of $$w_i's$$, e.g. the sums for $$X_1,...X_n$$ could approximately equal $$100$$, so $$X_1$$ could have a sum of 104, $$X_2$$ could have a sum of 97,... etc. Let's say this "equal sum" is $$Z$$.

Letting $$Y_i$$ be the sum for each $$i^{th}$$ bin, is there a way to choose Z such that the error is minimized, error being defined as $$\sum_i |Y_i-Z|$$, where $$1 \leq i \leq n$$?

• Ah yes sorry this wasn't clear, I agree $\{w_1,....w_m\}$ is not really a partition because order matters here; gnasher729 has the correct interpretation where I want $w_1,...w_{i1}$ in the first bin, $w_{i_1+1},....w_{i_2}$ to the second bin, etc. Aug 12 '20 at 21:52
• Sure! I'll keep that in mind for the future. Aug 13 '20 at 22:29

I assume you want to put items $$w_1$$ to $$w_{i_1}$$ into the first bin, $$w_{i_1+1}$$ to $$w_{i_2}$$ into the second bin, etc. etc. The number n of bins is given. This can be done with something similar to dynamic programming.
Examine all possible choices for $$_1$$ and calculate the error from bin 1 for each of these choices.
Then examine all possible choices for $$i_2$$. For each $$i_2$$ pick all possible $$i_1$$ and pick one where the total error from bin 1 and bin 2 is as small as possible. For each $$i_2$$, remember which $$i_1$$ was used with it.
Then examine all possible choices for $$i_3$$ etc. For $$i_n$$ there is obviously only one choice, and you have the solution.
• How do we integrate the greedy algorithm into your dynamic programming example? Does the greedy algorithm work something like this: when you're looking at $i_2$ are you using only the $i_1$ that minimizes the error from the first bin? Likewise, for the $i_3$ are you fixing the $i_1$ and $i_2$ combination that minimizes the combined error from bin 1 and bin 2? Aug 12 '20 at 21:48