0
$\begingroup$

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$?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – platypus17 Aug 12 at 21:52
  • $\begingroup$ Sure! I'll keep that in mind for the future. $\endgroup$ – platypus17 Aug 13 at 22:29
1
$\begingroup$

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.

You will notice that you make quite a few stupid choices. If you have 10 bins, X = 100, and the sum of weights is 1,000 then puting items with very little weight or total weight over 200 into the first bin is likely stupid. To help with this we find a non-optimal solution with a greedy algorithm. Then we don't accept anything that must be worse than the greedy algorithm. In the example, if the greed algorithm finds a solution with error = 100, then we would never put less than 50 or more than 150 in weight into the first bin.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – platypus17 Aug 12 at 21:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.