[excel] Risolvere il problema della somma di sottoinsiemi con il calcolo matriciale

Immaginiamo di avere una tabella con codici e importi e si voglia trovare la combinazione di codici la somma dei cui importi dia un importo cercato. Questo problema in informatica è noto come la ricerca della somma dei sottoinsiemi.

Prima di cominciare sottolineo che questa soluzione è pensata per Microsoft Office 365, che include le più recenti funzionalità di Excel che non sono disponibili in versioni precedenti.

Abbiamo quindi una tabella di codici e importi come la seguente:

E vogliamo permettere che si possa inserire un valore e trovare una combinazione di codici validi:

In questo caso abbiamo messo 1.400 e la combinazione dei codici F006 e H008 dà effettivamente come somma 1.400€

NOTA BENE: potrebbero esserci molteplici combinazioni che soddisfano lo stesso criterio, noi ne cerchiamo almeno 1

Anzitutto dobbiamo risolvere il problema di creare una lista (in realtà una matrice) di tutte le possibili combinazioni. Partiamo analizzando il problema nel modo più semplice: se avessimo solo tre elementi (chiamiamoli A, B e C) quante combinazioni potremmo avere?

Ad esempio potremmo avere ABC insieme, oppure solo AB o BC oppure AC, ecc. Come possiamo far fare questo calcolo a Excel? Ci può venire in aiuto la notazione binaria, dove vogliamo prendere tutti i numeri da 000 a 111 (che corrisponde a 7). Il numero 111 (ossia 7 in decimale) è l’ultimo numero di 2^3 – 1 (dove 3 è il numero di elementi). Potremmo quindi creare una lista binaria come la seguente:

0 = 000
1 = 001
2 = 010
3 = 011
4 = 100
5 = 101
6 = 110
7 = 111

Questo lo possiamo ottenere con la formula:

Il risultato sarà qualcosa del genere:

Per trasporre questi valori in riga scriviamo:

A questo punto abbiamo una matrice di 1 riga e 8 colonne, ossia 1×8. Al prossimo passaggio voglio estendere la cosa a n = 5 elementi anziché n = 3. Inoltre voglio separare le singole combinazioni in righe, su ciascuna colonna. In questo modo avremo una matrice 5×32 (5 righe per 32 colonne).

Il risultato (in espansione) sarà simile a questo:

Adesso ci basta moltiplicare la matrice 5×1 (una colonna di valori, ricordiamoci che ora ne stiamo prendendo solo 5) per la matrice ottenuta in precedenza:

Dove G8:G12 sono gli importi in questo modo:

Otterremo così un risultato come il seguente:

A questo punto abbiamo tutte le possibili combinazioni di valori.

Adesso si presenta il problema più complesso, ossia ridurre questa matrice da 5×32 a 1×32, praticamente una riga con valori uguali alla somma delle colonne della precedente matrice. Per ottenere questo risultato usiamo la funzione PERCOL (introdotta recentemente).

PERCOL accetta una funzione come secondo argomento, in questo caso applichiamo la funzione SOMMA.

Quello che otteniamo è un risultato simile a questo:

Adesso possiamo essere più felici che mai perché siamo ad un passo dalla soluzione. Ci basta costruire, in modo analogo la matrice con la concatenazione dei codici corrispondenti alle somme.

Per farlo applichiamo la funzione SE alla solita matrice binaria che abbiamo generato prima:

Dove l’intervallo F8:F12 è l’intervallo dei codici:

Usiamo di nuovo PERCOL, questa volta con la funzione MATRICE.A.TESTO.

E così abbiamo la sequenza di tutti i possibili codici. Non ci resta che utilizzare CERCA.X per cercare nella matrice degli importi e prendere l’equivalente combinazione di codici:

Questa volta estendiamo gli intervalli a tutti i codici e gli importi, nel modo seguente:

Cambiando l’ultimo parametro, la modalità di ricerca, possiamo decidere se farla a partire dal primo o dall’ultimo valore trovato.