複数の株式が与えられた場合の株式利益の最大化

Question

状況に応じて株式利益最大化アルゴリズムを検討しました。

在庫が1つしかなく、1回または複数回購入/販売できる状況の戦略はわかります。最大差分と最大サブアレイをそれぞれ使用します。

しかし、2つの株式とそれぞれの変動する価格が与えられるとどうなりますか？両方の株式を同時に保有して売却することはできず、別の株式を買うことはできません。

例：株式Aと株式Bを指定して収益を最大化します。株価は期間によって変動します。したがって、配列が与えられた場合、AとBの各配列内のインデックスは、特定の時刻の株式の価格を示します。両方の株式を同時に保有することができず、Aを購入し、Bを売却すると取引コストが発生することを考慮すると、使用する最良の戦略は何ですか？

Answer 1

はしてみましょう：

dp[i, j] = maximum worth obtainable at period i if we currently hold 
      stock j 

はt[i] = transaction cost at period iを想定します。

我々は持っている：

dp[0, A] = A[0] # buy the best at time 0 
dp[0, B] = B[0] # you said only buying A and selling B induces a cost, 
       # you didn't say buying B induces a cost. If it does, 
       # just subtract t accordingly below 
dp[i, A] = max(
      dp[i - 1, B] + A[i] - t[i], # sell B, buy A 
      A[i]      # buy A alone 
      )        # we buy A no matter what 

dp[i, B] = max(
      dp[i - 1, A] + B[i],  # sell A, buy B, - t[i] if needed 
      B[i]      # buy B alone 
      ) 

回答は次のとおりです。

max{dp[i, A], dp[i, B]} 
i