box stacking problem by sorting them according to the sum of their weight+strength

Question

I have a problem by proving the following greedy algorithm gives always a proper solution if there is one.

Given n boxes, each one has fixed weight and strength (w,s). Box's strength defines the load it can carry on top of it. We have to form a pile of boxes and arrange them one on top of another so that all of the boxes will be in the pile. Assuming that there is a solution to the problem I have to prove that i can always claim it by putting the boxes to the stack in descending order of the sum of their weight an strength. That means that given n boxes we will always have the following : w1+s1>w2+s2>...>wn+sn where box1(w1,s1) is at the base of stack and so on.

I understand that the best case is when the heaviest box is at base and the box with max strength is also at base. By running several instances from which we can always obtain a solution, I see that this greedy algorithm also gives a solution.

Any ideas ? Thank you in advance for your help.

Answer 1

To explain the ordering trick, as described in COMP3121/9101/3821/9801 Lecture Notes; More on Dynamic Programming (DP); LiC: Aleks Ignjatovic; School of Computer Science and Engineering; The University of New South Wales; Sydney, Australia:

We'd like to prove that we can rearrange any legitimate box stack to be ordered by weight + strength ascending. To do this we need to show that any consecutive pair where

(1) strength(b_i+1) + weight(b_i+1) < strength(b_i) + weight(b_i)

can be legitimately swapped, since then we could apply bubble sort. In other words, that

(2) (Sum j=1...i−1 of weight(b_j)) + weight(b_i+1) < strength(b_i)

The original, legitimate tower has

(3) (Sum j=1...i−1 of weight(b_j)) + weight(b_i) ≤ strength(b_i+1)

Add weight(b_i+1) to both sides:

(4) (Sum j=1...i−1 of weight(b_j)) + weight(b_i) + weight(b_i+1) ≤ strength(b_i+1) + weight(b_i+1)

Substitute (1) for the right side:

(Sum j=1...i−1 of weight(b_j)) + weight(b_i) + weight(b_i+1) ≤ strength(b_i) + weight(b_i)

Cancel weight(b_i):

(Sum j=1...i−1 of weight(b_j)) + weight(b_i+1) ≤ strength(b_i)

Answer 2

The "obvious" attack is the canonical indirect proof: given that a solution exists, start by assuming the greedy approach is not a solution. Work from there to a contradiction.

So ... we're give a sequence of N boxes; we will number them in the greedy order, as in your problem statement.

A legal stacking is one in which, for all 2 <= i <= n,
sum(w(j=i to n)) <= s(i-i)<br> i.e. box i-1 can hold the weight of all boxes on top of it.

Given that a legal stacking exists, assume that your greedy stacking is not legal. That tells you that there is some value i for which the above weight condition does not hold, but does hold for a different ordering of boxes. Work from that to a contradiction about the greedy box ordering.