Velocity Reviews > Re: cutting sticks problem

# Re: cutting sticks problem

James Dow Allen
Guest
Posts: n/a

 05-09-2008
On May 7, 11:24*pm, sophia <(E-Mail Removed)> 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][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 = 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
Guest
Posts: n/a

 05-11-2008
On May 11, 3:49*pm, rossum <(E-Mail Removed)> wrote:
> On Fri, 9 May 2008 03:48:20 -0700 (PDT), James Dow Allen
> <(E-Mail Removed)> 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
Guest
Posts: n/a

 05-12-2008
On May 11, 6:44*pm, rossum <(E-Mail Removed)> 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

Greg Herlihy
Guest
Posts: n/a

 05-12-2008
On May 11, 2:51*am, James Dow Allen <(E-Mail Removed)> 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