Автор задачі: | Микола Арзубов |
Задачу підготував: | Павло Цікалишин |
Розбір написав: | Костянтин Денисов |
Поділимо всі ваги на . Тоді у нас є ваги , , , , , а максимальна вага, яку витримує катамаран, — .
Для зручного зберігання кількості людей із кожною вагою можна використовувати масив .
Для розв'язання задачі доцільно використовувати жадібний підхід: спершу розміщувати людей із більшою вагою, намагаючись максимально ефективно заповнювати катамарани.
Для кожної людини з вагою потрібно виділити окремий катамаран. Після цього залишаються люди з вагами , , , .
Людину з вагою можна об'єднати з людиною вагою , якщо такі є. Виділяємо катамарани для груп 4+1, поки є обидва типи людей. Якщо людей вагою не вистачає, групуємо лише . Після цього залишаються люди з вагами , , .
Людину з вагою можна об'єднати або з людиною вагою , або з двома людьми вагою . Вигідніше спершу об'єднувати з , оскільки з двох одиничок можна утворити , але навпаки — ні. Тому формуємо групи 3+2, а коли людей вагою не залишиться, групуємо 3+1+1 (або менше одиничок, якщо їх не вистачає). Після цього залишаються люди з вагами та .
Далі компонування відбувається у такій пріоритетності:
2+2+1 (оскільки дозволяє ефективно використовувати вагу);
2+2 (якщо одиничок немає);
2+1+1+1 (щоб заповнити катамаран повністю);
2+1+1, 2+1, (у міру зменшення можливих комбінацій).
Коли залишаються лише люди з вагою , їх групуємо по п'ятеро в один катамаран. Якщо кількість не ділиться на , додаємо ще один катамаран для решти.
Такий підхід гарантує мінімальну кількість катамаранів для перевезення всієї групи.
Складність алгоритму: (через зчитування).