Классически такая задача формулируется как транспортная - машина должна из имеющегося запаса бензина доставить макс. кол-во в указанную точку (вариант - уехать максимально далеко).
дал верный ответ (обычно, правда, такая задача предполагает целочисленное решение, в этом случае на базар будет доставлено 533 банана). То, что оно верное - можно доказать. Строгое доказательство, полагаю, существует, я дам не совсем строгое, а так, основу.
Условие "доставить макс. кол-во на базар" эквивалентно (почти - без учёта того, что ради увеличения доставки можно кое-что бросить посередь пути) условию "использовать мин. количество на питание по дороге".
Исходно у нас 3000 бананов. Т.к. грузоподъёмность составляет 1000, то из исходной точки придётся выходить трижды. Запомним это.
Собственно алгоритм движений одинаков - берём по максимуму, идём до некоей точки, разгружаемся по максимуму, возвращаемся к точке, где ещё есть бананы... ну кроме последнего рывка, само собой. При этом получается, что движение вперёд - полезное, назад - паразитное (растёт расход на питание в пути!). Более того, чем дальше мы идём вперёд на очередной стадии (когда сзади ещё остались бананы, за которыми надо вернуться), тем больше эти паразитные расходы. К тому же минимизация количества этих "маятниковых" хождений тоже благотворно скажется на результате. (вот тут - отступление от строгости, доказательство, что первые два хождения должны быть равны, сложновато, примем это как постулат) Когда верблюд добредёт третий раз до точки первого сброса, он должен прикончить первую тысячу бананов, чтобы на след. стадии уменьшить количество челночков с 3 до 2. Соответственно он прошёл расстояние до первой точки сброса 5 раз, т.е. она располагается на 1000/5=200 км. Аналогично просчитывается положение второй точки сброса - в 1000/3 км от первой. И как итог - 533 банана на базаре.
Кстати, довольно забавно было скормить эту задачу Экселевому солверу. Подробно расписать движение верблюда, учесть, что на горбу, что на земле, что съедено, понаставить ограничений (всё целое, всё от 0 до 1000, ещё кое-какие ограничения одних цифирей по сравнению с другими...) и попросить максимизировать итог. Решение даётся почти мгновенно.
