On Fri, 9 May 2008 03:48:20 -0700 (PDT), James Dow Allen
<jdallen2000@[EMAIL PROTECTED]
> wrote:
>On May 7, 11:24 pm, 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) = 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 */
[snip code]
>
>James Dow Allen
I think that you could use a better algorithm. You are repeatedly
calculating the cost of the same sticks as part of your subproblems.
If there is a stick with marks at a, b, c, ... x, y, z then if you
make the first cut as a and the second cut at z you are left with a
stick of length z-a with cuts at b, c, ... x, y. If you make the
first cut at z and the second cut at a then you will have exactly the
same subproblem to solve. Saving the result and retrieving it would
be much faster than re-solving a problem you had already solved. This
needs more memory than the simple algorithm of course.
It would probably not be worthwhile storing intermediate results for
0, 1 or 2 cuts since there is no choice possible for 0 or 1 cuts and
there is an obvious algorithm for 2 cuts (cut off the longer
end-piece). I am not sure if there is an easy algorithm for three
cuts, not having thought about it at any length.
rossum
|
