Discrete : add 01-knapsack assignment

1 files changed, 58 insertions, 0 deletions

diff --git a/01-knapsack/solver.py b/01-knapsack/solver.py
new file mode 100755
index 0000000..81a6d79
--- /dev/null
+++ b/01-knapsack/solver.py
@@ -0,0 +1,58 @@
+#!/usr/bin/python2.7
+# -*- coding: utf-8 -*-
+
+
+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])
+
+    values = []
+    weights = []
+
+    for i in range(1, items+1):
+        line = lines[i]
+        parts = line.split()
+
+        values.append(int(parts[0]))
+        weights.append(int(parts[1]))
+
+    items = len(values)
+
+    # a trivial greedy algorithm for filling the knapsack
+    # it takes items in-order until the knapsack is full
+    value = 0
+    weight = 0
+    taken = []
+
+    for i in range(0, items):
+        if weight + weights[i] <= capacity:
+            taken.append(1)
+            value += values[i]
+            weight += weights[i]
+        else:
+            taken.append(0)
+
+    # prepare the solution in the specified output format
+    outputData = str(value) + ' ' + str(0) + '\n'
+    outputData += ' '.join(map(str, taken))
+    return outputData
+
+
+import sys
+
+if __name__ == '__main__':
+    if len(sys.argv) > 1:
+        fileLocation = sys.argv[1].strip()
+        inputDataFile = open(fileLocation, 'r')
+        inputData = ''.join(inputDataFile.readlines())
+        inputDataFile.close()
+        print solveIt(inputData)
+    else:
+        print 'This test requires an input file.  Please select one from the data directory. (i.e. python solver.py ./data/ks_4_0)'
+