Data Structures, Algorithms, & Applications in C++
Chapter 54, Exercise 2

First, we handle a few special cases. When the number of components is zero, the folding is possible regardless of the value of W; when we have one or more components, the folding cannot be done when W < w; and when n = 1 and W >= w, there are no fold points possible. All other cases as handled by computing the H values.

First, the H_i,1 and H_n,j values are computed. Next, Equation 54.2 is be used to compute the remaining H_i,js. The computation order is i = n-1, n-2, ..., 1. For each i, the order for the js is 2, 3, 4, ... s. For each H_i,j, we try values of k in the order i, i+1, ..., n-1.

The code is given below.

boolean equalWidthFolding(int h[], int r[], int w,, int n
                          int theWidth, int theH[][], int kay[][]
{// Fold components with heights h[1 .. n] into a
 // rectangle of width theWidth.
 // w is width of each component.
 // r is array of space to be left at column ends.
 // theH[i][j] is H_(i,j).
 // Values of theH[1..n][1..theWidth/w] and
 // kay[1..n][1..theWidth/w] are computed by this method.
 // Return true iff the folding is possible.
   int s = theWidth / w;  // max number of stacks
   if (n < 1)
      return true;
   if (s < 1)
      return false;
   if (n < 2)
      return true;

   // set boundary values of theH
   int hsum = 0;
   for (int i = n; i > 0; i--)
   {
      hsum += h[i];
      theH[i][1] = hsum + r[i];
   }
   for (int j = 1; j <= s; j++)
      theH[n][j] = h[n] + r[n];

   // compute remaining values using Eq. 54.4
   for (int i = n - 1; i > 0; i--)
      for (int j = 2; j <= s; j++)
      {
         hsum = 0;
         int minH = theH[1][1];   // upper bound
         int theK = 0;
         for (int k = i; k < n; k++)
         {
            hsum += h[k];
            int maxTerm = max(hsum + r[i] + r[k + 1],
                                   theH[k + 1][j - 1]);
            if (maxTerm < minH)
            {
               minH = maxTerm;
               theK = k;
            }
         }   
         theH[i][j] = minH;
         kay[i][j] = theK;
      }
   return true;
}

void traceback(int kay[][], int theWidth, int w, int n)
{// Output fold points.
   int s = theWidth / w;     // max number of stacks

   // find first nonzero kay[1][], this is also the number of stacks
   int j;
   for (j = s; j > 1; j--)
      if (kay[1][j] > 0)
         break;

   if (j < 2 || n < 2)
      cout << "There are no fold points" << endl;
   else
   {// there is at least one fold point
      cout << "The fold points are " << endl;
      int i = 1;
      while (j > 1)
      {
         i = kay[i][j] + 1;
         cout << i + " ";
         j--;
      }
      cout << endl;
   }
}

Data Structures, Algorithms, & Applications in C++ Chapter 54, Exercise 2

Data Structures, Algorithms, & Applications in C++
Chapter 54, Exercise 2