Путешественник собрался пересечь пустыню. Расстояние - 20 дней пути. Путешественник может нанять некоторое число помощников (они готовы помогать просто за еду). И путешественник и помощники могут нести запас пищи максимум на 7 дней пути каждый. Все ходят с одинаковой скоростью, а пища расходуется равномерно. Пищу можно оставлять в пустыни, но ее должен охранять от шакалов хотя бы один из помощников или путешественник. Во время стоянки (охраны пищи) охранник также расходует пищу как и во время путешествия. Все помощники по окончании миссии желают вернуться в начальный пункт путешествия за счет еды путешественника.
Сколько минимально еды должен закупить путешественник чтобы выполнить миссию, если:

подзадача 1: он хочет минимизировать свои расходы на еду

подзадача 2: он хочет побыстрее пересечь пустыню (возвращающиеся помощники, после финиша путешественника на в счет времени, но в счет затрат еды)

на 7 дней на одного человека?

(1) да

тогда он никогда не перейдет пустыню

(3) почему?

хотя нет перейдет

(2) Тогда максимум они смогут уйти на расстояние 3,5 дня пути, если хотят вернуться живыми. Путешественник уйдёт на 7 дней пути и помрёт от голода.

помнится мы такие рашали на методах оптимизации. Единственное что помню это что препод говорил про уравнение в частных производных

(6) нет. 2е могут оттащить скольк угодно еды на расстояние 1 день и тд

(6) ну вот представь если бы там было всего 10 дней пути
он берет троих негров и тащится с ними 3 дня, потом забирает у каждого из них по 1 пайко-дню еды, онегры возвращаются, а он с 7 пайками преодолевает оставшиеся 7 дней

(9) Да, тебя так просто в пустыне не истребить :)

пойдем от обратного. в конце пути путешественник пойдет один. значит это 7 дней. осталось рассчитать сколько афроамериканцев надо захватить с собой чтобы в конце 13 дня отнять у них еды на 7 дней.

(11) задача осложняется тем что нужно временные хранилища еды делать

на той стороне можно закупиться?

(11) Еще надо определиться (в задаче не сказано), можно ли оставить помощников в пустыне без еды, либо им надо обеспечить едой на обратный путь.

Можно ли грабить корованы?

(0) Надо просто есть помощников, затраты на еду будут минимальны.

(14) Сказано, что все помощники хотят вернуться домой

(12) не нужно, а можно
(13) на той стороне закупаться нельзя, вообще допустим там помощникам не рады, они хотят там появляться
(14) все должны вернуться живыми

+(18) они НЕ хотят там появляться

(18) встречать возвращающихся можно?

ну алгоритм в (9) описан, остается только рассчитать количество стартующих
ну а без запасов - тогда надо в условии что все четко - без опазданий - типа высылать экспедицию на встречу

(20) можно

последние 10 км проходятся на одном рюкзаке
т.е.
в точке -10 надо иметь 7х4 28 кг еды
это обеспечивается + 28 носильщиков 24 из которых вернуться назад отдав по 1 кг остальным
т.е. на точке -13 надо иметь 28*4 кг еды которые обеспечивают 28*4 носильщиков

это туда и наиболее быстро - без возвращений и ожиданий для путешественника

обратно - надо еще носильшиков либо для встречи либо для создания запасов для возвращающихся

"И путешественник и помощники могут нести запас пищи максимум на 7 дней пути каждый" запас пищи на всю группу или только на себя?

Надо просто оставлять помощников по цепочке с едой через какие-то промежутки времени - охранять ее для возвращающихся, тогда возвращающиеся смогут отдать все путешественнику, не доходя с ним до конца

(24) 7 паек, пайка на одного человека в день

Понятно, что нужно менять число помощников. Сначала их должно быть много, но с каждой "ходкой" количество должно уменьшаться.

(11)  На первом этапе могут идти сколько угодго помощников. Они идут 3 дня оставляют запас на 1 день и возвращаются.

(27) На 13 день их должно быть 7 и они могут оставить по запасу на 1 день.

Каково соотношение голубоглазых и кареглазых помощников?

(+29) на 10 день их должны ждать 70 порций.

(+31) На третий день 21 порция. До третьего дня можно взять сколько угодно много помощников.

Кннибализм не предлагать?

(33) Хороший вариант :)))

Разделим задачу на две позадачи:
1) Доставка путешественника к цели
2) Эвакуация негров домой. Будем считать, что в точке, когда негр должен повернуть назад ему нужен однодневный запас чтобы вернуться на один день назад. А там его встретят собратья накормят и датут пищу на обратный путь.

Доставка путешественника до цели
0) Начинают путешествие 17 человек включая путешественника.
Далее в каждом пункте людям которым надо идти обратно дают однодневный запас пищи и отправляют домой. Остальные загрузившись 7-ми дневным запасом идут вперед. Ниже указано сколько человек продалжает движение вперед.
1) 14чел.
2) 12чел.
3) 10чел.
4) 8чел.
5) 7чел.
6) 6чел.
7) 5чел.
8) 4чел.
9) 3чел.
10) 3чел.
11) 2чел.
12) 2чел.
13) 1чел.

