Путник может брать с собой пищу (еду, питьё) на р дней. А перебраться ему надо по пустынной местности на 2р-дневное...
...расстояние. У него есть возможность нанять нужное число помощников ("гидов"), которые, разумеется, должны вернуться назад к себе домой после завершения своих "миссий". Каждый из них может нести с собой столько же пищи, сколько и путник. Здесь и далее ради краткости и время, и путь, и кол-во пищи будем измерять в днях.
"Стратегия" такая: осуществить задуманное как можно быстрее, меньшим числом гидов и меньшим количеством пищи. Путник рассуждает таким образом.
"Я должен очутиться один на расстоянии р от цели с пищей р - дальше доберусь сам.
Нанимаю 13 гидов. Первое расстояние р разбиваю на 4 равные части.
ЭТАП 1. Выходим 14 чел с пищей 14р. К концу этапа израсходуем 14*р/4= 3,5р пищи. 6 чел возвращаются - им нужно 6*р/4= 1,5 р пищи. Итого расход этапа 3,5р+1,5р= 5р. Остаток 14р-5р= 9р. Путь будем продолжать 8 чел с пищей 8р. Разность 9р-8р= р спрячем на склад №1.
ЭТАП 2. Выходим 8 чел с пищей 8р. К концу этапа израсходуем 8*р/4= 2р пищи. 4 чел возвращаются - им нужно 4*(р/4+р/4)= 2р пищи. Дадим им 4*р/4= р пищи - этого хватит на путь до склада №1. Остальное р заберут со склада №1. Итого расход этапа 2р+р= 3р. Остаток 8р-3р= 5р. Путь будем продолжать 4 чел с пищей 4р. Разность 5р-4р= р спрячем на склад №2 (склад №1 уже пуст).
ЭТАП 3. Выходим 4 чел с пищей 4р. К концу этапа израсходуем 4*р/4= р пищи. 2 чел возвращаются - им нужно 2*(р/4+р/4+р/4)= 1,5р пищи. Дадим им 2*р/4= 0,5р пищи - этого хватит на путь до склада №2. Остальное р заберут со склада №2. Итого расход этапа р+0,5р= 1,5р. Остаток 4р-1,5р= 2,5р. Путь будем продолжать 2 чел с пищей 2р. Разность 2,5р-2р= 0,5р спрячем на склад №3 (склады №1 и №2 уже пусты).
ЭТАП 4. Выходим 2 чел с пищей 2р. К концу этапа израсходуем 2*р/4= 0,5р пищи. Последний гид возвращается - ему нужно р/4+р/4+р/4+р/4= р пищи. Даю ему 0,5р пищи - этого вместе с содержимым склада №3 хватит ему на весь путь до дому. Итого расход этапа 0,5р+0,5р= р. Остатка 2р-р= р хватит мне совершить последний марш-бросок".
Итак, задача решена.
ВОПРОС: Можно ли придумывать вариант решения пооптимальнее, придерживаясь стратегию, упомянутую в начале? Вообще, может быть, существует методика, позволяющая решать такие задачи на оптимизацию в общем виде?
Одновременное соблюдение всех трёх условий, указанных в "стратегии", скорее всего невозможно. Поэтому предлагаю придерживаться первого из них - поход должен завершиться как можно быстрее.
Ой, извините! Время меньше 2р не может быть! Значит, нужно минимизировать число задействованных лиц; то есть постараться найти решение при числе нанятых, меньших, чем 13 чел.
постановки задачи я так и не увидел
Такие задачи решаются "с конца". На полпути должен оказаться полный запас.
Возможный "садистский" вариант - когда шерпы (феллахи или бедуины) отдают весь остаток (они же местные! проживут как-нибудь!), как с многоступенчатой ракетой - пустые ступени отбрасываем. Тогда можно без возвратов. Оставшиеся полпути не обязательно делить пополам.
Напоминает знаменитую задачку о коммивояжере (раздел комбинаторика)
Пожалейте последнего гида! Зачем ему на последнем этапе таскать туда и обратно лишние 0,25р груза? Спрячьте его на складе №3. Да и на втором складе можно оставить 1,25р и не тащить лишние 0,25 на третий.
Путнику в пустыне пища практически не нужна). А вот водой лучше бы запастись.