Я пытаюсь попрактиковаться в некоторых проблемах с кодированием, и я столкнулся с этой проблемой:
Поскольку цены на электроэнергию растут, должен быть способ уменьшить потери за счет увеличения использования тяжелых машин, таких как лифты. Сформулируем проблему следующим образом. N человек (p_1, ..., p_N) ожидают в очереди, чтобы попасть в лифт. Кстати, есть только один лифт, и он перемещается между первым этажом и этажом неба (то есть между ними нет других остановок). Также все люди ждут на первом этаже. Просто для простоты нас интересует только использование лифта от земли до неба. Каждый человек p_i имеет положительный вес wi. Грузоподъемность элеватора составляет М . Поэтому не все люди могут быть вместе взятыми. Их несут в нескольких поездках. Каждый человек попадает в лифт в соответствии со своим порядком в очереди. То есть сначала входит p_1 , затем p_2 и так далее. Предположим, что во время поездки t-й в элеватор попадают люди p_j - p_k . Коэффициент отходов ( WF ) поездки t определяется как
Ваша задача - минимизировать общее количество отходов ( TW ), которое определяется как:
Где S - общее количество поездок, необходимых для переноса всех людей с земли на пол неба. Обратите внимание, что WF последней поездки не включен в расчет TW.
Я полностью застрял здесь, я подумал, что это можно решить с помощью DP, но я не знаю как. Особенно с условием поддержания порядка.
Полная проблема может быть найдена здесь Проблема K: Поднимите использование!