2015-10-19 32 views
6

Date due matrici A e B, ciascuno contenente n numeri non negativi, rimuovere a>0 elementi dalla fine di A e b>0 elementi da fine B. Valutare il costo di un'operazione come X*Y dove X è la somma degli elementi a rimossi da A e Y la somma degli elementi b rimossi da B. Continua a farlo finché entrambi gli array non sono vuoti. L'obiettivo è ridurre al minimo il costo totale.Dato 2 array di numeri non negativi, trovare la somma minima di prodotti

Utilizzo della programmazione dinamica e il fatto che una strategia ottimale richiede sempre esattamente un elemento da A o B È possibile trovare una soluzione O (n^3). Ora sono curioso di sapere se c'è una soluzione ancora più veloce a questo problema?

EDIT: Rubare un esempio @recursive nei commenti:

A = [1,9,1] e B = [1, 9, 1]. Possibile fare con un costo di 20. (1) * (1 + 9) + (9 + 1) * (1)

+0

Secondo me la soluzione dovrebbe selezionare gli ultimi due elementi di ciascun array sommarli e quindi aggiungere. Sopra). –

+0

Se ho torto, per favore chiarisci la dichiarazione del problema per me –

+0

Secondo la tua dichiarazione dobbiamo rimuovere dalla fine di A e alla fine di B –

risposta

4

Ecco O(n^2). Lascia che sia CostA(i, j) il costo minimo per eliminare A[1..i], B[1..j] in modo che la prima rimozione richieda solo un elemento da B. Sia il CostB(i, j) il costo minimo dell'eliminazione di A[1..i], B[1..j] in modo che la prima rimozione richieda un solo elemento da A. Abbiamo recidive mutuamente ricorsive

CostA(i, j) = A[i] * B[j] + min(CostA(i - 1, j), 
           CostA(i - 1, j - 1), 
           CostB(i - 1, j - 1)) 
CostB(i, j) = A[i] * B[j] + min(CostB(i, j - 1), 
           CostA(i - 1, j - 1), 
           CostB(i - 1, j - 1)) 

casi di base

CostA(0, 0) = 0 
CostA(>0, 0) = infinity 
CostA(0, >0) = infinity 
CostB(0, 0) = 0 
CostB(>0, 0) = infinity 
CostB(0, >0) = infinity. 

La risposta è min(CostA(n, n), CostB(n, n)).

+0

Grazie amico, quello era un releif. Fastidiosamente semplice! – user1337

+2

In realtà è necessario solo un 'Costo (i, j)' dove 'Costo (i, j) = A [i] * B [j] + min (Costo (i, j - 1), Costo (i - 1 , j), Costo (i - 1, j - 1)) ' – user1337

+0

Implementato e verificato entrambe le soluzioni. Posso confermare che funzionano correttamente. – Kenji

Problemi correlati