Optprob/Группировка людей — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
StasFomin (обсуждение | вклад) |
||
| Строка 93: | Строка 93: | ||
<!-- Целью распределения людей по группам является максимизация числа людей, которых они знают в своей группе.--> | <!-- Целью распределения людей по группам является максимизация числа людей, которых они знают в своей группе.--> | ||
| − | {{optsolv| | + | {{optsolv|Группировка_людей}} |
{{vim|778246197}} | {{vim|778246197}} | ||
* [[Blog:Advanced_Algorithms/Разбор_оптимизационной_задачи_«Группировка_людей»]] | * [[Blog:Advanced_Algorithms/Разбор_оптимизационной_задачи_«Группировка_людей»]] | ||
Текущая версия на 01:30, 6 октября 2024
Проверено: StasFomin 22:40, 19 февраля 2023 (UTC)
Пусть имеется группа из n=50 человек, с которыми будет создано m=10 рабочих групп.
Каждая группа будет состоять из фиксированного числа людей.
1 2 3 4 5 6 7 8 9 10 5 4 4 3 6 4 5 7 6 6
Некоторые люди знают друг друга.
70 связей
| Known | |
|---|---|
| Person1 | Person2 |
| 1 | 2 |
| 1 | 3 |
| 1 | 4 |
| 2 | 6 |
| 2 | 8 |
| 3 | 6 |
| 4 | 6 |
| 4 | 7 |
| 4 | 23 |
| 4 | 27 |
| 4 | 30 |
| 5 | 10 |
| 5 | 15 |
| 5 | 20 |
| 6 | 18 |
| 7 | 40 |
| 7 | 45 |
| 7 | 48 |
| 8 | 10 |
| 8 | 12 |
| 8 | 26 |
| 8 | 28 |
| 9 | 19 |
| 9 | 20 |
| 10 | 11 |
| 10 | 35 |
| 10 | 45 |
| 11 | 21 |
| 11 | 29 |
| 12 | 41 |
| 12 | 42 |
| 13 | 46 |
| 14 | 47 |
| 14 | 49 |
| 14 | 50 |
| 15 | 30 |
| 15 | 32 |
| 16 | 38 |
| 16 | 45 |
| 17 | 23 |
| 17 | 24 |
| 18 | 29 |
| 19 | 39 |
| 21 | 30 |
| 22 | 40 |
| 22 | 41 |
| 23 | 43 |
| 24 | 34 |
| 24 | 36 |
| 25 | 37 |
| 26 | 39 |
| 27 | 40 |
| 28 | 41 |
| 29 | 41 |
| 30 | 42 |
| 31 | 32 |
| 32 | 34 |
| 33 | 35 |
| 34 | 38 |
| 35 | 39 |
| 36 | 41 |
| 37 | 44 |
| 38 | 44 |
| 39 | 45 |
| 40 | 41 |
| 40 | 42 |
| 41 | 46 |
| 42 | 47 |
| 43 | 48 |
Надо так распределить людей по группам (возможно будут лишние, это нормально), чтобы максимизировать число людей, которые всех знают в своей группе.