Stack Overflow на русском Asked by MysNikita on August 26, 2020
В общем, в одной книжке нашёл задачу, но там даётся не совсем эффективное относительно моего решение.
Условие: есть N людей, их веса содержатся в массиве weight. Есть грузоподъёмность лифта X. Необходимо найти минимальное количество поездок, необходимое для перевозки всех людей.
Моё решение: расположим все веса в порядке убывания (это не будет узким местом алгоритма), и составим очередь. Далее будем прогонять эту очередь от начала до конца следующим образом. Сначала в лифт идёт самый тяжёлый (первый), затем если первый человек в очереди вмещается, то мы помещаем его в лифт и проверяем очередь дальше, в противном случае отправляем его в конец очереди. Когда очередь полностью проверена, лифт отправляется и всё сначала. То есть лифт каждый раз заполняется по максимуму. Можно ли подобрать пример, когда этот способ не сработает?
Нет, жадный алгоритм не всегда будет приводить к оптимальному решению.
Контрпример:
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
Get help from others!
Recent Questions
Recent Answers
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP