Author: Satori
Posted: 2017-05-01 18:42:56
Category:
solution
test
Views: 671
Comments: 0
```
from copy import deepcopy
N = 5
time_consuming = [
[10, 8, 20, 4, 8],
[4, 10, 6, 12, 5],
[22, 13, 4, 10, 8],
[2, 16, 25, 8, 2],
[6, 8, 13, 11, 16],
]
resource_consuming = [
[
[2, 0, 2, 1, 0],
[0, 1, 0, 2, 5],
[1, 0, 2, 0, 0],
[0, 0, 0, 3, 5],
[0, 2, 0, 0, 2],
],
[
[0, 2, 1, 0, 0],
[2, 0, 2, 0, 0],
[1, 0, 0, 2, 5],
[0, 1, 0, 0, 2],
[0, 0, 0, 3, 0],
],
[
[1, 0, 0, 0, 0],
[2, 2, 0, 0, 0],
[0, 0, 2, 3, 0],
[0, 0, 0, 1, 4],
[1, 0, 0, 1, 3],
],
[
[0, 0, 0, 1, 2],
[2, 3, 0, 0, 0],
[1, 0, 2, 0, 0],
[0, 2, 0, 3, 0],
[0, 3, 0, 0, 6],
],
[
[0, 1, 0, 0, 2],
[0, 0, 0, 4, 0],
[0, 0, 0, 0, 3],
[2, 0, 3, 1, 0],
[1, 3, 0, 0, 0],
],
]
resource = [3, 4, 3, 4, 6]
dependency = [
[None, None, None, None, None],
[[0], [0], [0], [0], None],
[None, [1], [0], None, [0]],
[[2], [1], [1, 2], [1, 2], [1]],
[1, 3], [2, 3], [3], [3], [2, 3],
]
all_task_queues = []
def get_resouce_consume(queue):
consume = [0 for x in range(N)]
for ind, queue_id in enumerate(queue):
consume_table = resource_consuming[ind]
for task in queue_id:
consume_column = consume_table[task]
for con_ind, con in enumerate(consume_column):
consume[con_ind] += con
return consume
def get_time_consume(queue):
time_consume = [0 for x in range(N)]
for ind, queue_id in enumerate(queue):
for task in queue_id:
con = time_consuming[ind][task]
time_consume[ind] += con
return max(time_consume)
def judge_exceed_resource(queue_id):
for ind, x in enumerate(get_resouce_consume(queue_id)):
if x > resource[ind]:
return False
return True
def judge_timing(queue_id):
def get_all_task_queues(cur_task_id, queue):
# all tasks are assigned, return the result
if cur_task_id == N:
all_task_queues.append(deepcopy(queue))
else:
for queue_id in queue:
queue_id.append(cur_task_id)
get_all_task_queues(cur_task_id + 1, queue)
queue_id.pop()
def clean_all_task_queues():
global all_task_queues
all_task_queues = list(filter(judge_exceed_resource, all_task_queues))
# format: [queue, time]
def get_min_time_queue():
min_queue = min(all_task_queues, key=lambda x: get_time_consume(x))
return [min_queue, get_time_consume(min_queue)]
if __name__ == "__main__":
queue = [[] for d in range(N)]
get_all_task_queues(0, queue)
clean_all_task_queues()
for ind, task_queue in enumerate(all_task_queues):
print(ind, task_queue)
print(get_min_time_queue())
```
Read More
