Minimizzare la somma iterativa di coppie di numeri in un elenco

Question

Dato il tuple (elenco, valore):

$$ Left ( Left [X_1, X_2, CDOTS X_N a destra], y a destra) $$

È possibile scegliere due valori adiacenti nell'elenco per modificare la tupla come:

$$ Left ( Left [X_1, X_2, CDOTS X_ {i-1}, (x_i + x_ {i + 1}), x_ {i + 2} CDots x_n destra], y + x_ {i } + x_ {i + 1} a destra) $$

Iterare fino a:

$$ Left ( Left [ Sum_i x_i a destra], y + z a destra) $$

Qual è il set ottimale di scelte che riducono al minimo $ z $?

Intuitivamente, non si desidera mai operare sul numero più grande nell'elenco. Ma il numero più grande in questo elenco cambia quando si aggiungono valori insieme. In altre parole, la soluzione ottimale non è necessariamente ottenuta da una soluzione ottimale di un sotto-problema.

Una soluzione avida inizierebbe prendendo il numero più piccolo in questo elenco e aggiungendolo al più piccolo dei suoi numeri adiacenti. Questa soluzione, sebbene chiusa, non è equivalente al valore restituito dalla ricerca della forza bruta. Ciò indica il fatto che alcuni passaggi localmente ottimali non sono ottimali a livello globale, il che potrebbe essere collegato al fatto che l'elemento più grande dell'elenco cambia man mano che i valori vengono sommati.