Szukaj…


Liczba sposobów na uzyskanie sumy

Biorąc pod uwagę monety o różnych nominałach i sumę, na ile sposobów możemy połączyć te monety, aby uzyskać sumę? Powiedzmy, że mamy coins = {1, 2, 3} a w total = 5 , możemy uzyskać sumę na 5 sposobów:

  • 1 1 1 1 1
  • 1 1 1 2
  • 1 1 3
  • 1 2 2
  • 2 3

Problem jest ściśle związany z problemem plecaka. Jedyną różnicą jest to, że mamy nieograniczoną podaż monet. Użyjemy programowania dynamicznego, aby rozwiązać ten problem.

Użyjemy tablicy 2D dp [n] [razem + 1], gdzie n jest liczbą różnych nominałów monet, które mamy. W naszym przykładzie potrzebujemy dp [3] [6] . Tutaj dp [i] [j] będzie oznaczać liczbę sposobów, w jakie możemy uzyskać j , gdybyśmy mieli monety od monet [0] do monet [i] . Na przykład dp [1] [2] zapisze, jeśli mamy monety [0] i monety [1] , na ile sposobów możemy zrobić 2 . Zaczynajmy:

W przypadku dp [0] [0] zadajemy sobie pytanie, czy mieliśmy tylko 1 nominał monety, czyli monety [0] = 1 , na ile sposobów możemy uzyskać 0 ? Odpowiedź jest 1 sposób, który jest, jeśli nie podejmiemy żadnej monety w ogóle. Idąc dalej, dp [0] [1] będzie reprezentować, gdybyśmy mieli tylko monety [0] , na ile sposobów możemy uzyskać 1 ? Odpowiedź brzmi ponownie 1 . W ten sam sposób dp [0] [2] , dp [0] [3] , dp [0] [4] , dp [0] [5] będzie wynosić 1 . Nasza tablica będzie wyglądać następująco:

     +---+---+---+---+---+---+---+
(den)|   | 0 | 1 | 2 | 3 | 4 | 5 |
     +---+---+---+---+---+---+---+
 (1) | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
     +---+---+---+---+---+---+---+
 (2) | 1 |   |   |   |   |   |   |
     +---+---+---+---+---+---+---+
 (3) | 2 |   |   |   |   |   |   |
     +---+---+---+---+---+---+---+

W przypadku dp [1] [0] zadajemy sobie pytanie, czy mieliśmy monety 2 nominałów, to znaczy, czy mieliśmy monety [0] = 1 i monety [1] = 2 , na ile sposobów możemy zrobić 0 ? Odpowiedź to 1 , czyli brak przyjmowania monet. W przypadku dp [1] [1] , ponieważ monety [1] = 2 są większe niż nasza obecna suma, 2 nie przyczyni się do uzyskania sumy. Wykluczymy więc 2 i policzymy liczbę sposobów uzyskania sumy za pomocą monet [0] . Ale ta wartość jest już zapisana w dp [0] [1] ! Więc weźmiemy wartość z góry. Nasza pierwsza formuła:

if coins[i] > j
    dp[i][j] := dp[i-1][j]
end if

W przypadku dp [1] [2] , na ile sposobów możemy uzyskać 2 , gdybyśmy mieli monety o nominałach 1 i 2 ? Możemy zrobić 2 używając monet o nominale 1 , które jest reprezentowane przez dp [0] [2] , ponownie możemy wziąć 1 nominał 2, który jest przechowywany w dp [1] [2-monety [i]] , gdzie i = 1 . Dlaczego? Będzie to oczywiste, jeśli spojrzymy na następny przykład. W przypadku dp [1] [3] , na ile sposobów możemy uzyskać 3 , gdybyśmy mieli monety o nominałach 1 i 2 ? Możemy wykonać 3 za pomocą monet o nominale 1 na 1 sposób, które są przechowywane w dp [0] [3] . Teraz, jeśli weźmiemy 1 nominał z 2 , będziemy potrzebować 3 - 2 = 1, aby uzyskać sumę. Liczba sposobów uzyskania 1 za pomocą monet o nominale 1 i 2 jest przechowywana w dp [1] [1] , który można zapisać jako dp [i] [j-monety [i]] , gdzie i = 1 . Dlatego zapisaliśmy poprzednią wartość w ten sposób. Nasza druga i ostatnia formuła będzie:

if coins[i] <= j
    dp[i][j] := dp[i-1][j] + dp[i][j-coins[i]]
