The cutting sticks problem---given a stick of length L and a set ofContrary to a suggestion in this thread,
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)
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
