Доброго времени суток!
Условие задачи звучит следующим образом:
Есть некоторое количество "заводов" которые из одного ресурса получают другой.
Каждый завод может произвести какое-то ограниченное количество ресурса.
У каждого завода есть свое фиксированное соотношение получаемого ресурса вида Б из А.
На вход подается какое-то количество ресурса одного вида. На выходе нужно получить максимально возможное количество ресурса другого вида, путем преобразования ресурсов на заводах.
Потери при преобразовании неважны. Т.е. если получаем избыточное число промежуточного ресурса который нельзя задействовать в дальнейшем преобразовании то плевать на него.
Главное получить максимальное количество заданного другого ресурса.
Число промежуточных заводов неограничено (или для простоты алгоритма можно ограничивать каким-то уровнем 2,3,4 ....).
Также может быть множество заводов производящих ресурс А из Б, но при этом иметь разный объем производства и разное соотношение производимого ресурса.
Пояснение:
- Большие точки - ресурс.
- связи между ними - заводы производящие переработку 1 ресурса на 2
- стрелка указывает направление обмена
- текст на стрелке указывает соотношение обмена и количество конечного ресурса которого может произвести данный завод
к примеру: 1/2 (100) [AC1]
- AC1 - условно имя завода
- 1/2 - соотношение обмена ресурса,
- (100) - максимальное возможное число единиц производимого ресурса.
- Т.е. завод AC1 делает переработку ресурса А на ресурс С. Из одной единицы ресурса А он может произвести 2 единицы ресурса С. Всего он может произвести 100 единиц ресурса С.
Пояснение к "большому" изображению
На вход подаем 100 единиц ресурса А.
На выход хотим получить наибольшее количество ресурса B
Есть маршрут
ab1 Из него можно сразу получить 100 B. Но при наличии других маршрутов он не есть оптимальный.
Второй возможный маршрут Ac1
Ac1: 50A => 100C
=>CB2: 25C -> 50B
=>CB1: 75C -> 75B
-----------------------------
∑ 125B получили
25C «остаток» его можно либо задействовать на 2 линиях, либо даже вернуть в первоначальное состояние Т.е. снова преобразовать в А. Ну или на крайний случай ничего не делать с ним.
Таким образом на втором маршруте используем 50 единиц ресурса А, а на первый (и в данном случае единственный ) пускаем остальные 50 единиц.
AB1 => 50A => 50B
-----------------------------------------------
∑ 125B + 50B = 175B - получили из 100 единиц ресурса А
- Несколько путей могут пересекаться.
- Некоторые пути могут зависеть от предыдущих путей, к примеру из А получаем B (через C ). Для чего используем 2 маршрута.
I) А -> C -> B
II) А -> C -> B
После их выполнения на "С" появится некий "излишек" ресурса. Его можно будет задействовать на "новом" появившимся лишь после прохождения этих первых двух маршрутов, к примеру С-> D -> B
Т.е. если "промежуточный" ресурс можно задействовать в других/ паралельных маршрутах - его нужно задействовать.
Но если его уже нельзя никак задействовать - то плевать на него. Т.е. задача "безотходного" производства или "производства без потерь" не ставится.
- не исключается "откат", т.е. возвращение к первоначальному ресурсу из каких-то промежуточных ресурсов, а то и с конечного.
Т.е. если хотим получить из 10 А B,
и есть маршруты 1 А - > 2 B (150 )
и 1B -> 2 A ( 20 )
то следующие шаги вполне допустимые:
1) по маршруту 1 А - > 2 B (150 ) получить 20 Б
2) по маршруту 1B -> 2 A ( 40 ) получить 40 А
3) по маршруту 1 А - > 2 B (130 ) [это первый маршрут но у него уже на 20 единиц конечной продукции меньше ] из 40 А получить 80 B
т.е. сразу построить цепи и среди них найти лучшие невыйдет, так как они могут влиять друг на друга ну и образовываться лишь после образования каких-то конкретных цепей.
Количество заводов и количество видов ресурсов не ограничивается.
Количество заводов производящих один вид ресурса из другого также не ограничивается.
Сложность алгоритма ( с точки зрения вычислений ) также неособо важна.
При наличии 5 заводов и по две связи между каждым ресурсом ( а связей может быть в разы больше) будет какая-то такая паутина
http://imglink.ru/pictures/17-02-11/877256...461dcf0f402.jpg
Но для простоты реализации или вычислений количество одного и другого можно искусственно ограничить.
Помогите пожалуйста кто чем может
алгоритмом решения или подсказками на что эта задача смахивает и с помощью чего было бы оптимально ее решить, любые идеи и подсказки
Буду благодарен любой Вашей помощи.
Линейный вид
