TransWikia.com

Является ли решение задачи верным?

Stack Overflow на русском Asked by MysNikita on August 26, 2020

В общем, в одной книжке нашёл задачу, но там даётся не совсем эффективное относительно моего решение.

Условие: есть N людей, их веса содержатся в массиве weight. Есть грузоподъёмность лифта X. Необходимо найти минимальное количество поездок, необходимое для перевозки всех людей.

Моё решение: расположим все веса в порядке убывания (это не будет узким местом алгоритма), и составим очередь. Далее будем прогонять эту очередь от начала до конца следующим образом. Сначала в лифт идёт самый тяжёлый (первый), затем если первый человек в очереди вмещается, то мы помещаем его в лифт и проверяем очередь дальше, в противном случае отправляем его в конец очереди. Когда очередь полностью проверена, лифт отправляется и всё сначала. То есть лифт каждый раз заполняется по максимуму. Можно ли подобрать пример, когда этот способ не сработает?

One Answer

Нет, жадный алгоритм не всегда будет приводить к оптимальному решению.

Контрпример:
X = 9
N = 6
weight = {5, 3, 3, 3, 2, 2}

Ваше решение: {5, 3}, {3, 3, 2}, {2} — три поездки.
Оптимальное решение: {5, 2, 2}, {3, 3, 3} — две поездки.

Correct answer by default locale on August 26, 2020

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP