Максимальная удача, продавая и покупая картофельные специи с течением времени

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

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

e.g

стартовое состояние: 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 долл. США) у первой специи]
    [Купить 1,25 кг (5 долл. США) у третьей специи]
  • 2-й год:
    [Продать 1 кг (8 долл. США) первой специи]
  • 3 год:
    [Купить 2 кг (8 долл. США) у Second Spice]
  • 4-й год: ничего
  • 5-й год: ничего
  • 6-й год: ничего
  • 7-й год: ничего
  • 8-й год:
    [Продать 1,25 кг (-15x1,25=18,75 $) третьей специи]
    [Продать 2 кг (12x2=24 $) второй специи]
  • 9-й год
    ничего

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


dynamic-programming maximization maximize
person P. M. K    schedule 28.12.2020    source источник

Ответы (1)


arrow_upward
0
arrow_downward

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

Пусть 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 год: ничего не делать
person augurar    schedule 18.04.2021