end if

To dwie wymagane formuły do wypełnienia całej tablicy dp . Po wypełnieniu tablica będzie wyglądać następująco:

     +---+---+---+---+---+---+---+
(den)|   | 0 | 1 | 2 | 3 | 4 | 5 |
     +---+---+---+---+---+---+---+
 (1) | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
     +---+---+---+---+---+---+---+
 (2) | 1 | 1 | 1 | 2 | 2 | 3 | 3 |
     +---+---+---+---+---+---+---+
 (3) | 2 | 1 | 1 | 2 | 3 | 4 | 5 |
     +---+---+---+---+---+---+---+

dp [2] [5] będzie zawierać naszą wymaganą odpowiedź. Algorytm:

Procedure CoinChange(coins, total):
n := coins.length
dp[n][total + 1]
for i from 0 to n
    dp[i][0] := 1
end for
for i from 0 to n
    for j from 1 to (total + 1)
        if coins[i] > j
            dp[i][j] := dp[i-1][j]
        else
            dp[i][j] := dp[i-1][j] + dp[i][j-coins[i]]
        end if
    end for
end for
Return dp[n-1][total]

Złożoność czasowa tego algorytmu wynosi O(n * total) , gdzie n jest liczbą posiadanych przez nas nominałów monet.

Minimalna liczba monet, aby uzyskać sumę

Biorąc pod uwagę monety o różnych nominałach i sumę, ile monet musimy połączyć, aby uzyskać sumę, jeśli użyjemy minimalnej liczby monet? Powiedzmy, że mamy coins = {1, 5, 6, 8} a w total = 11 , możemy uzyskać sumę za pomocą 2 monet, czyli {5, 6} . Jest to rzeczywiście minimalna liczba monet wymaganych do zdobycia 11 . Zakładamy również, że istnieje nieograniczona podaż monet. Użyjemy programowania dynamicznego, aby rozwiązać ten problem.

Użyjemy tablicy 2D dp [n] [razem + 1], gdzie n jest liczbą różnych nominałów monet, które mamy. W naszym przykładzie potrzebujemy dp [4] [12] . W tym przypadku dp [i] [j] będzie oznaczać minimalną liczbę monet potrzebną do uzyskania j , gdybyśmy mieli monety od monet [0] do monet [i] . Na przykład dp [1] [2] zapisze, jeśli mieliśmy monety [0] i monety [1] , jaka jest minimalna liczba monet, których możemy użyć do zrobienia 2 . Zaczynajmy:

Początkowo dla 0 kolumny można uzyskać 0 , nie biorąc wcale monet. Zatem wszystkie wartości 0 kolumny będą wynosić 0 . W przypadku dp [0] [1] zadajemy sobie pytanie, czy mieliśmy tylko 1 nominał monety, czyli monety [0] = 1 , jaka jest minimalna liczba monet potrzebna do uzyskania 1 ? Odpowiedź to 1 . W przypadku dp [0] [2] , gdybyśmy mieli tylko 1 , jaka jest minimalna liczba monet potrzebnych do uzyskania 2 . Odpowiedź to 2 . Podobnie dp [0] [3] = 3 , dp [0] [4] = 4 i tak dalej. Należy tu wspomnieć, że jeśli nie mielibyśmy monety o nominale 1 , mogą istnieć przypadki, w których sumy nie można osiągnąć za pomocą tylko 1 monety. Dla uproszczenia bierzemy 1 w naszym przykładzie. Po pierwszej iteracji nasza tablica dp będzie wyglądać następująco:

        +---+---+---+---+---+---+---+---+---+---+---+---+---+
 (denom)|   | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11|
        +---+---+---+---+---+---+---+---+---+---+---+---+---+
    (1) | 0 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11|
        +---+---+---+---+---+---+---+---+---+---+---+---+---+
    (5) | 1 | 0 |   |   |   |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+---+---+---+---+---+
    (6) | 2 | 0 |   |   |   |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+---+---+---+---+---+
    (8) | 3 | 0 |   |   |   |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+---+---+---+---+---+

Idąc dalej, w przypadku DP [1] [1] zadajemy sobie pytanie, czy mieliśmy monety [0] = 1 i monety [1] = 5 , jaka jest minimalna liczba monet potrzebnych do uzyskania 1 ? Ponieważ monety [1] są większe niż nasza obecna suma, nie wpłynie to na nasze obliczenia. Musimy wykluczyć monety [5] i zdobyć 1 za pomocą monet [0] tylko. Ta wartość jest przechowywana w dp [0] [1] . Tak więc bierzemy wartość z góry. Nasza pierwsza formuła to:

