Minimiser la somme itérative de paires de nombres dans une liste

Question

Compte tenu du tuple (liste, valeur):

$$ gauche ( gauche [x_1, x_2, cdots x_n droite], y droite) $$

Vous pouvez choisir deux valeurs adjacentes dans la liste pour modifier le tuple comme:

dollars } + x_ {i + 1} droit) $$

Itérer jusqu'à:

$$ gauche ( gauche [ sum_i x_i droite], y + z droite) $$

Quel est l'ensemble optimal de choix qui minimise $ z $?

Intuitivement, vous ne voulez jamais opérer sur le plus grand nombre de la liste. Mais le plus grand nombre de cette liste change lorsque vous ajoutez des valeurs ensemble. En d'autres termes, la solution optimale n'est pas nécessairement obtenue par une solution optimale d'un sous-problème.

Une solution gourmand commencerait par prendre le plus petit nombre de cette liste et l'ajouter au plus petit de ses nombres adjacents. Cette solution, bien que close, n'est pas équivalente à la valeur renvoyée par la recherche de force brute. Cela souligne le fait que l'étape localement optimale n'est pas optimale à l'échelle mondiale, ce qui pourrait être lié au fait que l'élément le plus grand de la liste change à mesure que les valeurs sont additionnées.