Ist das eine richtige Wiederholungsbeziehung, die ich für die Münzwechsel-Herausforderung gefunden habe?

Question

Ich versuche das "Münzwechsel-Problem" zu lösen und ich denke, ich habe eine rekursive Lösung gefunden, aber ich möchte es bestätigen.

Nehmen wir als Beispiel an, wir haben Pennies, Nickels und Groschen und versuchen, für 22 Cent zu ändern.

C = { 1 = penny, nickle = 5, dime = 10 } 
K = 22 

die Anzahl der Möglichkeiten Dann Änderung vorzunehmen ist

f(C,N) = f({1,5,10},22) 
= 
    (# of ways to make change with 0 dimes) 
+ (# of ways to make change with 1 dimes) 
+ (# of ways to make change with 2 dimes) 

= f(C\{dime},22-0*10) + f(C\{dime},22-1*10) + f(C\{dime},22-2*10) 
= f({1,5},22) + f({1,5},12) + f({1,5},2) 

und

f({1,5},22) 
= f({1,5}\{nickle},22-0*5) + f({1,5}\{nickle},22-1*5) + f({1,5}\{nickle},22-2*5) + f({1,5}\{nickle},22-3*5) + f({1,5}\{nickle},22-4*5) 
= f({1},22) + f({1},17) + f({1},12) + f({1},7) + f({1},2) 
= 5 

und so weiter.

Mit anderen Worten, ist mein Algorithmus wie

let f(C,K) be the number of ways to make change for K cents with coins C 
and have the following implementation 

if(C is empty or K=0) 
    return 0 
sum = 0 
m = C.PopLargest() 
A = {0, 1, ..., K/m} 
for(i in A) 
    sum += f(C,K-i*m) 
return sum 

Wenn es irgendeinen Fehler in das?

Wäre lineare Zeit, denke ich.

Answer 1

Rethink über Ihre Basis Fällen:

1. What if K < 0 ? Then no solution exists. i.e. No of ways = 0. 

2. When K = 0, so there is 1 way to make changes and which is to consider zero elements from array of coin-types. 

3. When coin array is empty then No of ways = 0. 

Rest der Logik ist korrekt. Aber Ihre Vorstellung, dass der Algorithmus linear ist, ist absolut falsch.

Läßt die Komplexität berechnen:

• Popping größte Element O (C.length). Dieser Schritt kann jedoch optimiert werden, wenn Sie das gesamte Array am Anfang sortieren.
• Ihre for-Schleife arbeitet O (K/C.max) mal in jedem Aufruf und in jeder Iteration ruft sie die Funktion rekursiv auf.

Also, wenn Sie die Wiederholung dafür schreiben.

T(N) = O(N) + K*T(N-1) 

Und dies wird sein exponentiell in Bezug auf N (Größe des Arrays): dann sollte es etwas ähnliches sein.

Wenn Sie nach Verbesserung suchen, würde ich vorschlagen, dass Sie dynamische Programmierung verwenden.