Блог

Допустим, у нас есть начальное состояние в 10 долларов, и мы хотим зарабатывать деньги, покупая и продавая картофель, и волшебным образом мы знаем цены ($) за кг в год на каждую картофельную специю. Каков наилучший алгоритм для нахождения конечного максимального состояния или локального максимума?

!! Если у вас состояние в 15 долларов, и вы продаете несколько кг в год и зарабатываете, скажем, на 4 доллара больше, вы не можете купить что-то, что стоит вам 19 долларов в том же году, они независимы, поэтому у вас должны быть деньги, чтобы купить что-то, прежде чем продавать что-то еще в том же году!!

например

начальное состояние: 10 $

Цены ($) за кг картофельных специй в год:

• Картофельные специи 1 цена ($) за кг:
  [5, 8, 7, 10, 12, 11, 14, 11, 10]
• Картофельные специи 2 цена ($) за кг:
  [8, 8, 4, 5, 7, 15, 10, 12, 10]
• Картофельные специи 3 цена ($) за кг:
  [4, 7, 5, 6, 10, 9, 11, 15, 11]

Что будет хорошим решением для этого?

Простой локальный максимум может быть достигнут следующим путем:

• 1-й год:
  [Купите 1 кг (5 $) у first spice]
  [Купите 1,25 кг (5 $) у third spice]
• 2-й год:
  [Продажа 1 кг (8 $) от first spice]
• 3-й год:
  [Купить 2 кг (8 $) у second spice]
• 4-й год: ничего
• 5-й год: ничего
• 6-й год: ничего
• 7-й год: ничего
• 8-й год:
  [Продажа 1,25 кг (- 15×1,25 = 18,75 $) от третьей специи]
  [Продажа 2 кг (12×2 = 24 $) от второй специи]
• 9-й год
  ничего

Состояние 42,75 $ (это был пример, наверняка не максимальное состояние)

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

Пусть P(i, k) будет цена за килограмм картофеля i в год k . Определите V(i, k) , чтобы быть стоимостью 1 кг картофеля i в год k , и пусть F(k) будет стоимостью 1 доллар в год k . Максимальное состояние, начиная с d долларов d * F(0) .

В качестве базового примера, в прошлом году k_max мы:

 V(i, k_max) = P(i, k_max)
F(i, k_max) = 1
 

Мы можем вычислить оставшиеся значения V и F посредством взаимной рекурсии следующим образом:

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

  V(i, k) = max(V(i, k 1), P(i, k) * F(k 1))

• В данном году k мы можем либо купить немного картофеля i (на любую сумму i ), либо придержать наши деньги до следующего года:

  F(k) = max(V(i, k 1)/P(i, k), F(k 1))

Обратите внимание, что из-за линейной разделимости «смешанные» стратегии не приносят пользы. В данном году мы должны либо вложить все наши наличные деньги в самый прибыльный вид картофеля, либо не вкладывать вообще. Аналогично, для каждого вида картофеля и года мы должны либо продать все наши запасы этого типа, либо сохранить их до следующего года.

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

     Year 1 2 3 4 5 6 7 8 9
Potato 1 - S - S S S S S S
       2 S S B B B S - S S
       3 B S S S S B B S S
 

Начиная с 10 долларов, это дает нам:

• Год 1: купите 2,5 кг картофеля 3 за 10 долларов
• Год 2: Продайте 2,5 кг картофеля 3 за $ 17,50
• Год 3: Купите 4,375 кг картофеля 2 за $ 17,50
• Год 4: ничего не делать
• Год 5: ничего не делать
• Год 6: Продайте 4,375 кг картофеля 2 за 65,625 долл.
• Год 7: Купите ~ 5,97 кг картофеля 3 за $ 65,625
• Год 8: Продайте ~ 5,97 кг картофеля 3 за ~ 89,49 долл.
• Год 9: ничего не делать