Facebook interview: découvrez l'ordre qui donne la somme maximale en sélectionnant des cases avec le numéro dans un anneau, lorsque les deux à côté de lui est détruit

Question

Vous n'avez pas trouvé de réponse similaire à ce sujet. Ceci est un tour final Question Facebook:

Vous recevez un anneau de boîtes. Chaque boîte a un nombre non négatif sur elle, peut être en double. Ecrivez une fonction/un algorithme qui vous indiquera l'ordre dans lequel vous avez sélectionné les boîtes, ce qui vous donnera la somme maximale. La capture est, si vous sélectionnez une boîte, elle est retirée de l'anneau, ainsi que les deux boîtes à côté de celle-ci (à droite et à gauche de celui que vous avez sélectionné).

donc si j'ai un anneau de
{10 3 8 12}

Si je sélectionne 12, 8 et 10 seront détruits et il ne vous reste 3.

Le maximum sélectionnerez 8 d'abord puis 10, ou 10 d'abord puis 8.

J'ai essayé de ré-affecter les boîtes leur valeur en prenant sa propre valeur, puis soustraire les deux à côté de est le coût.

Ainsi l'ancien anneau est {10 3 8 12}

le nouvel anneau est {-5, -15, -7, -6}, et je choisirai le plus élevé.

Cependant, cela ne fonctionne pas vraiment si vous avez {10, 19, 10, 0}, vous devez prendre les deux 10s, mais l'algorithme prendre le 19 et 0.

Aide s'il vous plaît?

Il est très probable que la programmation dynamique, mais je ne sais pas comment.

La bague peut être de n'importe quelle taille.

Answer 1

Voici quelques python qui résout le problème:

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

Sortie:

Total: 18
choix: 10 index: 0 nouvelle liste: [8]
choix: 8 Index: 0 nouvelle liste: []

Total: 20
choix: 10 index: 0 nouvelle liste: [10]
choix: 10 index: 0 nouvelle liste: []

Sans doute, il pourrait être un peu optimisé. Le bit de clé est val(), qui calcule la valeur totale d'un anneau donné. Le reste est juste la comptabilité.