n個のバケットからのアイテムを選択するための最小コスト

Question

バケットはn個あります。各バケットには、I1、I2 & I3という3つのアイテムが含まれています。各項目には独自のコストが関連付けられています。 2つの連続するバケットから選択されたアイテムが同じでないように、各バケットからアイテムを選択する必要があります。そのようなバケットからn個のアイテムをピッキングするための最小コストを見つけるアルゴリズムは何でしょうか？

私はすべてのコストを探索し、それらの最小値を見つける再帰的ブルートフォースの解決策しか考えられません。

問題を解決するための効率的なアルゴリズムは何ですか？

Answer 1

動的プログラミングの状態空間は、次のように定義できます。この状態空間の

C[i,j] = minimum cost attainable by choosing items an item from each 
     bucket in {1,...,i} where each item index is different from 
     the item index in the previous bucket and the item in the 
     last bucket is j where i in {1,...,n} and j in {1,2,3} 

は、我々は、以下の再発関係、{1,2,3}各{1,...,n}でjとkためI[j,k]バケットkでk番目の項目のコストを意味し得ます。

C[i,j] = min { min { C[i-1,2], C[i-1,3] } + I[i,1]: j = 1, 
       min { C[i-1,1], C[i-1,3] } + I[i,2]: j = 2, 
       min { C[i-1,1], C[i-1,2] } + I[i,3]: j = 3 
      } 

初期状態は

C[1,1] = I[1,1], 
C[1,2] = I[1,2], 
C[1,3] = I[1,3] 

を割り当てることによって充填することができ、繰り返し状態空間を充填した後、所望の値がfolowing発現を評価することによって求めることができます。

min { C[n,1], C[n,2], C[n,3] }