Re: cutting sticks problem

On May 7, 11:24=A0pm, sophia <sophia.ag...@[EMAIL PROTECTED]
> wrote:
> The cutting sticks problem---given a stick of length L and a set of
> points where it has to be cut. If the cost of making a cut is equal to
> the length of the stick, what is the best algorithm to find the
> optimal sequence of cuts(giving minimum cost)

Contrary to a suggestion in this thread,
the straightforward solution to this puzzle
is not of exponential complexity, but rather N^3/3.
Yes, I know O(N^3) =3D O(N^3/3) but I show the constant
divisor to emphasize that the iterative structure is
related to the volume of a pyramid.

I'm enclosing my source code (and cross-posting to
comp.lang.c) for critique.  The program is *not*
thoroughly tested; I estimate it still has 1.84 bugs.
(Certain peculiar code layout details are to ensure
short lines for Usenet.)

/* begin bestcutter.c */
#include   <stdlib.h>
#include   <stdio.h>

#define   MAXPIECE   100

/* Sol[a][b] describes substick [a ... a+b+1] */
struct {
   double   cost, leng;
   int   cutpt;
} Sol[MAXPIECE-1][MAXPIECE];

int bestcut(int xbeg, int xend)
{
   int     x, bstc;
   double  xcost, cheapest =3D 99999999;

   for (x =3D xbeg + 1; x < xend; x++) {
      xcost =3D
         Sol[xbeg][x - xbeg - 1].cost
         + Sol[x][xend - x - 1].cost;
      if (xcost < cheapest)
         cheapest =3D xcost, bstc =3D x;
   }
   return bstc;
}

double mkcuts(int xbeg, int ncut)
{
   int     cutpt;
   double  tcost;

   if (ncut < 1)
      return 0;
   cutpt =3D Sol[xbeg][ncut].cutpt;
   tcost =3D Sol[xbeg][ncut].leng;
   printf("Making cut at mark %d cost =3D %f\n",
         cutpt, tcost);
   return tcost
      + mkcuts(xbeg, cutpt - xbeg - 1)
      + mkcuts(cutpt, xbeg + ncut - cutpt);
}

int main(int argc, char **argv)
{
   int   ncut, ix1, bstc;

   if (MAXPIECE + 1 < argc || argc < 2) {
      printf("Usage: cutstick #L1 #L2 ... #LN\n");
      printf(" where #Lk is the distance from k-1'th");
      printf(" mark to k'th mark.\n  (0'th and N'th");
      printf(" marks are stick ends.)  N <=3D %d.\n",
         MAXPIECE);
      return EXIT_FAILURE;
   }
   for (ix1 =3D 0; ix1 < argc - 1; ix1++)
      Sol[ix1][0].leng =3D atof(argv[ix1 + 1]);
   for (ncut =3D 1; ncut < argc - 1; ncut++)
      for (ix1 =3D 0; ix1 < argc - ncut + 1; ix1++)
         if (ncut =3D=3D 1) {
            Sol[ix1][ncut].cutpt =3D ix1 + 1;
            Sol[ix1][ncut].cost =3D
            Sol[ix1][ncut].leng =3D
               Sol[ix1][0].leng
               + Sol[ix1 + 1][0].leng;
         } else {
            Sol[ix1][ncut].leng =3D
               Sol[ix1][0].leng
               + Sol[ix1 + 1][ncut - 1].leng;
            Sol[ix1][ncut].cutpt =3D
               bstc =3D bestcut(ix1, ix1 + ncut + 1);
            Sol[ix1][ncut].cost =3D
               Sol[ix1][ncut].leng
               + Sol[ix1][bstc - ix1 - 1].cost
               + Sol[bstc][ncut - bstc + ix1].cost;
         }
   printf("Total cost =3D %f\n", mkcuts(0, argc - 2));
   return EXIT_SUCCESS;
}
/* end bestcutter.c */
/* Sample execution:
 * % bestcutter 2 3 1 5
 * Making cut at mark 3 cost =3D 11.000000
 * Making cut at mark 1 cost =3D 6.000000
 * Making cut at mark 2 cost =3D 4.000000
 * Total cost =3D 21.000000
 */

James Dow Allen