# n bag of sand and one algorithms

We have $n$ bags of sand, with volume $$v_1,...,v_n, \forall i: \space 0 < v_i < 1$$ but not essentially sorted. we want to place all bag to boxes with volumes 1. We propose one algorithm:

At first we place all bags in the original order. Then we select one box and place on it, bag $1, 2, 3,...$ until these can be place in box. If the $i^{th}$ bag couldn't be inserted in a box, we choose another box and place it $i^{th}, i^{th+1},...$ until these can be place in the box.

If the number of boxes that be used in this algorithms $X$, and the number of boxes used in minimum way (by using minimum algorithms) be $Y$, why always $X > Y$ is false, and always true that $X < 2Y$.

In the best efficient way, each box is completely full:

$$Y=\Sigma v_i$$

So in general

$$Y\ge \Sigma v_i$$

In addition, in your algorithm, each two consecutive box must have at least one unit sand (otherwise the first box could accommodate the next one). So, even in the worst case:

$$\Sigma v_i>\frac X2$$

when X is even and

$$\Sigma v_i>\frac {X-1}2$$ when X is odd.

Combining two in-equations:

$$\frac X2 < \Sigma v_i \le Y$$

or

$$X < 2Y$$

for when X is even.

for odd cases of X we have $$X < 2Y+1$$

However, since 2Y is even, X=2Y does not happen and it can be re-written as:

$$X < 2Y$$

So, for both odd and even cases of X:

$$X < 2Y$$

• i edit a litle in my question. – Ali Movagher Feb 20 '15 at 18:37
• @AliMovagher better to change $X < 2Y$ to $X \le 2Y$ too. – Arashium Feb 20 '15 at 18:38
• would u please some detail and counterexample for X > Y is wrong? – Ali Movagher Feb 20 '15 at 18:39
• @AliMovagher, what if all $v_i>0.5$? then $X=Y=n$ so $X>Y$ is no longer correct. – Arashium Feb 20 '15 at 18:41
• X<= 2Y is correct ? and x >= Y ? – Ali Movagher Feb 20 '15 at 18:56

If $Y$ is the minimum number of boxes used by any algorithm and $X$ is the number of boxes used by your algorithm, then it must be that $X\ge Y$ simply by the way we defined $Y$.

If $X<Y$, then $Y$ couldn't be the minimum number of boxes used by any algorithm because your algorithm produces a smaller result.

It may be that you can prove that $X<2Y$, but that doesn't contradict anything about our discussion above.

• X <= 2Y. is proven., but i dont know how. – Ali Movagher Feb 20 '15 at 18:31
• How we can prove X < 2Y? – Ali Movagher Feb 20 '15 at 18:34
• i edit a litle in my question – Ali Movagher Feb 20 '15 at 18:38
• $\lceil \sum_{i=1}^nv_i\rceil=Y$, right? – Laars Helenius Feb 20 '15 at 18:41
• i didnt underestand. – Ali Movagher Feb 20 '15 at 18:55