Data Structures, Algorithms, & Applications in Java
Chapter 54, Exercise 1

Equation 54.2 may be used to compute the Wis in the order i = n, n-1, n-2, ..., 1. For each i we try values of k in the order i, i+1, ..., n. If hsum(i,k) > H for some k, then we need not try the remaining values of k.

The code is given below. 
public class EqualWidthFolding
{
   /** fold components with heights h[1 .. h.length - 1] into a
     * rectangle of height theHeight
     * @param w is width of each component
     * @param r is array of space to be left at column ends
     * @param theW[i] is W_i
     * values of theW[1..h.length] and kay[1..h.length-1] are computed
     * by this method
     * @return true iff the folding is possible */
   public static boolean equalWidthFolding(int [] h, int [] r, int w,
                                       int theHeight, int [] theW, int [] kay)
   {
      int n = h.length - 1;  // number of components
      theW[n + 1] = 0;
      for (int i = n; i > 0; i--)
      {// compute theW[i] using Eq. 54.2
         int hsum = 0,              // hsum(i,k)
             minW = w * n + 1;      // min W_i so far
   
         for (int k = i; k <= n; k++)
         {
            hsum += h[k];
            if (hsum > theHeight)
               // infeasible
               break;
            if (hsum + r[i] + r[k + 1] <= theHeight && theW[k + 1] < minW)
            {
               minW = theW[k + 1];
               kay[i] = k;
            }
         }
   
         theW[i] = w + minW;
      }
   
      if (theW[1] > w * n)
        // infeasible
        return false;
      else
         return true;
   }
   
   /** output fold points */
   public static void traceback(int [] kay)
   {
      int n = kay.length - 1;   // number of components
   
      if (kay[1] >= n)
         System.out.println("There are no fold points");
      else
      {// there is at least one fold point
         int i = 1;
         System.out.print("The fold points are ");
         while (kay[i] < n)
         {
            i = kay[i] + 1;
            System.out.print(i + " ");
         }
         System.out.println();
      }
   }
}