Upper bound on width in packing problem

Question

Suppose I have $n$ shelves and I'm supposed to store boxes in them starting from left to right. I have two types of boxes. For the first type of boxes $B_1$ I only know their total width, but I do not know how many of those boxes I have and how wide they are. Then I have $x$ boxes of the second type $B_2$. boxes of $B_2$ are all equally wide. The boxes of type $B_1$ have a higher priority, so I have to store them before the boxes of type $B_2$.

Consider the following example with $n = 3$ shelves:
The total width of the boxes of type $B_1$ is $W_{B_1} = 10$. Also I have $(x = )10$ boxes of $B_2$, each of them with a width of $w_{B_2} = 3$. All widths are integers.

A possible packing could look like this (I do not know how to draw tables, so the number between the vertical bars denote the width of one box and the bold, italic numbers mean that it's a box of type $B_1$):

1. Example
   | 5 | 3 | 3 | 3 |
   | 5 | 3 | 3 | 3 |
   | 3 | 3 | 3 | 3 |

In this example, the width of the shelf would be $5+3+3+3 = 14$.

2. Example
   | 3 | 3 | 3 | 3 | 0 |
   | 3 | 3 | 3 | 3 | 3 |
   | 4 | 3 | 3 | 3 | 0 |

Here, the middle shelf (might also be the top shelf, but doesn't actually matter) is the largest with a width $W = 4+3+3+3+3 = 15$.

3. Example
   | 10 | 3 | 0 | 0 | 0 |
   | 3 | 3 | 3 | 3 | 0 |
   | 3 | 3 | 3 | 3 | 3 |

In this example, the bottom or middle shelf would be the widest, with $W = 5*3 = 15$.

How can I calculate an upper bound on the width of the shelves for all possible combinations?

Answer 1

I will write $W_1 = W_{B_1}$ and $w_2 = w_{B_2}.$

As in the other answer, let $F(n,W_1,x,w_2)$ be the minimum length per shelf of an array of $n$ identical shelves that must hold boxes of type $B_1$ with total width $W_1$ and in addition must hold $x$ boxes of type $B_2,$ each of which has width $w_2.$ You asked for a way to calculate an upper bound on $F(n,W_1,x,w_2)$ for any possible input, and you would like that bound to be a tight one.

In the case where $n = 1,$ then $F(n,W_1,x,w_2) = W_1 + x w_2.$ Things only get interesting when $n > 1,$ so in the following we'll assume $n > 1$ until we say otherwise.

Not knowing the number of boxes of type $B_1,$ we cannot rule out the case that there is just one box of this type and its width is $W_1.$ So no matter how many shelves there are and no matter what we know about the other boxes, we have to make the shelves long enough so that we could reserve the first $W_1$ units of length along the first shelf to hold boxes of type $B_1$ and fit the rest of the boxes into the remaining space. In other words, when calculating an upper bound of $F(n,W_1,x,w_2)$ we can assume there is only one box of type $B_1.$ It is possible that when we receive the actual boxes and see what size type $B_1$ is, we will be able to find a packing in which the widest set of boxes on any shelf is less than the width calculated in that way, but since we do not have that information when we compute a bound on $F(n,W_1,x,w_2)$ we cannot use it.

In short, when computing an upper bound of the required width we cannot do better than to put the type $B_1$ box(es) in the leftmost $W_1$ units of width along the first shelf before placing any other boxes. A corollary is that $F(n,W_1,x,w_2) \geq W_1.$

If the width of each shelf is exactly $W_1,$ then we can fit $\lfloor W_1/w_2 \rfloor$ boxes of type $B_2$ on any shelf except the first one, so we can put a total of $(n-1) \lfloor W_1/w_2 \rfloor$ boxes of type $B_2$ on the remaining shelves. So in the case where $x \leq (n-1) \lfloor W_1/w_2 \rfloor,$ we have $F(n,W_1,x,w_2) = W_1.$

Now consider the case where $n>1$ and $x > (n-1) \lfloor W_1/w_2 \rfloor.$ As before, we begin by filling the leftmost $W_1$ units of width on the first shelf with boxes of type $B_1.$ We then put boxes of type $B_2$ in the leftmost $\lfloor W_1/w_2\rfloor w_2 = W_1 - (W_1 \bmod w_2)$ units of width of each of the remaining shelves.

Let $x' = x - (n-1) \lfloor W_1/w_2 \rfloor,$ that is, $x'$ is the remaining number of boxes of type $B_2$ that must be placed after the boxes in the previous paragraph. Now to keep the longest total width of boxes on any shelf as small as possible, we put the first $n-1$ of these boxes on the last $n-1$ shelves, then one box on the first shelf, and repeat until there are no boxes remaining. Then if $x' \equiv 0 \pmod n$ we put exactly $x'/n$ additional boxes on each shelf, so we require the first shelf to have width $W_1 + x'w_2/n$ and this width is enough to hold all the remaining boxes on the other shelves; but if $x' \not\equiv 0 \pmod n$ we must put $\lceil x'/n\rceil$ additional boxes on at least one shelf (which could be the last shelf), so we require the last shelf to have width $W_1 - (W_1 \bmod w_1) + \lceil x'/n\rceil w_2$ and this width is enough to hold all the remaining boxes on the other shelves.

To summarize, $$ F(n,W_1,x,w_2) = \begin{cases} W_1 + x w_2 & n = 1,\\ W_1 & n > 1 \land x \leq x_0,\\ W_1 + \frac{x - x_0}n w_2 & n > 1 \land x > x_0 \land x \equiv x_0 \pmod n,\\ W_1 - (W_1 \bmod w_1) + \lceil\frac{x - x_0}n\rceil w_2 & n > 1 \land x > x_0 \land x \not\equiv x_0 \pmod n \end{cases} $$ where $x_0 = (n-1) \lfloor W_1/w_2 \rfloor.$

Answer 2

I will use $w_1$ for what you call $W_{B_1}$ and $w_2$ for what you call $w_{B_2}$.

Define $F(n, w_1, x, w_2)$ to be the minimum width necessary for $n$ shelves to contain the boxes.

Then it is easy to see that $F(n, 0, x, w_2)=\lfloor {{x+n-1}\over{n}}\rfloor w_2 = \lceil{x\over{n}}\rceil w_2$.

If $F(n-1,0,x,w_2)>w_1>0$, then we can certainly put all of the boxes of type $B_1$ on the first shelf and therefore $F(n,w_1,x,w_2)\le F(n-1,0,x,w_2)$. (This bound can obviously be improved in some cases, but it's not clear to me that the extra work is worthwhile; if anyone is interested, please leave a comment and I'll look into it).

Otherwise, $w_1\ge F(n-1,0,x,w_2)$ and then because of the case where all of the boxes of type $B_1$ are just one large box of width $w_1$ we have $F(n,w_1,x,w_2) = w_1$.