Lino il Giornalaio (task)

Aiuto
1

Ciao ragazzi. Non riesco a capire in che modo attraverso la programmazione dinamica si risolve il problema “Lino il Giornalaio”. Sulla guida del Prof. Alessandro Bugatti ho trovato questo algoritmo:

1 int monete[100];
2 int soluzioni[1001];
3 int N,R;
4
5 int main()
6 {
7 ifstream in(“input.txt”);
8 ofstream out(“output.txt”);
9 in >> N >> R;
10 for (int i=0;i<N;i++)
11 in >> monete[i];
12 for (int i=0; i<=R; i++)
13 soluzioni[i] = 0;
14 soluzioni[0]=1;
15 for (int i = 0; i < N; i++)
16 for (int j = 0; j <= R - monete[i]; j++)
17 soluzioni[j + monete[i]] = soluzioni[j + monete[i]] + soluzioni[j];
18 out << soluzioni[R];
19 return 0;
20 }

Non riesco a capire il modo in cui questo algoritmo calcoli il massimo numero di combinazioni di monete.

2

Lo fa semplicemente trovando TUTTE le combinazioni possibili per ogni possibile resto R usando le monete a disposizione.

Inizializza il caso base (R == 0) a 1 (c’è un solo modo per dare resto 0, non darlo) e poi costruisce le altre in bottomup. Per ogni moneta scorre tutto l’array delle soluzioni. Ad ogni R+monetaCorrente aggiunge il numero di soluzioni di R. Cioè se ci sono Q combinazioni di monete per dare un resto R, allora alla soluzione per il resto R+x (dove x è il valore di una moneta) vanno aggiunte tutte queste combinazioni.

Procedendo così per ogni moneta puoi avere la soluzione per il resto desiderato. Spero sia abbastanza chiaro

1 Mi Piace