blob: 81a6d79cdd13d9452eac6d965e86ab7dec1fd6be (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
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)'
|
