Discrete : 01-knapsack: dynamic programming solver + malloc error when to many values

3 files changed, 226 insertions, 33 deletions

diff --git a/01-knapsack/each b/01-knapsack/each
new file mode 100755
index 0000000..ba6940a
--- /dev/null
+++ b/01-knapsack/each
@@ -0,0 +1,28 @@
+#! /bin/bash
+
+BIN=${BIN:-ks_dp}
+${CC:-clang} -O2 -pedantic -Wall -o $BIN $BIN.c || exit 1
+
+DATA="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
+"
+for I in $DATA; do
+   echo " *** $I $@"
+   ./$BIN ./data/$I $@
+done
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;
+}
diff --git a/01-knapsack/solver.py b/01-knapsack/solver.py
index 81a6d79..ffb1852 100755
--- a/01-knapsack/solver.py
+++ b/01-knapsack/solver.py
@@ -1,47 +1,30 @@
-#!/usr/bin/python2.7
+#!/usr/bin/python2
 # -*- coding: utf-8 -*-
 
+import os
+from subprocess import Popen, PIPE
 
-def solveIt(inputData):
-    # Modify this code to run your optimization algorithm
-
-    # parse the input
-    lines = inputData.split('\n')
 
-    firstLine = lines[0].split()
-    items = int(firstLine[0])
-    capacity = int(firstLine[1])
+def solveIt(inputData):
 
-    values = []
-    weights = []
+    # Writes the inputData to a temporay file
 
-    for i in range(1, items+1):
-        line = lines[i]
-        parts = line.split()
+    tmpFileName = 'tmp.data'
+    tmpFile = open(tmpFileName, 'w')
+    tmpFile.write(inputData)
+    tmpFile.close()
 
-        values.append(int(parts[0]))
-        weights.append(int(parts[1]))
+    # Runs the command: java Solver -file=tmp.data
 
-    items = len(values)
+    process = Popen(['./ks_dp', tmpFileName],
+                    stdout=PIPE)
+    (stdout, stderr) = process.communicate()
 
-    # a trivial greedy algorithm for filling the knapsack
-    # it takes items in-order until the knapsack is full
-    value = 0
-    weight = 0
-    taken = []
+    # removes the temporay file
 
-    for i in range(0, items):
-        if weight + weights[i] <= capacity:
-            taken.append(1)
-            value += values[i]
-            weight += weights[i]
-        else:
-            taken.append(0)
+    os.remove(tmpFileName)
 
-    # prepare the solution in the specified output format
-    outputData = str(value) + ' ' + str(0) + '\n'
-    outputData += ' '.join(map(str, taken))
-    return outputData
+    return stdout.strip()
 
 
 import sys