if coins[i] > j
    dp[i][j] := dp[i-1][j]

Ten warunek będzie spełniony, dopóki nasza suma nie będzie wynosić 5 w dp [1] [5] , w takim przypadku możemy wykonać 5 na dwa sposoby:

  • Bierzemy 5 nominałów monet [0] , które są przechowywane na dp [0] [5] (od góry).
  • Przyjmujemy 1 nominał monet [1] i ( 5 - 5 ) = 0 nominałów monet [0] .

Wybierzemy minimum tych dwóch. Więc dp [1] [5] = min ( dp [0] [5] , 1 + dp [1] [0] ) = 1 . Dlaczego wspomnieliśmy o 0 nominałach monet [0] tutaj będzie widoczne na naszej następnej pozycji.

Dla dp [1] [6] możemy zrobić 6 na dwa sposoby:

  • Bierzemy 6 nominałów monet [0] , które są przechowywane na górze.
  • Możemy wziąć 1 nominał 5 , potrzebujemy 6 - 5 = 1, aby uzyskać sumę. Minimalna liczba sposobów uzyskania 1 za pomocą monet o nominale 1 i 5 jest przechowywana w dp [1] [1] , który można zapisać jako dp [i] [j-monety [i]] , gdzie i = 1 . Właśnie dlatego tak zapisaliśmy poprzednią wartość.

Przyjmiemy minimum tych dwóch sposobów. Zatem naszą drugą formułą będzie:

if coins[i] >= j
    dp[i][j] := min(dp[i-1][j], dp[i][j-coins[i]])

Za pomocą tych dwóch formuł możemy wypełnić cały stół. Nasz końcowy wynik to:

        +---+---+---+---+---+---+---+---+---+---+---+---+---+
 (denom)|   | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11|
        +---+---+---+---+---+---+---+---+---+---+---+---+---+
    (1) | 0 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11|
        +---+---+---+---+---+---+---+---+---+---+---+---+---+
    (5) | 1 | 0 | 1 | 2 | 3 | 4 | 1 | 2 | 3 | 4 | 5 | 2 | 3 |
        +---+---+---+---+---+---+---+---+---+---+---+---+---+
    (6) | 2 | 0 | 1 | 2 | 3 | 4 | 1 | 1 | 2 | 3 | 4 | 2 | 2 |
        +---+---+---+---+---+---+---+---+---+---+---+---+---+
    (8) | 3 | 0 | 1 | 2 | 3 | 4 | 1 | 1 | 2 | 1 | 2 | 2 | 2 |
        +---+---+---+---+---+---+---+---+---+---+---+---+---+

Nasz wymagany wynik zostanie zapisany w dp [3] [11] . Procedura będzie:

Procedure coinChange(coins, total):
n := coins.length
dp[n][total + 1]
for i from 0 to n
    dp[i][0] := 0
end for
for i from 1 to (total + 1)
    dp[0][i] := i
end for
for i from 1 to n
    for j from 1 to (total + 1)
        if coins[i] > j
            dp[i][j] := dp[i-1][j] 
        else
            dp[i][j] := min(dp[i-1][j], dp[i][j-coins[i]])
        end if
    end for
end for
Return dp[n-1][total]

Złożoność tego algorytmu w środowisku wykonawczym wynosi: O (n * ogółem), gdzie n jest liczbą nominałów monet.

Aby wydrukować potrzebne monety, musimy sprawdzić:

  • jeśli wartość pochodzi z góry, bieżąca moneta nie jest uwzględniana.
  • jeśli wartość pochodzi od lewej, obecna moneta jest uwzględniana.

Algorytm wyglądałby następująco:

Procedure printChange(coins, dp, total):
i := coins.length - 1
j := total
min := dp[i][j]
while j is not equal to 0
    if dp[i-1][j] is equal to min
        i := i - 1
    else
        Print(coins[i])
        j := j - coins[i]
    end if
end while

W naszym przykładzie kierunek będzie następujący:

Tablica kierunkowa

Wartości będą wynosić 6 , 5 .



Modified text is an extract of the original Stack Overflow Documentation
Licencjonowany na podstawie CC BY-SA 3.0
Nie związany z Stack Overflow