Optprob/Хранение артефактов на складе

Ссылки сюда (4) →

Задача зарезервирована: Участник:Robohant Robert Safiullin

Представим склад на котором надо хранить какие-то артефакты.

На складе есть m мест хранения, каждое из которых поддерживает определенный вес.

m

15

Максимальный вес для места:

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
15	25	25	30	30	40	40	30	30	25	25	15	15	10	10

Между местами также есть расстояние, и есть (антипожарно-антимагическое) правило, что между любыми двумя занятыми местами хранения, должно быть не меньше 3х метров.

матрица 15×15

	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
1	0	10	2	1	1.5	2.5	3.5	4	5	5.5	6	6.5	7	7.7	7
2	0	0	1.5	2	1.5	3	4	5	2	3	2	3	4	5	5
3	0	0	0	1.5	4	1.5	1.5	4	2	2	2	2	5	3	2
4	0	0	0	0	2	4	4	1.5	4	2	2	1	1	1	1
5	0	0	0	0	0	3	4	2	1	2	2	2	2	3	2.5
6	0	0	0	0	0	0	3.5	2.5	1	2	1	4.6	1	2.7	4
7	0	0	0	0	0	0	0	1	2	1	2.6	1	2.7	1.5	1.5
8	0	0	0	0	0	0	0	0	1	1	3	4	6	3.5	2.5
9	0	0	0	0	0	0	0	0	0	1	2	1	2.6	1	2.7
10	0	0	0	0	0	0	0	0	0	0	1	2	1	1.5	2.5
11	0	0	0	0	0	0	0	0	0	0	0	1	3.4	3.5	2.7
12	0	0	0	0	0	0	0	0	0	0	0	0	4	2.5	1
13	0	0	0	0	0	0	0	0	0	0	0	0	0	2.5	2
14	0	0	0	0	0	0	0	0	0	0	0	0	0	0	3
15	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0

---

Есть n=25 артефактов.

Вес артефактов:

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
12	14	15	16	4	7	5	9	12	15	14	13	12	17	3	5	7	6	3	4	5	5	3	2	2

Некоторые артефакты совместимы — и их можно размещать в одном месте хранения, если суммарный вес не превышен. Некоторые нельзя — таблица совместимости (1=совместимы), представлена ниже.

матрица совместимости 25×25

	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
1	1	1	0	1	0	1	1	1	1	0	0	1	0	0	0	1	0	0	1	0	0	0	0	1	1
2	0	1	1	0	1	0	0	1	1	0	0	0	0	0	0	0	0	1	1	0	0	0	1	0	0
3	0	0	1	0	0	1	1	0	1	1	1	0	1	0	0	1	0	0	0	0	0	0	0	1	0
4	0	0	0	1	0	0	0	1	0	1	1	0	0	0	0	0	0	0	0	0	0	1	1	0	0
5	0	0	0	0	1	1	0	0	1	0	1	0	0	0	1	0	1	0	1	0	0	0	0	0	1
6	0	0	0	0	0	1	0	1	0	0	1	0	1	0	0	0	0	0	0	0	1	0	1	0	0
7	0	0	0	0	0	0	1	0	0	0	0	0	0	1	1	1	0	0	0	0	0	0	0	0	0
8	0	0	0	0	0	0	0	1	0	1	0	1	1	0	0	0	0	0	0	0	0	0	0	1	1
9	0	0	0	0	0	0	0	0	1	1	1	1	0	1	0	0	1	0	1	0	1	0	0	0	0
10	0	0	0	0	0	0	0	0	0	1	0	0	1	1	0	1	0	0	0	0	0	0	0	0	0
11	0	0	0	0	0	0	0	0	0	0	1	1	0	0	0	0	0	0	0	0	1	0	0	0	1
12	0	0	0	0	0	0	0	0	0	0	0	1	0	0	1	0	1	0	1	1	0	0	0	1	0
13	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0	0	0	0	0	0	0	0
14	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0	0	0	0	1	0	1
15	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	1	0	0	1	0	0	0	0	0
16	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0	1	0	0	0	0
17	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0	1	1	0
18	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0	0	0
19	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0	0
20	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	1	0	0
21	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	1	0
22	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0
23	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0
24	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0
25	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1

Не факт, что вообще удастся разместить все артефакты (ну тогда лишние уедут на другие «Хранилища»), но цель — разместить максимум артефактов (в штуках), т.е. каждому артефакту назначить место, или отказать в хранении.

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.