从n个桶中选择物品的最低成本

我有n个桶数。每个桶包含3个项目 - 比如I1，I2 & I3。每个项目都有自己的成本关联。您必须从每个存储桶中挑选物品，以便从两个连续存储桶中挑选的物品不相同。从n个这样的桶中找到n个物品的最小成本是什么算法？从n个桶中选择物品的最低成本

我能想到的唯一的递归蛮力解决方案，将探讨所有费用，并找出其中最小的。

什么可以是有效的算法来解决这个问题？

来源

2016-11-13 coderx

用于动态编程状态空间可以被定义如下。

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] }

来源

2016-11-13 07:33:31 Codor

从n个桶中选择物品的最低成本

回答

相关问题