facebook采访 : find out the order that gives max sum by selecting boxes with number in a ring, 旁边两个被摧毁时

Question

没有找到关于此的任何类似问题。这是最后一轮 Facebook 问题:

给你一圈盒子。每个盒子上都有一个非负数，可以重复。

编写一个函数/算法来告诉您选择方框的顺序，从而得出最大总和。

要注意的是，如果您选择一个框，它就会从环上取下，它旁边的两个框(在您选择的框的左右)也是如此。

所以如果我有一枚戒指
{10 3 8 12}

如果我选择 12，8 和 10 将被销毁，剩下 3。

最大值将先选择 8 再选择 10，或者先选择 10 再选择 8。

我尝试通过取其自己的值然后减去旁边的两个作为成本来重新分配框的值。

所以旧环是 {10 3 8 12}

新的环是{-5, -15, -7, -6}，我会选择最高的。

但是，如果您有 { 10, 19, 10, 0}，这肯定行不通，您应该取两个 10，但算法会取 19 和 0。

请帮忙？

这很可能是动态规划，但我不知道如何。

戒指可以是任何尺寸。

Answer 1

这里有一些 python 可以解决这个问题:

def sublist(i,l):
    if i == 0:
        return l[2:-1]
    elif i == len(l)-1:
        return l[1:-2]
    else:
        return l[0:i-1] + l[i+2:]

def val(l):
    if len(l) <= 3:
        return max(l)
    else:
        return max([v+val(m) for v,m in [(l[u],sublist(u,l)) for u in range(len(l))]])

def print_indices(l):
    print("Total:",val(l))
    while l:
        vals = [v+val(m) for v,m in [(l[u],sublist(u,l)) for u in range(len(l)) if sublist(u,l)]]
        if vals:
            i = vals.index(max(vals))
        else:
            i = l.index(max(l))
        print('choice:',l[i],'index:',i,'new list:',sublist(i,l))
        l = sublist(i,l)

print_indices([10,3,8,12])
print_indices([10,19,10,0])

输出:

Total: 18
choice: 10 index: 0 new list: [8]
choice: 8 index: 0 new list: []

Total: 20
choice: 10 index: 0 new list: [10]
choice: 10 index: 0 new list: []

毫无疑问，它可以进行一些优化。关键位是 val()，它计算给定环的总值。剩下的只是簿记。