From 4caa4c02dbf30f54b3f032cb91a6ce18bd9347b5 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?J=C3=A9r=C3=A9my=20Zurcher?= <jeremy@asynk.ch>
Date: Wed, 3 Jul 2013 22:08:37 +0200
Subject: Discrete : 01-knapsack: start speed seach => ks_dp-ng.c
---
01-knapsack/ks_dp-ng.c | 224 +++++++++++++++++++++++++++++++++++++++++++++++++
01-knapsack/run | 18 ++++
2 files changed, 242 insertions(+)
create mode 100644 01-knapsack/ks_dp-ng.c
create mode 100755 01-knapsack/run
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
--
cgit v1.1-2-g2b99