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

对于此状态空间，我们获得以下递归关系，其中{1,...,n}中的每个j的I[j,k]和{1,2,3}中的k表示存储桶k中的k-th项目的成本。

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