summaryrefslogtreecommitdiffstats
path: root/01-knapsack
diff options
context:
space:
mode:
authorJérémy Zurcher <jeremy@asynk.ch>2013-08-06 08:15:45 +0200
committerJérémy Zurcher <jeremy@asynk.ch>2013-08-06 08:15:45 +0200
commita2b0bb41876d956ca7abf123858ac45aea3c5898 (patch)
tree63dccf89aa4690c770196b6e49a974ca7837d3df /01-knapsack
parentb14e17eaa3cf971800eec93ca2f1bc5582252a88 (diff)
downloadcoursera-a2b0bb41876d956ca7abf123858ac45aea3c5898.zip
coursera-a2b0bb41876d956ca7abf123858ac45aea3c5898.tar.gz
Discrete : wip-worktree-statedescrete
Diffstat (limited to '01-knapsack')
-rw-r--r--01-knapsack/0-works-only-if-sorted-by-val-or-weight-asc.patch38
-rw-r--r--01-knapsack/1-relaxation-what-to-do-with.patch143
-rwxr-xr-x01-knapsack/ks_dpbin0 -> 8984 bytes
-rw-r--r--01-knapsack/ks_dp-ng.c69
-rw-r--r--01-knapsack/ks_dp2.c436
5 files changed, 686 insertions, 0 deletions
diff --git a/01-knapsack/0-works-only-if-sorted-by-val-or-weight-asc.patch b/01-knapsack/0-works-only-if-sorted-by-val-or-weight-asc.patch
new file mode 100644
index 0000000..bb4a6e1
--- /dev/null
+++ b/01-knapsack/0-works-only-if-sorted-by-val-or-weight-asc.patch
@@ -0,0 +1,38 @@
+diff --git a/01-knapsack/ks_dp-ng.c b/01-knapsack/ks_dp-ng.c
+index 7830651..106328b 100644
+--- a/01-knapsack/ks_dp-ng.c
++++ b/01-knapsack/ks_dp-ng.c
+@@ -120,20 +120,32 @@ static void solve(Solver* solver)
+
+ // this computes the top-left bottom-right diagonal,
+ // values above this don't need to be computed
++ j = k;
+ min_c -= w;
+ lower_bound = (k - min_c);
+ if (lower_bound < w)
+ lower_bound = w;
+- for (j = k; j >= lower_bound; j--, data--, up_left--)
++
++ while (j >= lower_bound)
+ {
+ counter++;
++ /* printf(" % 4d\n", j); */
+
+ if (data->v < (v + up_left->v))
+ {
+ data->i = i;
+ data->v = v + up_left->v;
+ data->w = w + up_left->w;
++ if (j == k) {
++ j -= w;
++ data -= w;
++ up_left -= w;
++ continue;
++ }
+ }
++ j--;
++ data--;
++ up_left--;
+ }
+
+ if (debug > 2)
diff --git a/01-knapsack/1-relaxation-what-to-do-with.patch b/01-knapsack/1-relaxation-what-to-do-with.patch
new file mode 100644
index 0000000..cbc59e3
--- /dev/null
+++ b/01-knapsack/1-relaxation-what-to-do-with.patch
@@ -0,0 +1,143 @@
+diff --git a/01-knapsack/ks_dp-ng.c b/01-knapsack/ks_dp-ng.c
+index 7830651..ddb0d04 100644
+--- a/01-knapsack/ks_dp-ng.c
++++ b/01-knapsack/ks_dp-ng.c
+@@ -7,12 +7,14 @@
+
+ #define NONE -1
+
++enum { RELAX = 0, NO_RELAX };
+ enum { SORT_DESC = 0, SORT_ASC };
+ enum { UNSORTED = 0, SORT_WR, SORT_VR, SORT_RW, SORT_RV};
+
+ static int debug;
+ static int sort;
+ static int sort_order;
++static int relax;
+
+ typedef struct _InputItem
+ {
+@@ -25,6 +27,7 @@ typedef struct _SolverItem {
+ int i; /* index of the selected item */
+ int v; /* cumulated value */
+ int w; /* cumulated weight */
++ float r; /* linear relaxation best value */
+ } SolverItem;
+
+ typedef struct _Solver
+@@ -87,11 +90,39 @@ item_cmp(const void *p1, const void *p2)
+ return 0;
+ }
+
++static inline float relax_item(Solver* solver, SolverItem* data, int start)
++{
++ int w;
++ int i;
++ float relax;
++ const InputItem *item;
++
++ w = data->w;
++ relax= data->v;
++ item = &solver->items[start];
++ for (i = start; i < solver->n; i++, item++)
++ {
++ if ((w + item->w) <= solver->k)
++ {
++ w += item->w;
++ relax += item->v;
++ }
++ else
++ {
++ relax += (item->v * ((solver->k - w) / (float)item->w));
++ break;
++ }
++ }
++
++ return relax;
++}
++
+ static void solve(Solver* solver)
+ {
+ int n, k;
+ int v, w;
+ int i, j;
++ float r;
+ int min_c, lower_bound;
+ const InputItem *item;
+ SolverItem *data;
+@@ -105,7 +136,16 @@ static void solve(Solver* solver)
+
+ if (debug > 2)
+ {
+- printf("\nformat V(i,W)\n");
++ printf("\nformat V(i,W,r)\n");
++ }
++
++ /* RELAXATION */
++ if (relax == RELAX)
++ {
++ data = solver->column;
++ r = relax_item(solver, data, 0);
++ for (j = 0; j <= k; j++, data++)
++ data->r = r;
+ }
+
+ /* SOLVE */
+@@ -134,6 +174,12 @@ static void solve(Solver* solver)
+ data->v = v + up_left->v;
+ data->w = w + up_left->w;
+ }
++
++ /* RELAXTION must be cached */
++ if (relax == RELAX)
++ {
++ data->r = relax_item(solver, data, (i + 1));
++ }
+ }
+
+ if (debug > 2)
+@@ -141,8 +187,8 @@ static void solve(Solver* solver)
+ printf("i=%d; j=k; j<=%d:\n", i, lower_bound);
+ data = solver->column;
+ for (j = 0; j <= k; j++, data++)
+- printf(" %d : % 4d(% 2d % 2d)\n",
+- j, data->v, data->i, data->w);
++ printf(" %d : % 4d(% 2d % 2d %.1f)\n",
++ j, data->v, data->i, data->w, data->r);
+ printf("\n");
+ }
+ }
+@@ -152,8 +198,8 @@ static void solve(Solver* solver)
+ 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);
++ printf(" % 4d(% 2d % 2d %.1f)\n",
++ data->v, data->i, data->w, data->r);
+ }
+
+ if (debug > 0)
+@@ -194,10 +240,11 @@ int main(int argc, char** argv, char** env)
+ InputItem *item;
+
+ debug = 0;
++ relax = NO_RELAX;
+ sort = UNSORTED;
+ sort_order = SORT_DESC;
+ excpected_value = NONE;
+- while ((opt = getopt(argc, argv, "d:e:s:S")) != -1) {
++ while ((opt = getopt(argc, argv, "d:e:s:SR")) != -1) {
+ switch (opt) {
+ case 'd':
+ debug = atoi(optarg);
+@@ -211,6 +258,9 @@ int main(int argc, char** argv, char** env)
+ case 'S':
+ sort_order = SORT_ASC;
+ break;
++ case 'R':
++ relax = RELAX;
++ break;
+ default: /* '?' */
+ fprintf(stderr, "Usage: %s [falgs] input\n",
+ argv[0]);
diff --git a/01-knapsack/ks_dp b/01-knapsack/ks_dp
new file mode 100755
index 0000000..0267f00
--- /dev/null
+++ b/01-knapsack/ks_dp
Binary files differ
diff --git a/01-knapsack/ks_dp-ng.c b/01-knapsack/ks_dp-ng.c
index 7830651..282cecf 100644
--- a/01-knapsack/ks_dp-ng.c
+++ b/01-knapsack/ks_dp-ng.c
@@ -160,6 +160,75 @@ static void solve(Solver* solver)
printf("loops count: %u\n", counter);
}
+static void reset_output(char *output, int bits)
+{
+ char *ch;
+ char *end;
+
+ end = output + bits;
+ for (ch = output; ch < end; )
+ {
+ (*ch++) = '0';
+ (*ch++) = ' ';
+ }
+ ch--;
+ *ch = '\0';
+}
+
+static int print(Solver* solver)
+{
+ int ret;
+ int v, w;
+ char *output;
+ const Item *item;
+ const SolverData *data;
+
+ output = calloc((solver->n * 2), sizeof(char));
+ if (!output)
+ {
+ fprintf(stderr, "ERROR: output calloc\n");
+ return EXIT_FAILURE;
+ }
+ reset_output(output, (solver->n * 2));
+
+ data = solver->column + solver->k;
+ printf("%d %d\n", data->v, 0);
+
+ v = 0;
+ w = 0;
+ /* for (data = solver->column + solver->k; data->i != -1 ; data -= item->w) */
+ for (data = solver->column + solver->k; data->s != -1 ; data -= item->w)
+ {
+ /* item = &solver->items[data->i]; */
+ item = &solver->items[data->s];
+ output[(item->i) * 2] = '1';
+ if (debug > 1)
+ printf(" from % 6d - take % 4d (% 4d % 4d)\n",
+ data->v, item->i, item->v, item->w);
+ v += item->v;
+ w += item->w;
+ }
+ printf("%s\n", output);
+
+ free(output);
+
+ ret = EXIT_SUCCESS;
+ data = solver->column + solver->k;
+ if (v != data->v)
+ {
+ fprintf(stderr, "ERROR: value %d != %d\n", v, data->v);
+ ret = EXIT_FAILURE;
+ }
+ if (w > solver->k)
+ {
+ fprintf(stderr, "ERROR: weight %d > %d\n", w, solver->k);
+ ret = EXIT_FAILURE;
+ }
+
+ return ret;
+
+}
+
static int check(Solver *solver, int excpected_value)
{
const SolverItem *data;
diff --git a/01-knapsack/ks_dp2.c b/01-knapsack/ks_dp2.c
new file mode 100644
index 0000000..a776f24
--- /dev/null
+++ b/01-knapsack/ks_dp2.c
@@ -0,0 +1,436 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <stdint.h>
+#include <time.h>
+#include <unistd.h>
+
+enum { UNSORTED = 0, SORT_WR, SORT_VR, SORT_RW, SORT_RV};
+enum { DESC = 0, ASC };
+enum { NO_RELAX = 0, RELAX };
+
+static int debug;
+static int sort;
+static int sort_order;
+static int relax;
+
+typedef struct _Item
+{
+ int i;
+ int v;
+ int w;
+} Item;
+
+typedef struct _SolverData {
+ int v; /* cumulated value */
+ int w; /* cumulated weight */
+ float r; /* relaxed max value */
+ int i; /* index of the selected item */
+} SolverData;
+
+typedef struct _Solver
+{
+ int k; /* capacity */
+ int n; /* items # */
+ int sum_w; /* sum of weight of all items */
+ Item *items; /* items */
+ SolverData *column; /* solver column */
+} Solver;
+
+static int
+item_cmp(const void *p1, const void *p2)
+{
+ int ret;
+ float r1, r2;
+ const Item *i1, *i2;
+
+ i1 = (const Item *) p1;
+ i2 = (const Item *) p2;
+
+ ret = ((sort_order == ASC) ? 1 : -1);
+
+ if (sort == SORT_WR)
+ {
+ if (i1->w > i2->w) return ret;
+ if (i1->w < i2->w) return -ret;
+ }
+ else if (sort == SORT_VR)
+ {
+ if (i1->v > i2->v) return ret;
+ if (i1->v < i2->v) return -ret;
+ }
+ else // SORT_RW | SORT_RV
+ {
+ r1 = i1->v / (float)i1->w;
+ r2 = i2->v / (float)i2->w;
+ if (r1 > r2) return ret;
+ if (r1 < r2) return -ret;
+ }
+
+ if (sort == SORT_RW)
+ {
+ if (i1->w > i2->w) return ret;
+ if (i1->w < i2->w) return -ret;
+ }
+ else if (sort == SORT_RV)
+ {
+ if (i1->v > i2->v) return ret;
+ if (i1->v < i2->v) return -ret;
+ }
+ else // SORT_WR | SORT_VR
+ {
+ r1 = i1->v / (float)i1->w;
+ r2 = i2->v / (float)i2->w;
+ if (r1 > r2) return ret;
+ if (r1 < r2) return -ret;
+ }
+
+ return 0;
+}
+
+static void reset_output(char *output, int bits)
+{
+ char *ch;
+ char *end;
+
+ end = output + bits;
+ for (ch = output; ch < end; )
+ {
+ (*ch++) = '0';
+ (*ch++) = ' ';
+ }
+ ch--;
+ *ch = '\0';
+}
+
+static int print(Solver* solver)
+{
+ int ret;
+ int v, w;
+ char *output;
+ const Item *item;
+ const SolverData *data;
+
+ output = calloc((solver->n * 2), sizeof(char));
+ if (!output)
+ {
+ fprintf(stderr, "ERROR: output calloc\n");
+ return EXIT_FAILURE;
+ }
+ reset_output(output, (solver->n * 2));
+
+ data = solver->column + solver->k;
+ printf("%d %d\n", data->v, 0);
+
+ v = 0;
+ w = 0;
+ for (data = solver->column + solver->k; data->i != -1 ; data -= item->w)
+ {
+ item = &solver->items[data->i];
+ output[(item->i) * 2] = '1';
+ if (debug > 1)
+ printf(" from % 6d - take % 4d (% 4d % 4d)\n",
+ data->v, item->i, item->v, item->w);
+ v += item->v;
+ w += item->w;
+ }
+ printf("%s\n", output);
+
+ free(output);
+
+ ret = EXIT_SUCCESS;
+ data = solver->column + solver->k;
+ if (v != data->v)
+ {
+ fprintf(stderr, "ERROR: value %d != %d\n", v, data->v);
+ ret = EXIT_FAILURE;
+ }
+ if (w > solver->k)
+ {
+ fprintf(stderr, "ERROR: weight %d > %d\n", w, solver->k);
+ ret = EXIT_FAILURE;
+ }
+
+ return ret;
+
+}
+
+static inline void relax_item(Solver* solver, SolverData* data, int start)
+{
+ int w;
+ int i;
+ const Item *item;
+
+ w = data->w;
+ data->r = data->v;
+ item = &solver->items[start];
+ for (i = start; i < solver->n; i++, item++)
+ {
+ if ((w + item->w) <= solver->k)
+ {
+ w += item->w;
+ data->r += item->v;
+ }
+ else
+ {
+ data->r += (item->v * ((solver->k - w) / (float)item->w));
+ break;
+ }
+ }
+}
+
+static void solve(Solver* solver)
+{
+ int n, k;
+ int v, w;
+ int i, j;
+ int max_c, upper_bound;
+ const Item *item;
+ SolverData *data;
+ const SolverData *up_left;
+
+ unsigned int counter;
+
+ n = solver->n;
+ k = solver->k;
+ max_c = solver->sum_w;
+
+ /* RELAXATION */
+ if (relax == RELAX)
+ {
+ data = solver->column;
+ for (j = 0; j <= k; j++, data++)
+ relax_item(solver, data, 0);
+ }
+
+ 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);
+
+ // this computes the top-left bottom-right diagonal,
+ // values above this don't need to be computed
+ max_c -= w;
+ upper_bound = (((k - max_c) > w) ? (k - max_c) : w );
+ for (j = k; j >= upper_bound; j--, data--, up_left--)
+ {
+ // FIXME
+ /* if ((relax == RELAX) && (data->v == (int)data->r)) */
+ /* if ((relax == RELAX) && (data->v <= (int)data->r)) */
+ /* if ((relax == RELAX) && (data->v < (int)data->r)) */
+ /* { */
+ /* /1* fprintf(stderr,"RELAX\n"); *1/ */
+ /* continue; */
+ /* } */
+
+ counter++;
+
+ if (data->v < (v + up_left->v))
+ {
+ data->i = i;
+ data->v = v + up_left->v;
+ data->w = w + up_left->w;
+ /* if (j == k) */
+ /* { */
+ /* for (critical = data; critical->i != -1 ; */
+ /* critical -= solver->items[data->i].w) */
+ /* { */
+ /* critical->c = critical->i; */
+ /* } */
+ /* print_vector(solver, i + 1, 0); */
+ /* print_vector(solver, i + 1, 1); */
+ /* } */
+ }
+
+ /* RELAXTION must be cached */
+ if (relax == RELAX)
+ {
+ relax_item(solver, data, (i + 1));
+ }
+ }
+
+ if (debug > 2)
+ {
+ printf("i=%d; j=k; j<=%d:\n", i, upper_bound);
+ data = solver->column;
+ for (j = 0; j <= k; j++, data++)
+ printf(" % 4d(% 2d % 2d %.1f)\n",
+ data->v, data->i, data->w, data->r);
+ printf("\n");
+ }
+ }
+
+ if (debug > 0)
+ printf("loops count: %u\n", counter);
+
+ if (debug == 2)
+ {
+ printf("i=%d:\n", solver->n - 1);
+ data = solver->column;
+ for (j = 0; j <= k; j++, data++)
+ printf(" % 4d(% 2d % 2d %.1f)\n",
+ data->v, data->i, data->w, data->r);
+ }
+}
+
+int main(int argc, char** argv, char** env)
+{
+ FILE *fp;
+
+ int opt;
+ int ret;
+ int i;
+ uint64_t dt;
+ struct timespec t0;
+ struct timespec t1;
+
+ Solver solver;
+ Item *item;
+
+ sort = UNSORTED;
+ sort_order = DESC;
+ relax = NO_RELAX;
+ debug = 0;
+ while ((opt = getopt(argc, argv, "d:s:SR")) != -1) {
+ switch (opt) {
+ case 's':
+ sort = atoi(optarg);
+ break;
+ case 'd':
+ debug = atoi(optarg);
+ break;
+ case 'S':
+ sort_order = ASC;
+ break;
+ case 'R':
+ relax = RELAX;
+ break;
+ default: /* '?' */
+ fprintf(stderr, "Usage: %s [-d level] [-s 0|1] [-S] [-R]input\n",
+ argv[0]);
+ return EXIT_FAILURE;
+ }
+ }
+
+ if (sort > SORT_RV) sort = UNSORTED;
+ if (sort_order > ASC) sort = DESC;
+
+ 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(Item));
+ if (!solver.items)
+ {
+ fprintf(stderr, "ERROR: items calloc\n");
+ return EXIT_FAILURE;
+ }
+
+ solver.column = calloc((solver.k + 1), sizeof(SolverData));
+ 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 = -1;
+
+ /* read items */
+ solver.sum_w = 0;
+ item = solver.items;
+ for (i = 0; i < solver.n; i++, item++)
+ {
+ item->i = i;
+ fscanf(fp, "%d %d\n", &item->v, &item->w);
+ solver.sum_w += item->w;
+ }
+ fclose(fp);
+
+ if (sort != UNSORTED)
+ qsort(solver.items, solver.n, sizeof(Item), item_cmp);
+
+ if (debug > 1)
+ {
+ printf(" Items ");
+ if (sort == UNSORTED)
+ {
+ printf("unsorted\n");
+ }
+ else
+ {
+ printf("sorted ");
+ switch(sort){
+ case SORT_VR:
+ printf("Value,ratio(V/W)");
+ break;
+ case SORT_WR:
+ printf("Weight,ratio(V/W)");
+ break;
+ case SORT_RW:
+ printf("ratio(V/W),Weight");
+ break;
+ case SORT_RV:
+ printf("ratio(V/W),Value");
+ break;
+ default:
+ break;
+ }
+ if (sort_order == ASC)
+ printf(" asc\n");
+ else
+ printf(" desc\n");
+ }
+ 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 = print(&solver);
+
+ 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;
+}
+