Question

Для строительства дома Сидорову нужно купить и доставить на строительную площадку песок. Стоимость песка составляет 500 руб за куб. м. Поставщик песка предлагает два варианта доставки песка: большими и маленькими самосвалами. Цена доставки за один рейс самосвала устанавливается вне зависимости от количества перевозимого песка и составляет 8600 руб за большой самосвал вместимостью 12 куб. м и 6300 руб за маленький самосвал вместимостью 5 куб. м. Большой самосвал в отличие от маленького к строительной площадке подъехать не может. Большой самосвал приходится разгружать около дороги. Рабочие, нанятые Сидоровым, согласились перевозить песок тачками от дороги до строительной площадки по цене 400 рублей за куб.м песка. Найдите минимальную стоимость приобретения и доставки на строительную площадку 48 куб.м песка, если доставку песка нужно произвести за 3 дня, рабочие могут перевезти в сутки не более 12 куб.м песка, а самосвалы совершить не более 3 рейсов в сутки? Завозить песок на строительную площадку тачками и самосвалами можно одновременно.

Answer 1

РЕШЕНИЕ
Вариант 1 - "маленькими" самосвалами и без грузчиков.
1) 48 м³ : 5 м³/рейс = 9,6 рейс ≈ 10 рейсов
2) 6300 руб * 10  = 63000 руб - стоимость заказа 1.
3) 10 рейсов : 3р/дн > 3,3 дней - не укладываются по сроку на 1/3 дня.
Вариант 2 - "большими" самосвалами и тачками.
1) 48 м³ : 12 м³/р = 4 рейса
2) 8600 р * 4 = 34 400 руб -  доставка самосвалами
3) 48 м³ : 12 м³/день = 4 дня - не укладываются по сроку на 1 день. 
4) 400 р/м³ * 48 м³ = 19 200 руб - доставка тачками.
5) 34 400 + 19 200 = 53 600 руб -  стоимость заказа.2.
ВЫВОД
1. Оба заказа не укладываются по сроку от 8 часов до целого дня.
2. Доставка тачками - значительно дешевле 53,6:63 = 0,85 = 85%

Answer 2

Для решения этой задачи можно воспользоваться динамическим программированием.

Пусть DP[i][j] будет минимальной стоимостью доставки i кубических метров песка за j дней.

Инициализация:

• DP[0][j] = 0 - доставка 0 кубических метров песка за любое количество дней обойдется в 0 рублей.
• DP[i][0] = infinity для всех i > 0 - невозможно доставить положительное количество песка за 0 дней.

Динамическое программирование:

• Для каждого значения i от 1 до 48 и каждого значения j от 1 до 3:
  • Рассмотрим случай, когда песок доставляется только тачками. Тогда стоимость доставки i кубических метров песка за j дней будет равна DP[i][j] = DP[i][j-1] + 400 * i.
  • Рассмотрим случай, когда песок доставляется только маленькими самосвалами. Тогда стоимость доставки i кубических метров песка за j дней будет равна DP[i][j] = DP[i][j-1] + 6300 * ceil(i / 5).
  • Рассмотрим случай, когда песок доставляется большими самосвалами. Так как большой самосвал может перевезти только 12 кубических метров песка, нам необходимо разделить i на 12 и округлить вверх. Обозначим это как k = ceil(i / 12). Тогда стоимость доставки i кубических метров песка за j дней будет равна DP[i][j] = DP[i - 12 * (k - 1)][j-1] + 8600 + 400 * (i - 12 * (k - 1)).

Минимальная стоимость доставки 48 кубических метров песка за 3 дня будет равна DP[48][3].

Приведенный подход позволяет найти минимальную стоимость доставки песка на строительную площадку, учитывая все ограничения и возможные варианты доставки.