Data Structures, Algorithms, & Applications in Java
Chapter 18, Exercise 12

(a)

Our greedy algorithm examines the cartons in the order 0, 1, 2, .... A carton is placed into the current substack so long as this placement does not cause the height of the current substack to exceed height. If an object cannot be placed in the current substack a new substack is started.

(b)

The greedy algorithm folds into the fewest number of substacks. To prove this we begin by assuming that there is no carton whose height exceeds height. So the folding can be done.

Consider any instance of the stack-folding problem. Let G be the greedy folding and let O be a folding that uses the fewest number of substacks. We shall show that G and O use the same number of substacks. Therefore, G is also a folding that uses the minimum number of substacks.

Our proof will asume that the substacks of a folding are ordered so that each carton in substack i has a smaller index than every carton in substack i+1.

Let substackG(i) be the substack into which carton i is folded in the greedy folding. Let substackO(i) be the substack into which carton i is folded in the greedy folding. Let n be the number of i for which substackG(i) != substackO(i). We use induction on n.

Induction Base
When n = 0, the two foldings are identical, and so they use the same number of substacks.

Induction Hypothesis
Let m be any integer >= 0. Assume that G is identical to a folding that uses the fewest number of substacks whenever n = m.

Induction Step
We will show that the two foldings use the name number of substacks when n = m+1.

Let i be the smallest integer such that substackG(i) != substackO(i). Such an i must exist because n = m+1 > 0.

If substackG(i) > substackO(i) then substackG(i) is not the first stack and so i is not the first carton (recall that the greedy algorithm always places the first carton into the first substack). From the way we chose i and the way the greedy algorithm works, it follows that substackO(i) = substackO(i-1) = substackG(i-1) = substackG(i)-1 and that in folding O substackO(i) has all the cartons that the greedy folding has in this substack. In addition O has carton i. This means that the height of substack i in folding O exceeds height (as, otherwise, the greedy algorithm would not have started a new substack for carton i). So O is an infeasible folding. This contradicts the fact that O is feasible by the way we chose this folding. Therefore, substackG(i) < substackO(i).

Now we may change substackO(i) to substackG(i) to get a feasible folding O' that uses the same number of substacks as does O. Hence O' is a feasible folding that uses the fewest number of substacks. Furthermore, the number of i for which substackG(i) != substackO'(i) is m. From the induction hypothesis it follows that G and O' (and hence O) use the same number of substacks.

(c)

The code for the greedy stack-folding algorithm is given below.

---

public class GreedyStackFolding
{
   /** @param h h[0:h.length - 1] is the array of carton heights
     * all heights are assumed to be > 0
     * @param height is maximum allowable height of a folded substack
     * @return an array substack such that substack[i] is
     * the substack into which carton i is folded
     * @return null iff h[i] > height for some i */
   public static int [] fold(double [] h, double height)
   {
      int [] substack = new int [h.length];
      int currentSubstack = 0;      // start with substack 0
      double currentHeight = 0;     // height of current substack

      // fold cartons into substacks in the order 0, 1, ...
      for (int i = 0; i < h.length; i++)
      {// pack carton i
         if (h[i] > height)
            // folding not possible
            return null;

         if (currentHeight + h[i] > height)
         {// start a new substack
            substack[i] = ++currentSubstack;
            currentHeight = h[i];
         }
         else
         {// put carton i into current substack
            substack[i] = currentSubstack;
            currentHeight += h[i];
         }
      }

      return substack;
   }
}

(d)

The code has a single for loop that iterates O(n) times where n is the number of cartons. Each iteration of this for loop takes O(1) time. Therefore, the time spent in the for loop is O(n). The remainder of the code also takes O(n) time. Therefore, the overall complexity is O(n).