Interview sur Facebook : trouvez l'ordre qui donne la somme maximale en sélectionnant des boîtes avec un numéro dans un anneau, lorsque les deux suivantes sont détruites.

Question

Je n'ai pas trouvé de question similaire à ce sujet. Il s'agit d'une question Facebook de dernière minute :

On vous donne un anneau de boîtes. Chaque boîte porte un nombre non négatif et peut être dupliquée.

Ecrivez une fonction/algorithme qui vous indique l'ordre dans lequel vous sélectionnez les cases, qui vous donnera la somme maximale.

Le problème, c'est que si vous sélectionnez une case, elle est retirée de l'anneau, tout comme les deux cases voisines (à droite et à gauche de celle que vous avez sélectionnée).

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

Si je choisis 12, 8 et 10 seront détruits et il vous restera 3.

Le maximum sera de sélectionner 8 d'abord puis 10, ou 10 d'abord puis 8.

J'ai essayé de réassigner aux boîtes leur valeur en prenant sa propre valeur et en soustrayant ensuite les deux à côté d'elle comme coût.

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

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

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

Aidez-moi, s'il vous plaît.

Il s'agit très probablement de programmation dynamique, mais je ne sais pas comment.

L'anneau peut être de n'importe quelle taille.

Answer 1

Voici un peu de 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 : []

Il pourrait sans doute être optimisé un peu. L'élément clé est val() qui calcule la valeur totale d'un anneau donné. Le reste n'est que de la comptabilité.