4
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

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

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.

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

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.