diff options
| -rw-r--r-- | 01-knapsack/ks_dp-ng.c | 224 | ||||
| -rwxr-xr-x | 01-knapsack/run | 18 |
2 files changed, 242 insertions, 0 deletions
diff --git a/01-knapsack/ks_dp-ng.c b/01-knapsack/ks_dp-ng.c new file mode 100644 index 0000000..9f98a0d --- /dev/null +++ b/01-knapsack/ks_dp-ng.c @@ -0,0 +1,224 @@ +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <stdint.h> +#include <time.h> +#include <unistd.h> + +#define NONE -1 + +static int debug; + +typedef struct _InputItem +{ + int i; /* item index */ + int v; /* item value */ + int w; /* item weight */ +} InputItem; + +typedef struct _SolverItem { + int i; /* index of the selected item */ + int v; /* cumulated value */ + int w; /* cumulated weight */ +} SolverItem; + +typedef struct _Solver +{ + int k; /* capacity */ + int n; /* items # */ + InputItem *items; /* items */ + SolverItem *column; /* solver column */ +} Solver; + +static void solve(Solver* solver) +{ + int n, k; + int v, w; + int i, j; + const InputItem *item; + SolverItem *data; + const SolverItem *up_left; + + unsigned int counter; + + n = solver->n; + k = solver->k; + + if (debug > 2) + { + printf("\ncurrent V(i,s,W,r)\n"); + } + + /* SOLVE */ + counter = 0; + item = solver->items; + for (i = 0; i < n; i++, item++) + { + v = item->v; + w = item->w; + data = NULL; + data = solver->column + solver->k; + up_left = solver->column + (solver->k - w); + + for (j = k; j >= w; j--, data--, up_left--) + { + counter++; + + if (data->v < (v + up_left->v)) + { + data->i = i; + data->v = v + up_left->v; + data->w = w + up_left->w; + } + } + + if (debug > 2) + { + data = solver->column; + for (j = 0; j <= k; j++, data++) + printf(" % 4d(% 2d % 2d)\n", + data->v, data->i, data->w); + printf("\n"); + } + } + + if (debug == 2) + { + printf("i=%d:\n", solver->n - 1); + data = solver->column; + for (j = 0; j <= k; j++, data++) + printf(" % 4d(% 2d % 2d)\n", + data->v, data->i, data->w); + } + + if (debug > 0) + printf("loops count: %u\n", counter); +} + +static int check(Solver *solver, int excpected_value) +{ + const SolverItem *data; + + if (excpected_value == NONE) + return EXIT_SUCCESS; + + data = solver->column + solver->k; + if (data->v != excpected_value) + { + fprintf(stderr,"*** ERROR found %d != %d excpected !", + data->v, excpected_value); + return EXIT_FAILURE; + } + + return EXIT_SUCCESS; +} + +int main(int argc, char** argv, char** env) +{ + FILE *fp; + + int ret; + int opt; + int i; + int excpected_value; + uint64_t dt; + struct timespec t0; + struct timespec t1; + + Solver solver; + InputItem *item; + + debug = 0; + excpected_value = NONE; + while ((opt = getopt(argc, argv, "d:e:")) != -1) { + switch (opt) { + case 'd': + debug = atoi(optarg); + break; + case 'e': + excpected_value = atoi(optarg); + break; + default: /* '?' */ + fprintf(stderr, "Usage: %s [-d level] input\n", + argv[0]); + return EXIT_FAILURE; + } + } + + if (optind >= argc) { + fprintf(stderr,"input file missing\n"); + return EXIT_FAILURE; + } + + if (debug > 0) printf("%s\n", argv[optind]); + fp = fopen(argv[optind], "r"); + if (fp == NULL) + { + fprintf(stderr, "I couldn't open results.dat for reading.\n"); + return EXIT_FAILURE; + } + + /* read k and n */ + if (fscanf(fp, "%d %d\n", &solver.n, &solver.k) != 2) + { + fprintf(stderr, "ERROR: read first line\n"); + return EXIT_FAILURE; + } + if (debug > 0) printf(" K:%d N:%d\n", solver.k, solver.n); + + /* allocate */ + solver.items = calloc(solver.n, sizeof(InputItem)); + if (!solver.items) + { + fprintf(stderr, "ERROR: items calloc\n"); + return EXIT_FAILURE; + } + + solver.column = calloc((solver.k + 1), sizeof(SolverItem)); + if (!solver.column) + { + free(solver.items); + fprintf(stderr, "ERROR: column calloc\n"); + return EXIT_FAILURE; + } + for (i = 0; i < (solver.k + 1); i++) + { + solver.column[i].i = NONE; + } + + /* read items */ + item = solver.items; + for (i = 0; i < solver.n; i++, item++) + { + item->i = i; + fscanf(fp, "%d %d\n", &item->v, &item->w); + } + fclose(fp); + + if (debug > 1) + { + item = solver.items; + printf(" index Value Weight\n"); + for (i = 0; i < solver.n; i++, item++) + printf(" % 8d % 8d % 8d\n", item->i, item->v, item->w); + } + + clock_gettime(CLOCK_MONOTONIC, &t0); + solve(&solver); + clock_gettime(CLOCK_MONOTONIC, &t1); + + ret = check(&solver, excpected_value); + + if (debug > 0) + { + dt = ((t1.tv_sec * 1000000000) + t1.tv_nsec) - + ((t0.tv_sec * 1000000000) + t0.tv_nsec); + printf(" time %7u [ms]\n", (unsigned int)(dt/1000000)); + } + + free(solver.items); + free(solver.column); + + return ret; +} + diff --git a/01-knapsack/run b/01-knapsack/run new file mode 100755 index 0000000..df6db5e --- /dev/null +++ b/01-knapsack/run @@ -0,0 +1,18 @@ +#! /bin/bash + +RESET="\033[0m" +RED="\033[0;31m" + +BIN=${BIN:-ks_dp-ng} +${CC:-clang} -O2 -pedantic -Wall -o $BIN $BIN.c || exit 1 + +DATAS=(ks_4_0 ks_19_0 ks_30_0 ks_40_0 ks_45_0 ks_50_0 ks_50_1 ks_60_0 ks_100_0 ks_100_1 ks_100_2 ks_200_0 ks_200_1 ks_300_0 ks_400_0 ks_500_0 ks_1000_0 ks_10000_0) +VALUES=(19 12248 99798 99924 23974 142156 5345 99837 99837 1333930 10892 100236 1103604 1688692 3967180 54939 109899 1099893) + +for((i=0;i<${#DATAS[@]};i++)) +do + data="./data/${DATAS[$i]}" + value="${VALUES[$i]}" + echo -e "$RED *** $data -e $value $@ $RESET" + ./$BIN $data -e $value $@ +done |