Решение олимпиадной задачи на Python

September 6, 2018 21:23

Условие: есть 2 платформы грузоподъемностью 200, есть список оборудования.

Формат списка: id, вес, список id несовместимых, полезность.

Задача: распределить на 2 платформы оборудование так, чтобы было больше полезного и в тоже время совместимого оборудования.

coords = [list(map(int, line.split(';'))) for line in open("coords.txt")]

MAX_RELIEF = 10
MAX_LATITUDE = 90
MAX_AREA = max(coords, key=lambda item: item[3])[3]

K_RELIEF = 1    # коэфициенты важности
K_LATITUDE = 0.5
K_AREA = 0.25

def key_func(item):
    relief, latitude, area = item[1], item[2], item[3]

    n_relief = 1 - relief / MAX_RELIEF
    n_latitude = 1 - abs(latitude) / MAX_LATITUDE
    n_area = area / MAX_AREA

    return n_relief * K_RELIEF + n_latitude * K_LATITUDE + n_area * K_AREA

print('\n'.join(list(map(str, sorted(coords, key=key_func, reverse=True)))[:5]))

Входные данные (список):


0;9;35,12,3;26
1;8;7,29,3;1
2;96;22,36,32;39
3;88;10,9,31;76
4;51;14,33,17;66
5;77;4,18,34;30
6;68;16,34,26;10
7;3;23,27,32;96
8;32;1,33,9;60
9;26;39,15,20;18
10;98;33,36,29;51
11;52;14,21,22;8
12;77;3,31,13;85
13;30;4,9,34;35
14;88;22,6,40;97
15;34;12,10,21;65
16;67;24,33,8;58
17;6;6,1,24;55
18;53;7,38,6;91
19;37;38,26,11;69
20;68;14,5,6;94
21;24;12,13,30;19
22;97;36,8,9;35
23;2;3,8,36;8
24;9;16,38,4;89
25;91;1,14,24;40
26;86;31,19,3;55
27;55;9,7,29;47
28;79;37,33,34;53
29;23;6,7,21;54
30;45;11,32,10;2
31;23;26,37,12;24
32;42;16,37,14;94
33;56;19,13,39;23
34;70;31,11,7;33
35;54;23,10,2;34
36;76;37,12,6;60
37;67;16,25,11;57
38;3;14,27,32;72
39;33;37,4,13;90