-
Notifications
You must be signed in to change notification settings - Fork 0
/
solver4_ordenado.py
147 lines (126 loc) · 5.13 KB
/
solver4_ordenado.py
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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
#!/usr/bin/python
# -*- coding: utf-8 -*-
from collections import namedtuple
from operator import itemgetter
from timeit import default_timer as timer
Item = namedtuple("Item", ['index', 'value', 'weight'])
max_estimate = 0
max_value = 0
max_node = None
items = []
def solve_it(input_data):
# Modify this code to run your optimization algorithm
class Node:
def __init__(self, value, room, estimate, parent, item, items_taken):
global max_value
global max_node
if max_value <= value:
max_value = value
max_node = self
self.value = value
self.room = room
self.estimate = estimate
self.treated = False
self.parent = parent
self.estimate_items_taken = items_taken
self.next_items_taken = None
if item is not None:
self.index_item = parent.index_item + 1
else:
self.index_item = -1
def expand(self, item, lista):
global items
if max_value < self.estimate:
if not self.treated:
#print("IZQ")
if self.room-item[0].weight >= 0:
lista.insert(0, Node(self.value + item[0].value, self.room - item[0].weight, self.estimate, self, items[self.index_item+1], self.estimate_items_taken))
self.treated = True
else:
#print("DER")
self.next_items_taken = self.estimate_items_taken[:]
self.next_items_taken[item[0].index]= 0
#print("[")
#for d in self.next_items_taken:
# print(str(d) + ", ")
lista.pop(0)
estimate = self.calculate_estimate() #self.estimate - items[self.index_item][1]
#estimate = self.calculate_estimate_old(item[0]) #self.estimate - items[self.index_item][1]
lista.insert(0, Node(self.value, self.room, estimate , self, items[self.index_item+1], self.next_items_taken))
else:
lista.pop(0);
def calculate_estimate_old(self, item):
return self.estimate - item.value
def calculate_estimate(self):
initial_estimated = 0
weight_take = 0
for i in items:
if not self.next_items_taken[i[0].index] == 0:
weight_take += i[0].weight
if weight_take > capacity:
initial_estimated += (i[0].weight-(weight_take-capacity))*i[0].value/i[0].weight
break
initial_estimated += i[0].value
#else:
#print("Index: " + str(i[0].index))
#print("Estimado: " + str(initial_estimated))
return initial_estimated
# parse the input
lines = input_data.split('\n')
first_line = lines[0].split()
item_count = int(first_line[0])
capacity = int(first_line[1])
#items_org = []
for i in range(1, item_count + 1):
line = lines[i]
parts = line.split()
items.append((Item(i - 1, int(parts[0]), int(parts[1])), int(parts[0])/int(parts[1])))
#items_org.append(Item(i - 1, int(parts[0]), int(parts[1])))
items.sort(key=itemgetter(1), reverse=True)
initial_estimate = 0
weight_taken = 0
for i in items:
weight_taken += i[0].weight
if weight_taken > capacity:
initial_estimate += (i[0].weight-(weight_taken-capacity))*i[0].value/i[0].weight
break
initial_estimate += i[0].value
taken = [0] * len(items)
items_taken = [1] * len(items)
#a = 0
#for i in items:
# a += i[0].value
#initial_estimate = a
node_list = [Node(0, capacity, initial_estimate, None, None, items_taken)]
prev = timer()
prev2 = timer()
while len(node_list) > 0:
#print("----")
#print(node_list[0].value)
#print(node_list[0].room)
#print(node_list[0].estimate)
if(timer()-prev2 > 5):
print("Tiempo transcurrido: " + str(timer()-prev) + " ---- Valor: " + str(max_value))
prev2 = timer()
if node_list[0].index_item+1 < len(items):
node_list[0].expand(items[node_list[0].index_item+1], node_list)
else:
# print("fin hoja")
node_list.pop(0)
#print("----")
print("Tiempo (s): " + str(timer()-prev))
# prepare the solution in the specified output format
output_data = str(max_value) + '\n'
output_data += ' '.join(map(str, max_node.estimate_items_taken))
#output_data += ' '.join(map(str, max_node.estimate_items_taken))
return output_data
if __name__ == '__main__':
import sys
if len(sys.argv) > 1:
file_location = sys.argv[1].strip()
with open(file_location, 'r') as input_data_file:
input_data = input_data_file.read()
print(solve_it(input_data))
else:
print(
'This test requires an input file. Please select one from the data directory. (i.e. python solver.py ./data/ks_4_0)')