diff options
Diffstat (limited to '01-knapsack')
| -rwxr-xr-x | 01-knapsack/each | 28 | ||||
| -rw-r--r-- | 01-knapsack/ks_dp.c | 182 | ||||
| -rwxr-xr-x | 01-knapsack/solver.py | 49 |
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 |