從n個桶中選擇物品的最低成本

Question

我有n個桶數。每個桶包含3個項目 - 比如I1，I2 & I3。每個項目都有自己的成本關聯。您必須從每個存儲桶中挑選物品，以便從兩個連續存儲桶中挑選的物品不相同。從n個這樣的桶中找到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} 

對於該狀態下的空間，我們得到以下的遞推關係，其中I[j,k]用於{1,...,n}每個j和k{1,2,3}中表示第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] 

和後迭代地填充的狀態空間，所需的值可以通過評估如下因素表達中找到被填充。

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