如何找到从相邻对中选择元素的最小成本

Question

给定一个包含至少两个元素的整数数组，我需要从每一对相邻的元素中至少选择一个，这样选择的成本要尽量低。最后，我要返回这个成本和所选的元素。
比如，

[50, 30, 40, 60, 10, 30, 10]

我们从第一对(50, 30)中选择30，从第二对(30, 40)中选择40。接着，从(40, 60)中选择40，从(60, 10)和(10, 30)中选择10。最后，从(30, 10)中也选择10。这样我们得到的总成本是30 + 40 + 10 + 10 = 90。

再举个例子，

[60, 100, 70]

这里有两种可能的选择：[60, 70]或者[100]。但是，最优的选择是[100]，总成本是100，这比60 + 70要少。所以，算法应该选择100。

我遇到的问题是，我只成功写出了一个代码，能返回最低的成本，但没有保存所用的元素。

我用Python写的代码

arr = [50, 30, 40, 60, 10, 30, 10]
min_sum = [0] * len(arr)
min_sum[0] = arr[0]
min_sum[1] = arr[1]

for i in range(2, len(arr)):
    choice1 = min_sum[i-1] + arr[i]
    choice2 = min_sum[i-2] + arr[i]
    min_sum[i] = min(choice1, choice2)

res = min(min_sum[-1], min_sum[-2])
print(res)

Answer 1

这里有其他一些方法可以参考。我在你的代码中添加了一个处理只有一个剩余元素的情况。当你的列表是 [50, 30, 40, 60, 10, 30, 10, 10] 时，你的代码会得到相同的总和，但实际上多了一个元素。在这个例子中，你的代码会计算出总和为90，但应该是100。所以，我添加了这一部分来避免漏掉这个情况。

if l==len(arr)-1: #Check if there is only one element left to check
    res.append(arr[l]) 

最终的代码应该是这样的。

arr = [50, 30, 40, 60, 10, 30, 10]


l = 0
r = 1
res = []
while r<len(arr):
    min_value = min(arr[l],arr[r])
    res.append(min_value)
    print(min_value)

    if min_value==arr[r]: 
        l+=2
        if l==len(arr)-1 and r != len(arr)-1: #Check if there is only one element left to check
            res.append(arr[l])
        r+=2
        
    else:
        l+=1
        r+=1
    

print(res,sum(res))

Answer 2

如果我理解得没错，你可以保存索引而不是元素，然后通过这些索引重新生成你想要的输出：

lst = [50, 30, 40, 60, 10, 30, 10]

out = []
for i in range(len(lst) - 1):
    mn = min(i, i + 1, key=lambda k: lst[k])
    if not out or mn != out[-1]:
        out.append(mn)

out = [lst[i] for i in out]
print(out)

打印结果：

[30, 40, 10, 10]

Answer 3

我们把 cost(i) 叫做考虑到数组中第 i 个元素时的最优解的成本，这个问题有一个简单的递归公式：

cost(i) = min(
    arr[i] + cost(i-1),
    arr[i-1] + cost(i-2),
)

举个例子，对于数组 [50, 30, 40, 60, 10, 30, 10]，它的成本是以下几种情况中的最小值：

10 + cost for [50, 30, 40, 60, 10, 30]
30 + cost for [50, 30, 40, 60, 10]

这个递归的基本情况是：

cost(0) = 0
cost(1) = 0
cost(2) = min(arr[0],arr[1])

这个递归关系可以用简单的循环代码来实现：

def cost(a):
    if len(a) <= 1:
        return 0
    elif len(a) == 2:
        return min(a)
    cost_iminus2 = 0
    cost_iminus1 = min(a[:2])
    for i in range(2,len(a)):
        cost_i = min(
            arr[i] + cost_iminus1,
            arr[i-1] + cost_iminus2,
        )
        cost_iminus2, cost_iminus1 = cost_iminus1, cost_i
    return cost_i

你可以很容易地修改这段代码，让它记住在计算中用到哪些元素：

def selection(a):
    if len(a) < 2:
        return 0, []
    elif len(a) == 2:
        return min(a), [min(a)]
    cost_iminus2, selection_iminus2 = 0, []
    cost_iminus1, selection_iminus1 = min(a[:2]), [min(a[:2])]
    for i in range(2,len(a)):
        cost_i = min(
            a[i] + cost_iminus1,
            a[i-1] + cost_iminus2,
        )
        if cost_i == a[i] + cost_iminus1:
            selection_i = [*selection_iminus1, a[i]] # need to copy
        elif cost_i == a[i-1] + cost_iminus2:
            selection_i = selection_iminus2 # no need to copy
            selection_i.append(a[i-1])
        else:
            raise ValueError("unreachable branch")
        cost_iminus2, cost_iminus1 = cost_iminus1, cost_i
        selection_iminus2, selection_iminus1 = selection_iminus1, selection_i
    return cost_i, selection_i

输出结果：

>>> selection([50, 30, 40, 60, 10, 30, 10])
(90, [30, 40, 10, 10])
>>> selection([60,100,70])
(100, [100])