Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Re: cutting sticks problem

Reply
Thread Tools

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
 
Reply With Quote
 
 
 
 
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
 
Reply With Quote
 
 
 
 
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
 
Reply With Quote
 
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

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Cutting and pasting a person to another photo - light/colour problem Brian Digital Photography 6 06-23-2009 01:44 AM
4 memory sticks w/Vista64 problem steveonan Windows 64bit 3 02-05-2008 07:48 AM
What DRAM sticks w/o peeking? Andrew Gideon Cisco 1 12-29-2004 03:10 AM
geocities guestbook problem - cutting visitor comments!!! ARGH!!! Ja D Digital Photography 4 07-02-2004 06:16 AM
problem with nf7 v2.0, 200fsb, 2 sticks ram Geoff A+ Certification 2 07-04-2003 10:25 PM



Advertisments