Динамическое программирование - Поиск Максимальная прибыль

Question

Я новичок динамического программирования. Итак, я полагаю, чтобы найти максимальную прибыль. Я не думаю, что я делаю правильно. Я не понимаю, для чего предназначены k конверсий. В данном примере даются 3 валюты, поэтому есть 3 преобразования. Может кто-нибудь, пожалуйста, дайте мне больше идей о том, как это решить?

Answer 1

Во-первых, давайте подумаем о том, сколько валютных операций есть. Если у вас есть три валюты (давайте назовем их фунтами, франками и отметками), у вас есть шесть возможных типов валютных операций: Фунты к отметкам, отметки в фунтах, фунты к франкам, франки к фунтам, франки к отметкам и отметки к фр.

Но с точки зрения вашей проблемы, когда они говорят, что у вас есть транзакции в валюте, они имеют в виду, что вам разрешено начинать с некоторой валюты и совершать последовательность транзакций в валюте. Ваша задача - выяснить, какие транзакции k приведут к наибольшей прибыли. Так, например, если у вас есть три валюты, но k = 1, и вам говорят начать с фунтов, ваша задача будет легкой: решите, лучше ли фунты к франкам, или фунты к отметкам лучше. Если k = 2, у вас есть больше вариантов и т. Д.

Возможно, было бы полезно подумать об этом как о взвешенном ориентированном графе, где валюты являются узлами, а дуги взвешены по обменным курсам. Тогда вы можете думать о проблемах с точки зрения нахождения наиболее выгодного пути по графику длины k, начиная с узла i.

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

И, наконец, динамическое программирование на структурах графов обычно включает в себя построение решения длины n + 1 из решения длины n, поэтому вы, вероятно, должны начать думать о наименьшей возможной проблеме и о том, как она относится ко второму наименьшая проблема и т. д.