[Algoritmi] Subset sum

[ZfreS]

Buonasera. Da un po di giorni studio il problema della subset sum. Ho prima visto la versione col backtracking che è stata abbastanza intuitiva da capire, poi sono passato alla versione che sfrutta la programmazione dinamica. Questa non riesco proprio a capirla. Ho che bisogna identificare dei sottoproblemi tra loro correlati, ma mentre in un problema come quello dei numeri di Fibonacci è chiaro dall'albero di ricorsione quali siano i sottoproblemi ripetuti, in questo caso non mi sembra evidente. Poi non capisco cosa faccia questa equazione di ricorrenza:
$DP[i][j]=DP[i-1][j] || DP[i-1][j-A[i-1]]$.
Sapreste spiegarmi a cosa serva e in cosa consistono i sottoproblemi di cui è composto questo problema?

[apatriarca]

In linea generale quando l'input è formato da un array/lista/sequenza si considerano i sottoinsiemi formati dai primi \(i\) elementi per ogni \(i\). Qui hai due indici perché è l'input è formato da un array di array.. Ma l'idea è la stessa.

[ZfreS]

Penso di aver capito come funziona questo algoritmo, ma mi è sorto un dubbio su un altro problema che è il seguente: data ua tabella $3xn$ trovare tutti i modi di riempirla usando tessere $2x1$. L'equazione ricorsiva è questa: $F(N)= F(n-2)+2G(n-1)$ $G(N)=F(n-1)+g(n-2$ dove $F(n)$ indica il numero di modi di piazzare le tessere in una tabella completa, mentre $G(n)$ è il numero di modi di piazzare le tessere in una tabella in cui manca o un angolo destro altro o destro basso. Ora capisco il perchè la $F(n)$ sia definita in quel modo, ma non capisco il perchè di definire $G(n)$ così.

[apatriarca]

Non sono sicuro di aver compreso la tua situazione. Le tessere possono essere ruotate (e quindi usi tessere \(2 \times 1\) e \(1 \times 2\)? Se così non fosse ogni colonna sarebbe indipendente dalle altre e non potresti riempire la tabella perché ad ogni colonna mancherebbe una cella. A questo punto però che cosa intendi con manca un angolo destro alto o basso? Una singola cella in alto o in basso?

Sinceramente in questi casi ti conviene fare dei disegni e cercare di visualizzare quelle formule caso per caso.