Recuperare gli addendi che costituiscono la somma

posted Jun 7, 2011, 9:07 AM by r   [ updated Jun 24, 2011, 2:41 AM ]
Il problema è di recuperare gli addendi che costituiscono una somma partendo da un elenco di valori.

Una ottima soluzione VBA, che mi sento di consigliare, è quella proposta da Harlan Grove in una discussione che risale al 2005 (link). E' una procedura che consente di lavorare con un congruo numero di valori e ottenere il risultato in breve tempo. Il codice è ricco di spunti interessanti. Si fa uso delle regexp e di dictionary sono quindi necessari i riferimenti a librerie esterne. In alternativa è possibile modificare il codice utilizzando CreateObject per creare un'associazione tardiva.

Altra soluzione possibile è quella di utilizzare il Risolutore (link). Non la consiglierei perchè non offre flessibilità e sopratutto non restituisce un elenco di tutte le possibili combinazioni.

In questo articolo proporrò una soluzione con sole formule excel discussa nel Quizzone di Excel sull'NG (Quesito 20).

Può essere utilizzata con elenchi di valori ridotti (non più di 10-12 addendi).
Con un maggior numero di addendi il calcolo matriciale richiede molte risorse e i tempi di ricalcolo diventano proibitivi.
Nonostante questo limite è sicuramente una soluzione interessante che vale la pena di discutere.

La soluzione che propongo utilizza un'unica formula da trascinare a destra e in basso in un intervallo sufficiente a contenere tutte le possibili soluzioni.


Definiamo con un nome (rng) l'intervallo dinamico che contiene gli addendi, sia (come nel file di esempio scaricabile dal fondo della pagina) in A6 il primo addendo:

=$A$6:INDICE($A$6:$A$20;CONTA.VALORI($A$6:$A$20))

=$A$6:INDEX($A$6:$A$20,COUNTA($A$6:$A$20))

In altra parte del foglio la formula (valida per Excel 2003 e versioni successive):
=SE(RESTO(INT(GRANDE(SE(MATR.PRODOTTO(RESTO(INT(RIF.RIGA($A$1:INDICE($A:$A;2^RIGHE(rng)-1))/2^(RIF.COLONNA($A$1:INDICE($1:$1;;RIGHE(rng)))-1));2);rng)=$B$6;RIF.RIGA($A$1:INDICE($A:$A;2^RIGHE(rng)-1)));RIF.RIGA($A1))/2^(RIF.COLONNA(A1)-1));2);INDICE(rng;RIF.COLONNA(A$1));"")

=IF(MOD(INT(LARGE(IF(MMULT(MOD(INT(ROW($A$1:INDEX($A:$A,2^ROWS(rng)-1))/2^
(COLUMN($A$1:INDEX($1:$1,,ROWS(rng)))-1)),2),rng)=$B$6,ROW($A$1:INDEX($A:$A,2^
ROWS(rng)-1))),ROW($A1))/2^
(COLUMN(A1)-1)),2),INDEX(rng,COLUMN(A$1)),"")

che va confermata con Ctrl+Maiusc+Invio e trascinata a destra per un numero di colonne almeno pari al numero di addendi e in basso fino a quando restituirà valori di errore.

La formula di qui sopra non è utilizzabile con Excel 2003. Per questa versione è necessario dividere la formula o meglio è sufficiente utilizzare un nome per definire la matrice binaria.

Così definiamo il nome arr in questo modo:
=MATR.PRODOTTO(RESTO(INT(RIF.RIGA($A$1:INDICE($A:$A;2^RIGHE(rng)-1))/2^(RIF.COLONNA($A$1:INDICE($1:$1;;RIGHE(rng)))-1));2);rng)

=MMULT(MOD(INT(ROW($A$1:INDEX($A:$A,2^ROWS(rng)-1))/2^
(COLUMN($A$1:INDEX($1:$1,,ROWS(rng)))-1)),2),rng)

e modifichiamo la formula come segue (valida per tutte le versioni):
=SE(RESTO(INT(GRANDE(SE(arr=$B$6;RIF.RIGA($A$1:INDICE($A:$A;2^RIGHE(rng)-1)));RIF.RIGA($A1))/2^(RIF.COLONNA(A1)-1));2);INDICE(rng;RIF.COLONNA(A$1));"")

=IF(MOD(INT(LARGE(IF(arr=$B$6,ROW($A$1:INDEX($A:$A,2^ROWS(rng)-1))),ROW($A1))/2^
(COLUMN(A1)-1)),2),INDEX(rng,COLUMN(A$1)),"")

che come la precedente va confermata con Ctrl+Maiusc+Invio e trascinata a destra e in basso.

Il cuore della formula è proprio la matrice definita in arr e creata con MATR.PRODOTTO:
MATR.PRODOTTO(RESTO(INT(RIF.RIGA($A$1:INDICE($A:$A;2^RIGHE(rng)-1))/2^
(RIF.COLONNA($A$1:INDICE($1:$1;;RIGHE(rng)))-1));2);rng)

in particolare Matrice1 primo argomento della funzione:

RESTO(INT(RIF.RIGA($A$1:INDICE($A:$A;2^RIGHE(rng)-1))/2^
(RIF.COLONNA($A$1:INDICE($1:$1;;RIGHE(rng)))-1));2)

Questa restituisce una matrice rettangolare con le possibili disposizioni dei valori 0 e 1.
Nell'immagine qui sotto le possibili disposizioni quando il numero di addendi (posizioni) è 4:


In sostanza dove vi è 1 verrà *acceso* il relativo addendo lo 0 viceversa *spegnerà* il corrispondente valore.
MATR.PRODOTTO restituisce la somma sulle righe del prodotto tra la matrice di qui sopra e i valori degli addendi (rng), immaginiamo ora che gli addendi siano 1, 2, 3 e 4 si avrà:


la somma di ogni riga porta come risultato di MATR.PRODOTTO un vettore simile a quello nell'immagine qui sotto
Il resto della formula non fa altro che confrontare tali somme con il valore desiderato e mantenere quindi i risultati che soddisfano il problema.

Propongo anche la formula per contare quante sono le possibili soluzioni al problema:
=SOMMA(--(MATR.PRODOTTO(RESTO(INT(RIF.RIGA($A$1:INDICE($A:$A;2^RIGHE(rng)-1))/2^(RIF.COLONNA($A$1:INDICE($1:$1;;RIGHE(rng)))-1));2);rng)=B6))

=SUM(--(MMULT(MOD(INT(ROW($A$1:INDEX($A:$A,2^ROWS(rng)-1))/2^
(COLUMN($A$1:INDEX($1:$1,,ROWS(rng)))-1)),2),rng)=B6))

che va confermata con Ctrl+Maiusc+Invio.
ċ
r,
Jun 7, 2011, 9:21 AM
Ĉ
r,
Jun 14, 2011, 9:45 AM
Ĉ
r,
Jun 7, 2011, 1:31 PM
Comments