(0) Если не хватит еды - можно сожрать негров.

В условии задачи написано: "Все помощники по окончании миссии желают вернуться в начальный пункт путешествия за счет еды путешественника."

Нигде не написано что помощников нельзя продинамить.

(36) Не воруй мою идею! (33)

(0) Из условия
"Все ходят с одинаковой скоростью, а пища расходуется равномерно."
следует, что задача не дискретна, т.е. можно пройти, например, 2/7 дня и взять с собой 6,666 единиц еды?

(39) можно

(0)243 дня? Ну или около того...
Примерно прикинул... :)

(41) Ой. Это если он один будет ходить.

надо так: прежде отправить негров пусть по пути следования сделают припасы заранее, тогда
отправляется первый негр  делает припасы на точке 3,5 дня пути, второй на 7, третий на 10,5 и  четвертый на 14

(40) при таком условии, IMHO смысл в запасах теряется: можно организовать доставку необходимого количества к нужному времени, без издержек на охрану.

Минимальное количество еды - 739,7958
Еда     Макс. расстояние
7    7
14    9,333333333
21    10,5
28    11,27777778
35    11,97777778
42    12,44444444
49    12,83333333
56    13,22222222
63    13,55555556
70    13,81481481
77    14,06481481
84    14,29814815
91    14,53148148
98    14,72592593
105    14,92037037
112    15,07592593
119    15,23148148
126    15,38703704
133    15,51666667
140    15,6462963
147    15,77592593
154    15,90319865
161    16,01986532
168    16,13653199
175    16,2476431
182    16,35875421
189    16,46481481
196    16,5545584
203    16,64097816
210    16,72431149
217    16,80764482
14    9,333333333
21    10,5
28    11,27777778
35    11,97777778
42    12,44444444
49    12,83333333
56    13,22222222
63    13,55555556
70    13,81481481
77    14,06481481
84    14,29814815
91    14,53148148
98    14,72592593
105    14,92037037
112    15,07592593
119    15,23148148
126    15,38703704
133    15,51666667
140    15,6462963
147    15,77592593
154    15,90319865
161    16,01986532
168    16,13653199
175    16,2476431
182    16,35875421
189    16,46481481
196    16,5545584
203    16,64097816
210    16,72431149
217    16,80764482
224    16,8854226
231    16,96320038
238    17,04097816
245    17,11875594
252    17,19653371
259    17,27345679
266    17,34345679
273    17,41012346
280    17,47493827
287    17,53975309
294    17,6045679
301    17,66938272
308    17,73419753
315    17,79253086
322    17,84808642
329    17,90364198
336    17,95549383
343    18,00734568
350    18,05919753
357    18,11104938
14    9,333333333
21    10,5
28    11,27777778
35    11,97777778
42    12,44444444
49    12,83333333
56    13,22222222
63    13,55555556
70    13,81481481
77    14,06481481
84    14,29814815
91    14,53148148
98    14,72592593
105    14,92037037
112    15,07592593
119    15,23148148
126    15,38703704
133    15,51666667
140    15,6462963
147    15,77592593
154    15,90319865
161    16,01986532
168    16,13653199
175    16,2476431
182    16,35875421
189    16,46481481
196    16,5545584
203    16,64097816
210    16,72431149
217    16,80764482
224    16,8854226
231    16,96320038
238    17,04097816
245    17,11875594
252    17,19653371
259    17,27345679
266    17,34345679
273    17,41012346
280    17,47493827
287    17,53975309
294    17,6045679
301    17,66938272
308    17,73419753
315    17,79253086
322    17,84808642
329    17,90364198
336    17,95549383
343    18,00734568
350    18,05919753
357    18,11104938
364    18,16290123
371    18,21437182
378    18,26103849
385    18,30770516
392    18,35345679
399    18,39666667
406    18,43987654
413    18,48308642
420    18,5262963
427    18,56872054
434    18,61114478
441    18,65281145
448    18,69447811
455    18,73541379
462    18,77430268
469    18,81319156
476    18,85208045
483    18,89096934
490    18,92985823
497    18,96874712
504    19,00578416
511    19,04282119
518    19,07985823
525    19,11670034
532    19,15205387
539    19,18740741
546    19,22074074
553    19,25407407
560    19,28740741
567    19,31981481
574    19,35222222
581    19,38462963
588    19,41574074
595    19,44604377
602    19,4759583
609    19,50587283
616    19,53467942
623    19,56245719
630    19,59023497
637    19,61801275
644    19,64568073
651    19,67160666
658    19,69753258
665    19,72345851
672    19,74938444
679    19,77531036
686    19,80123629
693    19,82716221
700    19,85308814
707    19,87901407
714    19,90493999
721    19,93086592
728    19,95679184
735    19,98243287
742    20,0080739