On May 7, 11:24*pm, sophia <(EMail Removed)> wrote:
> The cutting sticks problemgiven 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 crossposting 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[MAXPIECE1][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 k1'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
