Re: cutting sticks problem

Discussion in 'C Programming' started by James Dow Allen, May 9, 2008.

  1. On May 7, 11:24 pm, sophia <> 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) = 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] 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 = 99999999;

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

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

    if (ncut < 1)
    return 0;
    cutpt = Sol[xbeg][ncut].cutpt;
    tcost = Sol[xbeg][ncut].leng;
    printf("Making cut at mark %d cost = %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 <= %d.\n",
    MAXPIECE);
    return EXIT_FAILURE;
    }
    for (ix1 = 0; ix1 < argc - 1; ix1++)
    Sol[ix1][0].leng = atof(argv[ix1 + 1]);
    for (ncut = 1; ncut < argc - 1; ncut++)
    for (ix1 = 0; ix1 < argc - ncut + 1; ix1++)
    if (ncut == 1) {
    Sol[ix1][ncut].cutpt = ix1 + 1;
    Sol[ix1][ncut].cost =
    Sol[ix1][ncut].leng =
    Sol[ix1][0].leng
    + Sol[ix1 + 1][0].leng;
    } else {
    Sol[ix1][ncut].leng =
    Sol[ix1][0].leng
    + Sol[ix1 + 1][ncut - 1].leng;
    Sol[ix1][ncut].cutpt =
    bstc = bestcut(ix1, ix1 + ncut + 1);
    Sol[ix1][ncut].cost =
    Sol[ix1][ncut].leng
    + Sol[ix1][bstc - ix1 - 1].cost
    + Sol[bstc][ncut - bstc + ix1].cost;
    }
    printf("Total cost = %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 = 11.000000
    * Making cut at mark 1 cost = 6.000000
    * Making cut at mark 2 cost = 4.000000
    * Total cost = 21.000000
    */

    James Dow Allen
    James Dow Allen, May 9, 2008
    #1
    1. Advertising

  2. On May 11, 3:49 pm, rossum <> wrote:
    > On Fri, 9 May 2008 03:48:20 -0700 (PDT), James Dow Allen
    > <> wrote:
    > >the straightforward solution to this puzzle
    > >is not of exponential complexity, but rather N^3/3.

    >
    > >I'm enclosing my source code (and cross-posting to
    > >comp.lang.c) for critique.


    > I think that you could use a better algorithm.  You are repeatedly
    > calculating the cost of the same sticks as part of your subproblems.


    No. Reread the source to see that the code calculates and saves the
    intermediate results exactly as you describe. It is the caller of
    bestcut()
    rather than bestcut() itself that saves these results -- is that
    where your confusion lies?

    My algorithm is O(N^3). Are your comments intended to suggest
    existence of a less complex algorithm?

    James
    James Dow Allen, May 11, 2008
    #2
    1. Advertising

  3. On May 11, 6:44 pm, rossum <> wrote:
    > On Sun, 11 May 2008 02:51:38 -0700 (PDT), James Dow Allen wrote
    >
    > >No.  Reread the source to see that the code calculates and saves the
    > >intermediate results exactly as you describe.

    >
    > It does indeed, my mistake.  Thankyou for the correction.


    Thank *you* for bringing closure to this subthread.
    Everyone can (and does) make mistakes. *Acknowledging*
    a mistake, especially in these newsgroups, is as rare
    as spotting a beautiful butterfly on a stormy day.

    > Apologies for my mistake.


    I think mine was the bigger mistake. A few well chosen
    comments in the source would have prevented any
    confusion.

    James
    James Dow Allen, May 12, 2008
    #3
  4. James Dow Allen

    Greg Herlihy Guest

    On May 11, 2:51 am, James Dow Allen <> wrote:
    >
    > My algorithm is O(N^3).  Are your comments intended to suggest
    > existence of a less complex algorithm?


    I'm unclear why the program has a complexity of N^3 instead of N!
    (which is the number of ways in which the stick can be cut.)

    Greg
    Greg Herlihy, May 12, 2008
    #4
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. MattB

    cutting down on postbacks

    MattB, Apr 2, 2004, in forum: ASP .Net
    Replies:
    1
    Views:
    365
    Jim Corey
    Apr 3, 2004
  2. Dave
    Replies:
    1
    Views:
    648
    John Timney \( MVP \)
    Feb 2, 2006
  3. NES

    JApplet: Button Sticks!

    NES, Aug 4, 2005, in forum: Java
    Replies:
    2
    Views:
    488
    Andrew Thompson
    Aug 4, 2005
  4. Raven

    cutting out the tags

    Raven, Jul 26, 2003, in forum: HTML
    Replies:
    2
    Views:
    448
    Robert Frost-Bridges
    Jul 27, 2003
  5. MoshiachNow

    Tk- getOpenFile sticks on W2K server

    MoshiachNow, Sep 25, 2006, in forum: Perl Misc
    Replies:
    6
    Views:
    147
    MoshiachNow
    Nov 16, 2006
Loading...

Share This Page