Zoptymalizowane miejsce na zmianę monety

Question

Biorąc pod uwagę wartość N, jeśli chcemy wprowadzić zmiany za N centów, a my mamy nieskończoną podaż każdej monety o wartości S = {S1, S2, .., Sm}, ile sposobów czy możemy dokonać zmiany? Kolejność monet nie ma znaczenia.

Na przykład dla N = 4 i S = {1,2,3} istnieją cztery rozwiązania: {1,1,1,1}, {1,1,2}, {2,2} , {1,3}. Zatem wynik powinien wynosić 4. Dla N = 10 i S = {2, 5, 3, 6}, istnieje pięć rozwiązań: {2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5} i {5,5}. Więc wynik powinien wynosić 5.

Znalazłem 3 podejścia HERE. Jednak nie jest w stanie zrozumieć zoptymalizowanego pod względem przestrzeni podejścia do programowania dynamicznego, w którym wykorzystywana jest tylko jednowymiarowa tablica tablic [].

int count(int S[], int m, int n) 
{ 
    // table[i] will be storing the number of solutions for 
    // value i. We need n+1 rows as the table is consturcted 
    // in bottom up manner using the base case (n = 0) 
    int table[n+1]; 

    // Initialize all table values as 0 
    memset(table, 0, sizeof(table)); 

    // Base case (If given value is 0) 
    table[0] = 1; 

    // Pick all coins one by one and update the table[] values 
    // after the index greater than or equal to the value of the 
    // picked coin 
    for(int i=0; i<m; i++) 
     for(int j=S[i]; j<=n; j++) 
      table[j] += table[j-S[i]]; 

    return table[n]; 
} 

Answer 1

Pierwsza uwaga, że ​​tabela [i] jest wiele sposobów na zmianę monety gdy N = I.

Podany algorytm wypełnia tę tablicę (tabela []) zgodnie z podanym zestawem monet (S []). Początkowo wszystkie wartości w tabeli [] zostały zainicjowane na 0. I tabela [0] ustawiona na 0 (jest to przypadek podstawowy N = 0).

Każda moneta sumuje wartości w tabeli [] w następujący sposób.

Na monety wartości X, są następujące aktualizacje tablicy [] -

1. tabeli [X] = tabeli [X] + 1

   ten jest łatwy do zrozumienia. W szczególności dodaje to rozwiązanie {X}.

2. wszystkie Y> X

   tabeli [T] = tabela [Y] + tabeli [Y-X]

   Jest to trudne do zrozumienia. Weźmy przykład X = 3 i rozważmy przypadek dla Y = 4.

   4 = 3 + 1, to znaczy 4 można uzyskać łącząc 3 i 1. Z definicji liczba sposobów na uzyskanie 1 to tabela [1]. Tak wiele sposobów jest dodanych do tabeli [4]. To dlatego powyższe wyrażenie używa tabeli [Y-X].

Po linia algorytmu oznacza takie same (ponad dwa etapy) -

table[j] += table[j-S[i]]; 

Po zakończeniu algorytmu tabeli [n] dla n zawiera roztwór.

Answer 2

Spróbuj zrozumieć algorytm w ten sposób.

table[i][j] oznacza używanie pierwszych monet o numerach i w celu zmiany wartości na wartość j. następnie:

table[i][j] = table[i-1][j] + table[i][j-S[i]]

Oczywiście kiedy tworzących j monety, masz dwie możliwości. nie używanie ith monety lub użycie i-tej monety. Gdy nie używa się ith monety, numer rozwiązania to table[i-1][j]. W przypadku użycia i-tej monety, numer rozwiązania to table[i][j-S[i]], co oznacza, że ​​za pomocą pierwszych monet i tworzy się wartość jS [i]. Dlatego suma jest sumą obu, która jest table[i-1][j] + table[i][j-S[i]]

W kodzie, ty zobaczy pętlę for. zewnętrzna pętla przechodzi przez I i wewnętrzna pętla przechodzi przez j. instrukcja += obliczyć table[i][j] na podstawie powyższego równania.

EDIT

table[j] w kodzie jest rzeczywiście table[i][j] mówię powyżej i jest wartością w pętli. po pętli table[N] oznacza table[M][N], reprezentujących przy użyciu pierwszych monet M, które są wszystkie monety, aby wartość dla N.

podam więcej szczegółów na podstawie kodu:

for(int i=0; i<m; i++) 
     for(int j=S[i]; j<=n; j++) 
      table[j] += table[j-S[i]]; 

Kiedy i = 0, table[j] znaczy stosowanie pierwszy 1 monety, aby dokonać zmian w wartości j. na przykład table[2] oznacza teraz używając coins {1} dokonać zmiany na 2. Tak więc:

table[1] = table[1] + table[1 - S[0]] = table[1] + table[0] = 1 + 0= 1 
table[2] = table[2] + table[2 - S[0]] = table[2] + table[1] = 0 + 1= 1 
table[3] = 1 
table[4] = 1 

Po tym, mamy wyniki, gdy = 0. table[1] ~ table[4] oznacza teraz używając coin {1} dokonać zmiany dla wartości 1, 2, 3, 4 osobno.

Gdy i = 1, table[j] oznacza użycie coin {1, 2} do wprowadzenia zmian dla wartości j.

table[2] = table[2] + table[2 - S[1]] = table[2] + table[0] = 1 + 1= 2 
table[3] = table[3] + table[3 - S[1]] = 1 + 1 = 2 
table[4] = table[4] + table[4 - S[1]] = table[4] + table[2] = 1 + 2 = 3 

Poniższy proces jest taki sam.

Wreszcie Bierzemy table[4] gdy i = 1 się i analizować go:

table[4] = table[4] + table[4 - S[1]] = table[4] + table[2] = 1 + 2 = 3 

Tutaj table[4] po lewej stronie jest wartością jesteśmy obliczania i rzeczywiście jest to table[i=1][4]. table[4] po prawej stronie przedstawia poprzednią wartość, w tym przypadku table[i=0][4]. To może rozwinąć do:

table[i=1][4] = table[i=0][4] + table[i=1][4 - S[1]] 

równanie ma dokładnie

table[i][j] = table[i-1][j] + table[i][j-S[i]] 

EDIT Follow-Up Pytanie

Jeśli uważasz, że naprawdę zrozumieć to pytanie, spróbuj rozwiązać ten sam problem z nowym przymus. A co, jeśli każdą monetę można wykorzystać tylko raz? Na przykład N = 4 i S = {1,2,3}, tylko jedno rozwiązanie {1,3}, więc wynik powinien wynosić 1. I dla N = 10 i S = {2, 5, 3, 6}, wciąż tylko jedno rozwiązanie {2, 3, 5}, a wyjście to 1.

Wskazówka: wystarczy jedna liniowa zmiana oryginalnego kodu.

Odpowiedź: http://ideone.com/t1JnEz