Zrozumienie zmiana podejmowania algorytm

Question

szukałem dobrego rozwiązania Change-making problem i znalazłem ten kod (Python):

target = 200 
coins = [1,2,5,10,20,50,100,200] 
ways = [1]+[0]*target 
for coin in coins: 
    for i in range(coin,target+1): 
     ways[i]+=ways[i-coin] 
print(ways[target]) 

mam żadnych problemów ze zrozumieniem tego, co robi kod dosłownie, ale nie mogę zrozum, DLACZEGO to działa. Ktoś może pomóc?

Answer 1

Aby uzyskać wszystkie możliwe zestawy, które elementy są równe „A” lub „B” lub „C” (nasze monety), które sumują się do „X” można:

• Take wszystkie takie zestawy, które sumować do Xa i dodać do każdej z nich dodatkowe "a".
• Weź wszystkie takie zestawy, które sumują się do X-b i dodaj do każdej z nich dodatkowe "b".
• Weź wszystkie takie zestawy, które sumują się do X-c i dodaj do każdej z nich dodatkowe "c".

Liczba sposobów, w jakie można uzyskać X, jest sumą liczb sposobów, w jakie można uzyskać X-a i X-b oraz X-c.

ways[i]+=ways[i-coin] 

Odpoczynek jest prostym nawrotem.

Dodatkowa wskazówka: na początku można się ustawić z sumy zerowej dokładnie jeden sposób (zbiór pusty)

ways = [1]+[0]*target 

Answer 2

ten jest klasycznym przykładem dynamic programming. Korzysta z buforowania, aby uniknąć pułapki liczenia rzeczy, takich jak 3 + 2 = 5 dwukrotnie (z powodu innego możliwego rozwiązania: 2 + 3). Algorytm rekurencyjny wpada w tę pułapkę. Skupmy się na prostym przykładzie, gdzie target = 5 i coins = [1,2,3].Kawałek kodu, który pisał powodów:

1. 3 + 2
2. 3 + 1 + 1
3. 2 + 2 + 1
4. 1 + 2 + 1 + 1
5. 1 + 1 + 1 + 1 + 1

natomiast rekurencyjne wersja liczy:

1. 3 + 2
2. 2 + 3
3. 3 + 1 + 1
4. 1 + 3 + 1
5. 1 + 1 + 3
6. 2 + 1 + 2
7. 1 + 1 + 2
8. 2 + 2 + 1
9. 2 + 1 + 1 + 1
10. 1 + 2 + 1 + 1
11. 1 + 1 + 2 + 1
12. 1 + 1 + 1 + 2
13. 1 + 1 + 1 + 1 + 1

kod rekurencyjne:

coinsOptions = [1, 2, 3] 
def numberOfWays(target): 
    if (target < 0): 
     return 0 
    elif(target == 0): 
     return 1 
    else: 
     return sum([numberOfWays(target - coin) for coin in coinsOptions]) 
print numberOfWays(5) 

Programowanie dynamiczne:

target = 5 
coins = [1,2,3] 
ways = [1]+[0]*target 
for coin in coins: 
    for i in range(coin, target+1): 
     ways[i]+=ways[i-coin] 
print ways[target] 

Answer 3

Ideą kodu jest następujący: " Na każdym kroku dostępne są ways sposoby na zmianę i kwoty pieniędzy podanych monet [1,...coin] ".

Tak więc w pierwszej iteracji masz tylko monetę o nominale 1. Uważam, że oczywiste jest, że istnieje tylko jeden sposób, aby zmienić tylko monety na dowolny cel. Na tym etapie tablica będzie wyglądać następująco: [1,...1] (tylko jeden sposób dla wszystkich obiektów docelowych od 0 do target).

W następnym kroku dodajemy monetę o nominale 2 do poprzedniego zestawu monet. Teraz możemy obliczyć, ile kombinacji zmian istnieje dla każdego celu od 0 do target. Oczywiście liczba kombinacji zwiększy się tylko dla celów> = 2 (lub w ogóle w przypadku dodania nowej monety). Tak więc, jeśli cel wynosi 2, liczba kombinacji będzie wynosić ways[2](old) + ways[0](new). Generalnie, za każdym razem, gdy i równa się nowej wprowadzonej monecie, musimy dodać 1 do poprzedniej liczby kombinacji, gdzie nowa kombinacja będzie składać się tylko z jednej monety.

Dla target>2, odpowiedź będzie składać się z sumy „wszystkie kombinacje target ilości posiadające wszystkie monety mniej niż coin” i „wszystkie kombinacje coin ilości posiadające wszystkie monety mniej niż sama coin”.

Tutaj opisałem dwa podstawowe kroki, ale mam nadzieję, że łatwo je uogólnić.

Pokażę ci obliczeniowej drzewo dla target = 4 i coins=[1,2]:

sposoby [4] Podane monety = [1,2] =

sposoby [4] Podane monety = [1] + sposób [2] podane monety = [1,2] =

1 + sposób [2] podane monety = [1] + sposoby [0] podane monety = [1,2] =

1 + 1 + 1 = 3

Istnieją trzy sposoby zmiany: [1,1,1,1], [1,1,2], [2,2].

Powyższy kod jest całkowicie równoważny rozwiązaniu rekursywnemu. Jeśli rozumiesz the recursive solution, założę się, że rozumiesz rozwiązanie podane powyżej.

Answer 4

Zamieszczone rozwiązanie jest streszczoną wersją tego kodu.

/// <summary> 
    /// We are going to fill the biggest coins one by one. 
    /// </summary> 
    /// <param name="n"> the amount of money </param> 
    public static void MakeChange (int n) 
    { 
     int n1, n2, n3; // residual of amount after each coin 
     int quarter, dime, nickel; // These are number of 25c, 10c, 5c, 1c 
     for (quarter = n/25; quarter >= 0; quarter--) 
     { 
      n1 = n - 25 * quarter; 
      for (dime = n1/10; dime >= 0; dime--) 
      { 
       n2 = n1 - 10 * dime; 
       for (nickel = n2/5; nickel >= 0 && (n2 - 5*nickel) >= 0; nickel--) 
       { 
        n3 = n2 - 5 * nickel; 
        Console.WriteLine("{0},{1},{2},{3}", quarter, dime, nickel, n3); // n3 becomes the number of cent. 
       } 
      } 
     } 
    }