Условие:
В длинном прямом коридоре жилого комплекса расположено несколько магазинов, которые в своём ассортименте имеют продукты, произведённые в ситифермах. Объём ежедневно поставляемой продукции обычно невелик, поэтому доставка до точек сбыта осуществляется с помощью человека, занимающегося постоянным перемещением тяжестей в руках в соответствии с приказом Министерства труда и социальной защиты Российской Федерации от 14.09.2021 № 629н.

Несколько раз в день посредством специального приложения магазины заказывают у оператора ситиферм недостающую продукцию. Запросы учитываются во внутренней системе оператора и приходят на склад в следующем виде:

название_магазина_1;расстояние_от_склада_до_магазина_1;общая_масса_товара_для_магазина_1;название_магазина_2;расстояние_от_склада_до_магазина_2;общая_масса_товара_для_магазина_2…

Напишите программу, которая подсчитает общую продолжительность оптимального пути для доставки продуктов на основе полученных данных.
Учтите, что доставщик может зайти в несколько магазинов по пути, расстояние - целое число, масса указывается в килограммах с точностью до тысячной, десятичный разделитель - точка, доставщик не может заносить поставки в магазины частями; если доставка в конкретный магазин невозможна, он должен быть проигнорирован в расчётах.
Input: стандартный ввод или input.txt
Output: стандартный вывод или output.txt
Ограничения: 1с, 64 мб

Задача похожа на транспортную задачу из раздела математики, который называется “комбинаторика”. Только условие не полное. И ограничения не понятны. “1с” - означает что Python не применим для решения задачи? И что означает “64 миллибит”?

Alex.Pro.
Задача похожа на транспортную задачу из раздела математики, который называется “комбинаторика”. Только условие не полное. И ограничения не понятны. “1с” - означает что Python не применим для решения задачи? И что означает “64 миллибит”?

1с - про ограничение времени работы программы
64 мегабайта - макс объем памяти

Alex.Pro.
Задача похожа на транспортную задачу из раздела математики, который называется “комбинаторика”. Только условие не полное. И ограничения не понятны. “1с” - означает что Python не применим для решения задачи? И что означает “64 миллибит”?

А чего в условии не хватает?

Nespashiy
А чего в условии не хватает?

А в каких случаях доставка может быть невозможна?
Что мешает доставщику взять все заказы разом и разнести их по всем магазинам по очереди?
Для выше приведённого условия - "общая продолжительность (? это про время или про расстояние?) оптимального пути для доставки продуктов" будет равна расстоянию до самого дальнего магазина.

Alex.Pro.
Невозможно больше 15 кг за раз (по приказу минтруда, который в условии дан)

Nespashiy
Невозможно больше 15 кг за раз (по приказу минтруда, который в условии дан)

Охраной труда мы тут не занимаемся, поэтому ссылки на приказы Минтруда нас мало интересуют. Но, если условие задачи дополнено ограничением грузопод,ёмности доставщика - условие стало достаточно полным. Теперь предлагаю изучить теорию прикладной математики. Для решения сбалансированной транспортной задачи предлагаю использовать метод северо-западного угла для формирования опорного плана и метод потенциалов для окончательной оптимизации решения.
Успехов!

Это олимпиадная задача. Я такие стараюсь не решать, так как они мало похожи на задачи реального мира - “дикие задачи”. Когда я учился в начале, я их тоже прорешивал все, путая их с учебными. Поломать мозг, поучаствовать в олимпиаде или соревнованиях можно, но нужных навыков так не получишь. То есть после них ничего не напишешь. Для вырабатывания навыков надо решать учебные задачи, которые больше похожи на части реальных задач, потому что их специально делают такими, чтобы в мозге учащегося развить нужные навыки решения. Поэтому вузовские задачи, похожие друг на друга и в большом количестве, мне дали гораздо больше. Я научился делать многие вещи и поэтому у меня в реальных задачах всё получается делать и всё получается с первого раза.

Что касается этой задачи. Она такая же, как классическая задача про кузнечика, который прыгает или на одну, или на две клетки. То есть это задача на динамическое программирование. Чтобы её решить, надо начать рассматривать путь с конечной точки и размытывать путь к начальной точке, подбирая наилучший вариант с предыдущего шага. Так ты сможешь построить оптимальный путь. Когда ты дойдёшь до начальной точки, у тебя будет построен весь путь из наилучших вариантов.

Сначала входные данные отфильтруй и выкини из них те точки, до которых ты точно не доедешь. Потом на этих отфильтрованных данных строй оптимальный алгоритм с конца к началу.