/*---------------------------------------------------------------------- File : knapsack.c Contents: algorithms for the knapsack problem Author : Christian Borgelt History : 06.04.1998 file created ----------------------------------------------------------------------*/ #include #include #include /*---------------------------------------------------------------------- Preprocessor Definitions ----------------------------------------------------------------------*/ #define BLKSIZE 256L /* block size for object vector */ /* --- error codes --- */ #define OK 0 /* no error */ #define E_NONE 0 /* no error */ #define E_NOMEM (-1) /* not enough memory */ #define E_FOPEN (-2) /* file open failed */ #define E_FREAD (-3) /* file read failed */ #define E_FWRITE (-4) /* file write failed */ #define E_METHOD (-5) /* illegal packing method */ #define E_KSSIZE (-6) /* illegal knapsack size */ #define E_SIZE (-7) /* illegal object size */ #define E_VALUE (-8) /* illegal object value */ #define E_UNKNOWN (-9) /* unknown error */ /*---------------------------------------------------------------------- Type Definitions ----------------------------------------------------------------------*/ typedef struct { /* --- an object --- */ int id; /* object identifier */ int size; /* size of the object */ int value; /* value of the object */ int cnt; /* number of selected objects */ } OBJECT; /* (object) */ typedef struct { /* --- table element for dynprg() --- */ int value; /* value of the knapsack */ int last; /* last object added */ } TABELEM; /* (table element) */ /*---------------------------------------------------------------------- Constants ----------------------------------------------------------------------*/ const char *errmsgs[] = { /* error messages */ /* E_NONE 0 */ "no error\n", /* E_NOMEM -1 */ "not enough memory\n", /* E_FOPEN -2 */ "cannot open file `%s'\n", /* E_FREAD -3 */ "read error on file `%s'\n", /* E_FWRITE -4 */ "write error on file `%s'\n", /* E_METHOD -5 */ "illegal packing method %d\n", /* E_KSSIZE -6 */ "illegal knapsack size %d\n", /* E_SIZE -7 */ "illegal object size %d\n", /* E_VALUE -8 */ "illegal object value %d\n", /* E_UNKNOWN -9 */ "unknown error\n" }; /*---------------------------------------------------------------------- Global Variables ----------------------------------------------------------------------*/ static char *prgname; /* program name for error messages */ /*---------------------------------------------------------------------- Auxiliary Functions (for qsort) ----------------------------------------------------------------------*/ int idcmp (const void *p1, const void *p2) { /* --- compare object identifiers */ const OBJECT *o1 = p1, *o2 = p2; /* pointers to objects */ if (o1->id < o2->id) return -1; /* return the negated sign of */ return (o1->id > o2->id) ? 1 : 0; /* the identifier difference */ } /* idcmp() */ /*---------------------------------------------------------------------- If passed to the standard library function qsort, the above function leads to ascending object identifiers, the next two functions lead to ascending (absolute or relative) value with descending size within the same (absolute or relative) value. ----------------------------------------------------------------------*/ int abscmp (const void *p1, const void *p2) { /* --- compare absolute object values */ const OBJECT *o1 = p1, *o2 = p2; /* pointers to objects */ if (o1->value < o2->value) return -1; /* return the sign of */ if (o1->value > o2->value) return 1; /* the value difference */ if (o1->size < o2->size) return 1; /* return the negated sign */ return (o1->size > o2->size) ? -1 : 0; /* of the size difference */ } /* abscmp() */ /*--------------------------------------------------------------------*/ int relcmp (const void *p1, const void *p2) { /* --- compare relative object values */ const OBJECT *o1 = p1, *o2 = p2; /* pointers to objects */ float v1, v2; /* relative object values */ v1 = (float)o1->value / o1->size; /* compute the */ v2 = (float)o2->value / o2->size; /* relative object values */ if (v1 < v2) return -1; /* and return the sign */ if (v1 > v2) return 1; /* of their difference */ if (o1->size < o2->size) return 1; /* return the negated sign */ return (o1->size > o2->size) ? -1 : 0; /* of the size difference */ } /* relcmp() */ /*---------------------------------------------------------------------- Main Functions ----------------------------------------------------------------------*/ int dynprg (OBJECT objs[], int cnt, int max, int *size) { /* --- dynamic programming */ int i, k, n; /* loop variables and table index */ TABELEM *tab; /* table for intermediate results */ int value; /* buffer for (maximal) value */ tab = (TABELEM*)calloc(max +1, sizeof(TABELEM)); if (!tab) return -1; /* allocate table */ for (i = 0; i < cnt; i++) { /* traverse objects and sizes */ for (n = 0, k = objs[i].size; k <= max; k++, n++) { value = tab[n].value +objs[i].value; if (value <= tab[k].value) continue; tab[k].value = value; /* construct a new solution by adding */ tab[k].last = i; /* the current object's value to the */ } /* solution retrieved above, and if */ } /* the value increases, note it */ value = tab[max].value; /* get value of optimal solution */ for (n = max; --n >= 0; ) /* find smallest optimal solution */ if (tab[n].value < value) break; for (k = ++n; k > 0; ) { /* fill knapsack with objects */ objs[i = tab[k].last].cnt++;/* count last object added and */ k -= objs[i].size; /* get index of table element with */ } /* solution of smaller problem */ free(tab); /* deallocate table */ *size = n; /* set the knapsack size and return */ return value; /* the value of the knapsack contents */ } /* dynprg() */ /*--------------------------------------------------------------------*/ int greedy (OBJECT objs[], int cnt, int max, int abs, int *size) { /* --- greedy object selection */ OBJECT *o; /* to traverse the objects */ int left = max; /* space left in knapsack */ int value = 0; /* value of knapsack contents */ qsort(objs, cnt, sizeof(OBJECT), (abs) ? abscmp : relcmp); o = objs +cnt; /* sort objects acc. to their value */ while ((left > 0) && (--o >= objs)) { /* while there is space left */ o->cnt = left /o->size; /* take as many objects as possible */ left -= o->cnt *o->size; /* of the next object type, subtract */ value += o->cnt *o->value; /* their size from the space left, */ } /* and sum their value */ qsort(objs, cnt, sizeof(OBJECT), idcmp); /* resort the objects */ *size = max -left; /* set the knapsack size and return */ return value; /* the value of the knapsack contents */ } /* greedy() */ /*--------------------------------------------------------------------*/ void error (int code, ...) { /* --- print error message */ va_list args; /* list of variable arguments */ const char *msg; /* buffer for error message */ if ((code > 0) || (code < E_UNKNOWN)) code = E_UNKNOWN; /* check error code */ msg = errmsgs[-code]; /* get error message */ if (!msg) msg = errmsgs[-E_UNKNOWN]; fprintf(stderr, "\n%s: ", prgname); /* print program name */ va_start(args, code); /* get variable arguments */ vfprintf(stderr, msg, args); /* print error message */ va_end(args); /* end variable argument evaluation */ exit(code); /* abort programm */ } /* error() */ /*--------------------------------------------------------------------*/ int main (int argc, char *argv[]) { /* --- main function */ int i; /* loop variable */ int size, value; /* size and value of an object */ int max; /* maximal size of knapsack */ OBJECT *objs = NULL; /* vector of available objects */ int vsz = 0; /* current size of the vector */ int cnt = 0; /* number of objects in the vector */ FILE *in = stdin; /* file to read objects from */ FILE *out = stdout; /* file to write objects to */ int method; /* knapsack packing method */ prgname = argv[0]; /* program name for error messages */ /* --- print a usage message --- */ if ((argc != 3) && (argc != 4)) { /* if wrong number of args. given */ printf("usage: %s m infile [outfile]\n", argv[0]); printf("solve knapsack problem in file `filename' with method m\n"); printf("m = 0: dynamic programming\n"); printf("m = 1: greedy maximal absolute value\n"); printf("m = 2: greedy maximal relative value\n"); printf("if 'infile' starts with a '-', " "input is read from stdin.\n"); printf("if 'outfile' starts with a '-', " "output is written to stdout.\n"); printf("format of infile:\n"); printf("first line: maximal size of knapsack\n"); printf("next lines: pairs of object size and value\n"); return 0; /* print a usage message */ } /* and abort the function */ /* --- get packing method id --- */ method = atoi(argv[1]); /* get and check packing method id */ if ((method < 0) || (method > 2)) error(E_METHOD, method); /* --- read knapsack size and objects --- */ if (argv[2][0] != '-') { /* if to read objects from a file */ in = fopen(argv[2], "r"); /* open the input file */ if (!in) error(E_FOPEN, argv[2]); printf("reading %s ... ", argv[2]); fflush(stdout); } if (fscanf(in, "%d", &max) != 1) error(E_FREAD, argv[2]); /* read max. size of knapsack */ if (max <= 0) error(E_KSSIZE, max); /* and check it */ while (fscanf(in, "%d%d", &size, &value) == 2) { if (size <= 0) error(E_SIZE, size); /* check size and value */ if (value <= 0) error(E_VALUE, value); /* (both must be > 0) */ if (cnt >= vsz) { /* if the object vector is full */ vsz += (vsz > BLKSIZE) ? (vsz >> 1) : BLKSIZE; objs = (OBJECT*)realloc(objs, vsz *sizeof(OBJECT)); if (!objs) error(E_NOMEM); } /* allocate a larger object vector */ objs[cnt ].id = cnt+1; /* add the object read at the */ objs[cnt ].size = size; /* end of the object vector, */ objs[cnt ].value = value; /* note its size and value, */ objs[cnt++].cnt = 0; /* and clear its counter */ } if (ferror(in)) error(E_FREAD, argv[2]); if (in != stdin) { /* if input has been read from a file, */ fclose(in); /* close the input file */ printf("[size %d, %d objects] done.\n", max, cnt); } /* print a success message */ if (cnt <= 0) { /* check number of objects read */ printf("%s: nothing to do\n", argv[0]); return 0; } /* --- pack knapsack --- */ printf("packing knapsack ... "); fflush(stdout); switch (method) { /* evaluate the const. method id */ case 1: case 2: value = greedy(objs, cnt, max, (method < 2), &size); break; default: value = dynprg(objs, cnt, max, &size); break; } /* pack the knapsack */ if (value < 0) error(E_NOMEM);/* and print the result */ printf("[size %d, value %d] done.\n", size, value); /* --- print the knapsack --- */ if (argc > 3) { /* if output file name given */ if (argv[3][0] != '-') { /* if to write objects to a file */ out = fopen(argv[3], "w");/* open the output file */ if (!out) error(E_FOPEN, argv[3]); printf("writing %s ... ", argv[3]); fflush(stdout); } fprintf(out, "obj cnt size total value total\n"); for (i = 0; i < cnt; i++) { /* traverse the object vector and */ if (objs[i].cnt <= 0) continue; /* print the sel. objects */ fprintf(out, "%3d: %4d ", objs[i].id, objs[i].cnt); fprintf(out, "%5d %5d ", objs[i].size, objs[i].cnt * objs[i].size); fprintf(out, "%5d %5d\n", objs[i].value, objs[i].cnt * objs[i].value); } /* print object information */ fprintf(out, "%-16s %5d %6s %5d\n", "sum:", size, "", value); if (out != stdout) { /* if output was to a file */ if (fclose(out) != 0) error(E_FWRITE, argv[3]); printf("done.\n"); /* close the output file and */ } /* print a success message */ } free(objs); /* delete the object vector */ return 0; /* return `ok' */ } /* main() */