1 files changed, 182 insertions, 0 deletions
diff --git a/01-knapsack/ks_dp.c b/01-knapsack/ks_dp.c
new file mode 100644
index 0000000..25e92cb
--- /dev/null
+++ b/01-knapsack/ks_dp.c
@@ -0,0 +1,182 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <limits.h>
+
+int main(int argc, char** argv, char** env)
+{
+   int k;         // capacity
+   int n;         // items #
+   int *values;   // items values
+   int *weights;  // items weights
+   int *solution; // solution
+   int *matrix;   // solving matrix
+
+   int i, j;
+   int *vp, *wp;
+   int v, w, tmp;
+
+   if(argc < 2)
+     {
+        fprintf(stderr,"input file missing");
+        return EXIT_FAILURE;
+     }
+
+   FILE *fp;
+
+   /* printf("%s read %s\n", argv[0], argv[1]); */
+   fp = fopen(argv[1], "r");
+   if (fp == NULL)
+     {
+        fprintf(stderr, "I couldn't open results.dat for reading.\n");
+        exit(EXIT_FAILURE);
+     }
+
+   /* read k and n */
+   if (fscanf(fp, "%d %d\n", &n, &k) != 2)
+     {
+        fprintf(stderr, "ERROR: read first line\n");
+        return EXIT_FAILURE;
+     }
+   /* printf("k:%d n:%d\n", k, n); */
+
+   /* allocate */
+   values = calloc(n, sizeof(int));
+   if (!values)
+     {
+        fprintf(stderr, "ERROR: values calloc\n");
+        return EXIT_FAILURE;
+     }
+   vp = values;
+
+   weights = calloc(n, sizeof(int));
+   if (!weights)
+     {
+        free(values);
+        fprintf(stderr, "ERROR: weights calloc\n");
+        return EXIT_FAILURE;
+     }
+   wp = weights;
+
+   solution = calloc(n, sizeof(int));
+   if (!solution)
+     {
+        free(values);
+        free(weights);
+        fprintf(stderr, "ERROR: solution calloc\n");
+        return EXIT_FAILURE;
+     }
+
+   matrix = calloc(k * n, sizeof(int));
+   if (!matrix)
+     {
+        free(values);
+        free(weights);
+        free(solution);
+        fprintf(stderr, "ERROR: matrix calloc\n");
+        return EXIT_FAILURE;
+     }
+
+   /* read items */
+   for (i = 0; i < 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])
+     {
+        fprintf(stderr, "ERROR: wrong sum of values %d != %d\n",
+                v, matrix[LAST]);
+        return EXIT_FAILURE;
+     }
+
+   if (w > k)
+     {
+        fprintf(stderr, "ERROR: wrong sum of weights %d > %d\n", w, k);
+        return EXIT_FAILURE;
+     }
+
+   free(values);
+   free(weights);
+   free(solution);
+   free(matrix);
+
+   return EXIT_SUCCESS;
+}