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

Equation 54.5 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 VariableWidthFolding
{
   /** fold components with heights h[1 .. h.length - 1] and widths
     * w[1 .. w.length - 1] into a rectangle of height theHeight
     * @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 variableWidthFolding(int [] h, int [] r, int [] w,
                                      int theHeight, int [] theW, int [] kay)
   {
      int n = h.length - 1;  // number of components
      theW[n + 1] = 0;
      // determine sum of widths
      int widthSum = 0;
      for (int i = 1; i <= n; i++)
         widthSum += w[i];

      for (int i = n; i > 0; i--)
      {// compute theW[i] using Eq. 54.5
         int hsum = 0,                   // hsum(i,k)
             wmax = 0,                   // wmax(i,k)
             minW = widthSum + 1;        // min value for W_i so far
   
         for (int k = i; k <= n; k++)
         {
            hsum += h[k];
            if (hsum > theHeight)
               // infeasible
               break;
            if (w[k] > wmax)
               wmax = w[k]; 
            if (hsum + r[i] + r[k + 1] <= theHeight &&
                wmax + theW[k + 1] < minW)
            {
               minW = wmax + theW[k + 1];
               kay[i] = k;
            }
         }
         theW[i] = minW;
      }
   
      if (theW[1] == widthSum + 1)
        // 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();
      }
   }
}