Условие:
Один из главных недостатков ровера-доставщика — ограниченный по объёму отсек, в котором иногда чуть-чуть не хватает места. Экспериментальная модель ровера обладает эластичным отсеком для перевозки заказов.
Базовый объём отсека составляет
S
S литров. Пока отсек не заполнен, товары в нём не испытывают дополнительного давления. Однако, поскольку отсек эластичный, в него можно положить дополнительные товары сверх базового объёма. Если объём положенных в отсек товаров
U
U превышает
S
S, то все товары в отсеке будут испытывать давление
P
=
U
−
S
P=U−S.
Каждый товар обладает тремя характеристиками: объёмом
v
i
v
i
, стоимостью
c
i
c
i
и давлением, которое он выдерживает
p
i
p
i
.
Всего необходимо доставить
N
N товаров, однако в первую поездку ровера необходимо отправить товары с максимальной суммарной стоимостью — это обрадует заказчика. Определите максимальную стоимость товаров, которые можно разместить в ровере так, чтобы все они выдерживали давление.
Формат ввода
В первой строке находятся два целых числа
N
N (
1
≤
N
≤
100
1≤N≤100) и
S
S (
0
≤
S
≤
1
0
9
0≤S≤10
9
) — количество товаров.
Следующие
N
N строк содержат описание очередного товара
v
i
v
i
,
c
i
c
i
и
p
i
p
i
(
1
≤
v
i
≤
1000
1≤v
i
≤1000,
0
≤
c
i
≤
1
0
6
0≤c
i
≤10
6
,
0
≤
p
i
≤
1
0
9
0≤p
i
≤10
9
) — объём и стоимость товара, а также максимальное давление, которое он выдерживает.
Формат вывода
В первой строке выведите число товаров
K
K, которые необходимо разместить в отсеке ровера, и их максимальную суммарную стоимость.
Во второй строке выведите
K
K чисел — номера товаров, которые нужно разместить в отсеке ровера. Товары нумеруются с единицы в том порядке, в котором они даны во входном файле.
Если существует несколько вариантов ответа, выведите любой из них.
Решение:
Для решения данной задачи мы можем использовать метод динамического программирования, аналогичный решению задачи о рюкзаке. Мы будем учитывать как объем товаров, так и давление, которое они могут выдерживать.
Шаг 1: Ввод данных
Сначала мы считываем количество товаров N и базовый объем отсека S. Затем мы считываем характеристики каждого товара: объем vi, стоимость ci и максимальное давление pi.Шаг 2: Подготовка данных
Создадим массивы для хранения объемов, стоимостей и давлений товаров. Также создадим массив для хранения индексов товаров.Шаг 3: Динамическое программирование
Мы будем использовать двумерный массив dp, где dp[j][k] будет хранить максимальную стоимость товаров, которые можно разместить в отсеке с объемом j и давлением k.1. Инициализируем массив dp нулями.
2. Для каждого товара проверяем, можем ли мы его добавить в отсек, учитывая его объем и давление.
3. Если добавление товара не превышает максимальное давление, обновляем значение в массиве dp.
Шаг 4: Восстановление решения
После заполнения массива dp мы можем восстановить, какие товары были выбраны для достижения максимальной стоимости. Мы будем отслеживать, какие товары были добавлены, начиная с максимальной стоимости и двигаясь назад.Шаг 5: Вывод результата
Выводим количество товаров и их максимальную стоимость, а также индексы выбранных товаров.Теперь давайте реализуем это в коде:
1. Мы создаем массивы для хранения максимальной стоимости и выбранных товаров. 2. Затем проходим по каждому товару и обновляем массивы, проверяя, можем ли мы добавить товар в отсек. 3. В конце мы находим максимальную стоимость и соответствующие товары, которые были выбраны. 4. Результат выводится в требуемом формате. Этот алгоритм работает за O(N · S · P), где P — максимальное давление, что может быть эффективно для заданных ограничений.