From 12894c00980227baa8c2660eaebb92d632a6d78e Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?J=C3=A9r=C3=A9my=20Zurcher?= Date: Wed, 3 Jul 2013 14:32:12 +0200 Subject: Discrete : 01-knapsack: 1 vector + bit fields + pointer arithmetic --- 01-knapsack/ks_dp.c | 282 ++++++++++++++++++++++++++++------------------------ 1 file changed, 154 insertions(+), 128 deletions(-) diff --git a/01-knapsack/ks_dp.c b/01-knapsack/ks_dp.c index 25e92cb..1ba27b9 100644 --- a/01-knapsack/ks_dp.c +++ b/01-knapsack/ks_dp.c @@ -1,29 +1,142 @@ #include #include -#include +#include +#include -int main(int argc, char** argv, char** env) +static int debug = 0; + +typedef uint32_t word_t; +enum { WORD_BITS = sizeof(word_t) * 8 }; + +static inline int bindex(int b) { return b / WORD_BITS; } +static inline int boffset(int b) { return b % WORD_BITS; } + +static inline void set_bit(word_t *bits, int b) { - int k; // capacity - int n; // items # - int *values; // items values - int *weights; // items weights - int *solution; // solution - int *matrix; // solving matrix + bits[bindex(b)] |= (1 << (boffset(b))); +} + +static inline int get_bit(word_t *bits, int b) +{ + return ((bits[bindex(b)] & (1 << (boffset(b)))) >> (boffset(b))); +} + +typedef struct _SolverData { + int v; + word_t *bits; +} SolverData; + +typedef struct _Solver +{ + int k; // capacity + int n; // items # + int *values; // item values + int *weights; // item weights + int nw; // # bytes per bits array + size_t sd_sz; // solver data size + SolverData *data; // solver data +} Solver; + +static void solve(Solver* solver) +{ + int n, k, nw; + size_t sd_sz; + int *values, *weights; int i, j; + int v, w; + char *data_base; + SolverData *c, *p; + + sd_sz = solver->sd_sz; + nw = solver->nw; + n = solver->n; + k = solver->k; + values = solver->values; + weights = solver->weights; + data_base = (char *) solver->data; + + /* SOLVE */ + for (i = 0; i < n; i++) + { + v = values[i]; + w = weights[i]; + c = (SolverData *) (data_base + (sd_sz * k)); + p = (SolverData *) (data_base + (sd_sz * (k - w))); + + for (j = k; j > 0; j--) + { + if (j < w) + break; + if ((j >= w) && (c->v < (v + p->v))) + { + c->v = v + p->v; + memcpy(c->bits, p->bits, (nw * sizeof(word_t))); + set_bit(c->bits, i); + } + c = (SolverData *) (((char *) c) - sd_sz); + p = (SolverData *) (((char *) p) - sd_sz); + } + + if (debug) + { + printf("i=% 4d : ", i); + for (j = 0; j <= k; j++) + { + c = (SolverData *) (data_base + (sd_sz * j)); + printf("% 4d ", c->v); + } + printf("\n"); + } + } +} + +static void print(Solver* solver) +{ + int b; + int i; + int v, w; + SolverData *sol; + + v = 0; + w = 0; + sol = (SolverData *) (((char *) solver->data) + (solver->sd_sz * solver->k)); + + printf("%d %d\n", sol->v, 1); + for (i = 0; i < solver->n; i++) + { + b = get_bit(sol->bits, i); + printf("%d ", b); + if (b) + { + v += solver->values[i]; + w += solver->weights[i]; + } + } + printf("\n"); + + if (v != sol->v) + fprintf(stderr, "ERROR: value %d != %d\n", v, sol->v); + if (w > solver->k) + fprintf(stderr, "ERROR: weight %d > %d\n", w, solver->k); +} + +int main(int argc, char** argv, char** env) +{ + FILE *fp; + Solver solver; // solver + + int i; int *vp, *wp; - int v, w, tmp; + SolverData *data; if(argc < 2) { - fprintf(stderr,"input file missing"); + fprintf(stderr,"input file missing\n"); return EXIT_FAILURE; } - FILE *fp; - - /* printf("%s read %s\n", argv[0], argv[1]); */ + if (debug) printf("%s read %s\n", argv[0], argv[1]); fp = fopen(argv[1], "r"); if (fp == NULL) { @@ -32,151 +145,64 @@ int main(int argc, char** argv, char** env) } /* read k and n */ - if (fscanf(fp, "%d %d\n", &n, &k) != 2) + if (fscanf(fp, "%d %d\n", &solver.n, &solver.k) != 2) { fprintf(stderr, "ERROR: read first line\n"); return EXIT_FAILURE; } - /* printf("k:%d n:%d\n", k, n); */ + if (debug) printf(" K:%d N:%d\n", solver.k, solver.n); /* allocate */ - values = calloc(n, sizeof(int)); - if (!values) + solver.values = calloc(solver.n, sizeof(int)); + if (!solver.values) { fprintf(stderr, "ERROR: values calloc\n"); return EXIT_FAILURE; } - vp = values; + vp = solver.values; - weights = calloc(n, sizeof(int)); - if (!weights) + solver.weights = calloc(solver.n, sizeof(int)); + if (!solver.weights) { - free(values); + free(solver.values); fprintf(stderr, "ERROR: weights calloc\n"); return EXIT_FAILURE; } - wp = weights; + wp = solver.weights; - solution = calloc(n, sizeof(int)); - if (!solution) + solver.nw = (solver.n / WORD_BITS + 1); + solver.sd_sz = sizeof(SolverData) + (solver.nw * sizeof(word_t)); + solver.data= calloc((solver.k + 1), solver.sd_sz); + if (!solver.data) { - free(values); - free(weights); - fprintf(stderr, "ERROR: solution calloc\n"); + free(solver.values); + free(solver.weights); + fprintf(stderr, "ERROR: solver calloc\n"); return EXIT_FAILURE; } - - matrix = calloc(k * n, sizeof(int)); - if (!matrix) + for (i = 0; i <= solver.k; i++) { - free(values); - free(weights); - free(solution); - fprintf(stderr, "ERROR: matrix calloc\n"); - return EXIT_FAILURE; + data = (SolverData *) (((char *) solver.data) + solver.sd_sz * i); + data->bits = (word_t *) (((char *) data) + sizeof(SolverData)); } /* read items */ - for (i = 0; i < n; i++) + for (i = 0; i < solver.n; i++) fscanf(fp, "%d %d\n", vp++, wp++); fclose(fp); - /* for (i = 0; i < n; i++) */ - /* printf("%d -> v:%d w:%d\n", i, values[i], weights[i]); */ - - /* SOLVE matrix is [i][j] */ -#define CURRENT ((i * k) + j) -#define LEFT (((i - 1) * k) + j) -#define UPLEFT (((i - 1) * k) + (j - w)) -#define LAST ((k * n) - 1) - /* first item */ - i = 0; - v = values[i]; - w = weights[i]; - for (j = 0; j < k; j++) // capacities - { - if (w <= (j + 1)) - matrix[CURRENT] = v; - } - /* following items */ - for (i = 1; i < n; i++) // items - { - v = values[i]; - w = weights[i]; - for (j = 0; j < k; j++) // capacities - { - // item weight to much - if (w > j + 1) - { - matrix[CURRENT] = matrix[LEFT]; - } - else - { - /* do not go upper than capacity 0 when moving up left */ - tmp = v + (((j - w) < 0) ? 0 : matrix[UPLEFT]); - if ( tmp > matrix[LEFT]) - matrix[CURRENT] = tmp; - else - matrix[CURRENT] = matrix[LEFT]; - } - } - } - - /* printf("matrix\n"); */ - /* for (j = 0; j < k; j++) */ - /* { */ - /* printf(" %d : ", (j + 1)); */ - /* for (i = 0; i < n; i++) */ - /* { */ - /* printf(" %d", matrix[CURRENT]); */ - /* } */ - /* printf("\n"); */ - /* } */ - - j = k - 1; - for (i = n - 1; i >= 0; i--) - { - w = weights[i]; - tmp = matrix[CURRENT]; - if( (tmp != 0) && ((j - w) >= -1) && ( (i == 0) || (tmp != matrix[LEFT]))) - { - solution[i] = 1; - j -= w; - } - else - solution[i] = 0; - } - - v = 0; - w = 0; - printf ("%d %d\n", matrix[LAST], 0); - for (i = 0; i < n; i++) - { - printf("%d ", solution[i]); - if (solution[i]) { - v += values[i]; - w += weights[i]; - } - } - printf("\n"); - - if (v != matrix[LAST]) + if (debug) { - fprintf(stderr, "ERROR: wrong sum of values %d != %d\n", - v, matrix[LAST]); - return EXIT_FAILURE; + printf(" index value weight\n"); + for (i = 0; i < solver.n; i++) + printf(" % 8d % 8d % 8d\n", i, solver.values[i], solver.weights[i]); } - if (w > k) - { - fprintf(stderr, "ERROR: wrong sum of weights %d > %d\n", w, k); - return EXIT_FAILURE; - } + solve(&solver); + print(&solver); - free(values); - free(weights); - free(solution); - free(matrix); + free(solver.values); + free(solver.weights); return EXIT_SUCCESS; } -- cgit v1.1-2-g2b99