Rekursion Bezahlwege Münzen

komat · 20. Dezember 2013 um 01:45

Hey, ich versuche einen rekursiven Algorithmus für das im Titel schon erwähnte Problem zu finden.

Also , ich möchte herausfinden auf wieviele verschiedene Wege ich einen Geldbetrag mit Münzen bezahlen kann.

Mir sind bisher nur ein paar Ansätze eingefallen,

Ich würde jede Münze als Variable in einen Array speichern.
Ich würde einen zweiten Array erstellen der beim Algorithmus die verschiedenen Kombinationen einspeichert.
Die Anzahl der vershceidenen Kombinationen bekomme ich dann einfach wenn ich die Länge des Arrays mit den Kombinationen ausgebe.

Allerdings fällt mir kein passender Algorithmus ein und wäre für ein paar Tipps dankbar

MfG Komat

SlaterB · 20. Dezember 2013 um 02:06

‚Bezahlwege‘ ist für google kein gutes Wort, wenig Ergebnisse, dein Thread wird bald auftauchen,
ich habe mir wie ersichtlich übrigens erlaubt, den Titel etwas zu kürzen

‚Rekursion geldbeträge münzen‘ findet schon mehr,
‚Münzproblem‘ taucht dann auch auf, hat zwar anscheinend auch andere Bedeutungen, aber lohnt trotzdem als weiterer Suchbegriff

damit findest du einiges fertiges/ genaueres, falls das dein Ziel ist,
ansonsten:
Algorithmen kann man nicht wie Blumen pfücken, einfach daran arbeiten, schlechtes korrigieren und langsam zum Ziel kommen,

Array ist richtig, Schleifen, rekursiver Aufruf, die Grundbausteine sind dir anscheinend bekannt,

oder vielleicht doch noch nötiger wichtigter Tipp, gleich Algorithmus quasi, jetzt wird es doch noch ne Menge:
a)
fange mit der höchsten Münze an, versuche soviele davon zu nehmen wie möglich/ vorhanden falls begrenzt,
und dann den evtl. Restbetrag mit den restlichen Münzen, neues Teilproblem genauso lösen, nur das bisherige merken,
welche Münzen schon im aktuellen Ergebnis, welche ausgeschlossen (Array-Index um 1 höher)

wenn mit evtl. zahllosen rekursiven Schritten fertig (ergeben sich erst aus Gesamtprogramm, vorerst ist es schlicht: der rekursive Aufruf),
dann wieder bei Situation/ auf Ebene a), da eine Münze wegnehmen und wieder rekursiver Aufruf

pro Ebene so lange bis keine Münzen mehr da,
und noch an das untere Ende denken, bei kleinster Münze aufhören, vollständige Ergebnisse auf jeder Ebene aufschreiben,

puh, das kann doch wirklich lang werden, lieber Lösungen anschauen

von Code-Lösungen abzuschreiben und korrekt anzupassen/ umzusetzen/ ausprobieren: 1 Punkt
von meinen Erklärungen zum Ziel kommen: 5 Punkte
selber darauf kommen wäre das eigentliche Ziel, 20 Punkte, aber wie nur, hmm…

CyborgBeta · 20. Dezember 2013 um 05:02

Hi, gerade noch rechtzeitig fertig geworden:

        if (s <= 0) {
            r2.add(r1);
            return;
        }
        for (int i : c) {
            if (s - i >= 0) {
                List<Integer> r3 = new ArrayList<Integer>(r1);
                r3.add(i);
                münzen(c, s - i, r3, r2);
            }
        }
    }

    public static List<List<Integer>> münzen(int[] c, int s) {
        List<List<Integer>> r = new ArrayList<List<Integer>>();
        münzen(c, s, Collections.EMPTY_LIST, r);
        return r;
    }

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
        System.out.println(rev("Hallo"));

        System.out.println(münzen(new int[]{2, 3, 1}, 9));
    }```

c: candidats,
s: sum,
r: result 1 bis 3,
münzen: muenzen (überschrieben, nicht verdeckt, nicht überladen; andere Sig.).

Zu verbessern:

- Besser HashSet<Integer, Integer> für die Indizes und die Anzahl der Münzen verwenden,
- Abbruchbedingung verfeinern (Wenn die Summe kleiner 0 ist, ist es dann ein Ergebnis?),
- muss r1 wirklich immer kopiert werden? (an dieser Stelle),
- int[] c absteigend sortieren (Ist 1 immer enthalten, kann Summe immer ausgezahlt werden?),
- Cents und Millicents verwenden, anstatt Fließkommazahlen
- usw.

system · 20. Dezember 2013 um 07:15

In Pseudocode

//Situation
Münzen = [5, 2, 1]
Betrag = 20

//Erster funktionsaufruf
f({}, 20, [5,2,1]) => (f({5}, 15, [5,2,1]), f({5},15,[2,1]))

//Daraus ergeben sich diese rekursiven Aufrufe
f({5}, 15, [5,2,1] => (f({5,5}, 10, [5,2,1], f({5,5},10, [2,1]))
f({5}, 15, [2,1] => (f({5,2}, 13, [2,1], f({5,2},13, [1]))
...


//Abbruchbedingungen
f(x, 0, [y]) => (x)

f(x, y<0, [z]) => {}

Also Aufruf der Methode mit einer Leeren Liste von Münzen dem Betrag und einer Liste von Münzen.
Nimm die erste Münze und ziehe sie vom Betrag ab, so daß du einen Restbetrag erhältst.

Nun lege die Münze zur Leeren Liste und Rufe die Methode mit dem Restbetrag und einmal mit und einmal ohne der Münze auf.

Tu dies solange der Restbetrag größer 0 ist.

Ist er 0, gib die Liste der Münzen, die zu diesem Betrag geführt haben zurück, ansonsten gib die Leere Liste zurück.

Das ist komplett rekursiv machbar so daß man auf jegliche Schleifen verzichten kann.

CyborgBeta · 20. Dezember 2013 um 07:49

Mir ist auch noch ein kritischer Fehler unterlaufen. Angenommen, Münzen 2 und 1, Summe 3, dann u. a. Ergebnis: (2,1) und (1,2). Um das zu vermeiden, noch einen Parameter/Argument idx mit schleppen, ab welcher Stelle Kandidaten aus c eingefügt werden sollen.

r1 bis r3 heißen übrigens akkumulierende Parameter (habe ich mal gelernt).

@Unregistered: Jede Schleife kann in Rekursion umgesetzt werden, keine Frage, aber ich glaube, ich weiß, was du meinst… Noch einen Parameter mitschleppen usw. Immer daran zu denken ist aber, dass rekursive Methodenaufrufe (in JAVA) immer ein bisschen Zeit kosten.

system · 20. Dezember 2013 um 09:56

import java.util.Arrays;
import java.util.List;

public class Coins {

    private final int[] coins;

    public Coins(final int[] coins) {
        this.coins = coins;
    }

    public List<int[]> change(int value) {
        return change(value, new int[coins.length], 0);
    }

    private List<int[]> change(int rest, int[] acc, int index) {
        if (rest == 0) {
            List<int[]> result = new ArrayList<int[]>();
            result.add(acc);
            return result;
        } else if (rest < 0 || index >= coins.length) {
            return new ArrayList<int[]>();
        } else {
            int coin = coins[index];
            int newRest = rest - coin;
            int[] newAcc = Arrays.copyOf(acc, acc.length);
            newAcc[index] = newAcc[index] + 1;
            if (newRest == 0) {
                List<int[]> result = new ArrayList<int[]>();
                result.add(newAcc);
                return result;
            } else {
                List<int[]> result = new ArrayList<int[]>();
                result.addAll(change(newRest, newAcc, index));
                result.addAll(change(newRest, newAcc, index + 1));
                return result;
            }
        }
    }

    public static void main(final String[] args) {
        long start = System.currentTimeMillis();
        int[] coins = new int[]{1, 2, 5, 10, 20, 50, 100};
        List<int[]> result = new Coins(coins).change(200);
        long end = System.currentTimeMillis();

        for (int[] amounts : result) {
            int sum = 0;
            for (int i = 0; i < coins.length; i++) {
                System.out.printf("%dx %d	", amounts**, coins**);

                sum += (amounts** * coins**);
            }
            System.out.println("= " + sum);
        }
        long end2 = System.currentTimeMillis();
        System.out.println("#Results " + result.size());
        System.out.printf("Time: %d  millis%n", (end - start));
        System.out.printf("Time: %d  millis%n", (end2 - start));
    }
}```

Die Berechnung geht immer noch wesentlich schneller als die Ausgabe des Ergebnisses. Zudem sei angemerkt, dass das Ergebnis dieser simplen Aufgabe 42.787 Ergebnisse hervorbringt.

CyborgBeta · 20. Dezember 2013 um 12:15

Warum machst du es nicht so, wie ich es beschrieben habe? Zu einfach?

system · 20. Dezember 2013 um 13:50

Nunja, ich bin nicht der TO.
Habe ich mich bei der Implementierung ein klein wenig vertan. Aber das ging dir ja genauso.

Es müsste heißen:

        if (rest < 0 || index >= coins.length) {
            return new ArrayList<int[]>();
        } else if (rest == 0) {
            List<int[]> result = new ArrayList<int[]>();
            result.add(acc);
            return result;
        } else {
            int coin = coins[index];
            int newRest = rest - coin;
            
            int[] newAcc = Arrays.copyOf(acc, acc.length);
            newAcc[index] = newAcc[index] + 1;
            
            List<int[]> result = new ArrayList<int[]>();
            result.addAll(change(newRest, newAcc, index));
            result.addAll(change(rest, acc, index + 1));
            return result;
        }
    }

Es ist nicht komplizierter, auch wenn es so aussehen mag. Aber Java fehlt hier mMn. etwas der Syntaktische Zucker, was dafür sorgt dass es etwas komplizierter erscheint.

Könntest du das mit dem index mal implementieren wie du es dir vorstellst, damit die Duplikate wegfallen.
(1,1,1,2)(1,1,2,1)(1,2,1,1)(2,1,1,1)
So wie es jetzt ist gibt es für die Münzen 1 und 2 und den Betrag 10946 Kombinationen heraus.

CyborgBeta · 20. Dezember 2013 um 16:04

Ich bessere das morgen aus. Objekterstellung spielt auch bei dir eine Rolle, die ist neben vielen rekursiven Methoden- oder Prozeduraufrufen auch “langsam”. Yow, Permutationen/Kombinationen gibt es dabei viele… zu viele…

*** Edit ***

Irgendwie braucht man dazu ein Bier… So… das ist zwar jetzt maximal unleslich geworden, aber es ist fix:

        if (s <= 0) {
            r2.add(r1.toArray(new Integer[r1.size()]));
            return;
        }
        for (; i < c.length; i++) {
            int ci = c**;
            int s2 = s - ci;
            if (s2 >= 0) {
                r1.add(ci);
                münzen(c, s2, i, r1, r2);
                r1.removeLast();
            }
        }
    }

    public static List<Integer[]> münzen(int[] c, int s) {
        List<Integer[]> r = new ArrayList<Integer[]>();
        münzen(c, s, 0, new ArrayDeque<Integer>(), r);
        return r;
    }

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        for (Integer[] integers : münzen(new int[]{2, 3, 1}, 9)) {
            for (Integer integer : integers) {
                System.out.printf("%-3d", integer);
            }
            System.out.printf("%n");
        }
    }```


Meine Ausgabe:
[spoiler]

run:
2 2 2 2 1
2 2 2 3
2 2 2 1 1 1
2 2 3 1 1
2 2 1 1 1 1 1
2 3 3 1
2 3 1 1 1 1
2 1 1 1 1 1 1 1
3 3 3
3 3 1 1 1
3 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
BUILD SUCCESSFUL (total time: 0 seconds)

[/spoiler]


Deque, insb. ArrayDeque, soll noch etwas schneller sein als ArrayList für Stack-/Queue-ähnliche Aufgaben.

Alle Verbesserungsvorschläge stehen ja schon oben.

system · 20. Dezember 2013 um 18:33

        final Collection<int[]> result = new ArrayDeque<>();
        change(result, value, new int[coins.length], 0);
        return result;
    }

    private void change(Collection<int[]> result, int rest, int[] acc, int index) {
        if (rest > 0 && index < coins.length) {
            int[] newAcc = Arrays.copyOf(acc, acc.length);
            newAcc[index] = newAcc[index] + 1;
            change(result, rest - coins[index], newAcc, index);
            change(result, rest, acc, index + 1);
        } else if (rest == 0) {
            result.add(acc);
        }
    }```

ArrayDeque schein einen vernünftigen Eindruck zu machen. Ich hab jetzt nur ein wenig die Reihenfolge geändert und gebe eine Collection zum speichern des Ergebnisses mit. Damit sieht das ganze doch schon halbwegs leserlich aus.

Wenn ich jetzt die Zeiten vergleiche sind diese garnicht mal so unterschiedlich. Mal ist das eine etwas schneller, mal das andere.
Ab einer bestimmten größe werfen beide ihre Stackover-Exception, wegen der Rekursionstiefe.

Was allerdings verschieden ist, ist das Ausgabeformat.

Bei mir kommt ein Array mit Koeffizienten zurück. Bei dir eine Liste mit den Werten.

Daher kann ich so ein Ergebnis produzieren.

Resultat
[spoiler]

run:
Dez 21, 2013 3:14:15 AM asimplejavaapplication.Coins main
Information: Coins [1, 3, 2]
Dez 21, 2013 3:14:15 AM asimplejavaapplication.Coins main
Information: Total 9
Dez 21, 2013 3:14:15 AM asimplejavaapplication.Coins main
Information: 9x 1 0x 3 0x 2 = 9
Dez 21, 2013 3:14:15 AM asimplejavaapplication.Coins main
Information: 7x 1 0x 3 1x 2 = 9
Dez 21, 2013 3:14:15 AM asimplejavaapplication.Coins main
Information: 6x 1 1x 3 0x 2 = 9
Dez 21, 2013 3:14:15 AM asimplejavaapplication.Coins main
Information: 5x 1 0x 3 2x 2 = 9
Dez 21, 2013 3:14:15 AM asimplejavaapplication.Coins main
Information: 4x 1 1x 3 1x 2 = 9
Dez 21, 2013 3:14:15 AM asimplejavaapplication.Coins main
Information: 3x 1 2x 3 0x 2 = 9
Dez 21, 2013 3:14:15 AM asimplejavaapplication.Coins main
Information: 3x 1 0x 3 3x 2 = 9
Dez 21, 2013 3:14:15 AM asimplejavaapplication.Coins main
Information: 2x 1 1x 3 2x 2 = 9
Dez 21, 2013 3:14:15 AM asimplejavaapplication.Coins main
Information: 1x 1 2x 3 1x 2 = 9
Dez 21, 2013 3:14:15 AM asimplejavaapplication.Coins main
Information: 1x 1 0x 3 4x 2 = 9
Dez 21, 2013 3:14:15 AM asimplejavaapplication.Coins main
Information: 0x 1 3x 3 0x 2 = 9
Dez 21, 2013 3:14:15 AM asimplejavaapplication.Coins main
Information: 0x 1 1x 3 3x 2 = 9
Dez 21, 2013 3:14:15 AM asimplejavaapplication.Coins main
Information: #Results 12
Dez 21, 2013 3:14:15 AM asimplejavaapplication.Coins main
Information: Time: 1 millis

[/spoiler]



Wenn jetzt allerdings eine Eingabe mit mehreren Münzen 
[1,2,5,10] kommt und auf 800 rausgegeben werden soll, dann geht das mit der Implementierung, während deine mit OutofMemory daherkommt.

Das ist auch Verständlich, da es 882.441 Kombinationen gibt und das Format
[800,0,0,0] Platzsparender daherkommt als [1,1,1,...1].

Zudem Denke ich nicht dass sich die Anzahl der Methodenaufrufe groß Unterscheidet. Wenn man allerdings keine Rekursive Lösung haben möchte (entgegen dem Titel des Threads), dann kann man auch alles in einer Methode unterbringen und sich viele Methodenaufrufe sparen.

CyborgBeta · 21. Dezember 2013 um 02:55

Was hältst du hiervon:

 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package javaapplication1;

import java.util.ArrayList;
import java.util.Collection;

/**
 * @author CBBB
 */
public class JavaApplication1 {

    private static String rev(String s) {
        if (s.isEmpty()) {
            return s;
        }
        return rev(s.substring(1)) + s.charAt(0);
    }

    private static void münzen(int[] c, int[] r1, Collection<int[]> r2, int s, int i) {
        if (s <= 0) {
            int[] r3 = new int[r1.length];
            System.arraycopy(r1, 0, r3, 0, r1.length);
            r2.add(r3);
            return;
        }
        for (; i < c.length; i++) {
            int ci = c**;
            int s2 = s - ci;
            if (s2 >= 0) {
                r1**++;
                münzen(c, r1, r2, s2, i);
                r1**--;
            }
        }
    }

    public static ArrayList<int[]> münzen(int[] c, int s) {
        ArrayList<int[]> r = new ArrayList<int[]>();
        münzen(c, new int[c.length] /* wichtig!!! */, r, s, 0);
        return r;
    }

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
        System.out.println(rev("Hallo"));

        for (int[] is : münzen(new int[]{2, 3, 1}, 9)) {
            for (int i = 1; i < 4; i++) {
                System.out.printf("%3d", i % 3 + 1);
            }
            System.out.printf("%n");
            for (int i : is) {
                System.out.printf("%3d", i);
            }
            System.out.printf("%n%n");
        }
    }
}```


Ausgabe neu:
[spoiler]

run:
ollaH
2 3 1
4 0 1

2 3 1
3 1 0

2 3 1
3 0 3

2 3 1
2 1 2

2 3 1
2 0 5

2 3 1
1 2 1

2 3 1
1 1 4

2 3 1
1 0 7

2 3 1
0 3 0

2 3 1
0 2 3

2 3 1
0 1 6

2 3 1
0 0 9

BUILD SUCCESSFUL (total time: 0 seconds)

[/spoiler]


Das enthält doch syntaktisch Zucker, oder? Die Aufrufe sollten auch nicht zu viele werden, für "gewöhnliche" Größen von Sum etc. Ansonsten halt vollständig ohne Rekursion, wie aber nicht der Aufgabenstellung zu entnehmen isss.

Bezeichner:
c = coins
s = sum
r.... = results
i = index for coins
ci = current coin
s2 = new sum
münzen = muenzen = two methods (declared as private and public)
etc.

Bin erst mal raus aus dem Thema. Bis BAld.

Landei · 21. Dezember 2013 um 10:29

[QUOTE=CyborgBeta]
Bezeichner:
c = coins
s = sum
r… = results
i = index for coins
ci = current coin
s2 = new sum
münzen = muenzen = two methods (declared as private and public)
etc.[/QUOTE]

Warum nennst du die Variablen dann nicht **gleich **so? Kosten die paar Tastendrücke was extra?

CyborgBeta · 21. Dezember 2013 um 17:23

Tastenanschläge kosten eig. keine Euronen. Aber ich bin mir nicht sicher, ob’s dann nicht unübersichtlicher wird, unverständlicher und nicht entsprechend des Algos ist. Vor- und Nachteile? Pros und Contras? Mathem. schreiben meist doch auch nicht mehr als 3 Buchstabenß?

anon94273153 · 22. Dezember 2013 um 02:50

Ich empfehle mal “Clean Code” zu lesen.

anon2594669 · 22. Dezember 2013 um 02:59

Clean Code kann ich da auch nur empfehlen.

Ein Beispiel: Du liest den Code in 2 Monaten noch mal und weißt vermutlich nicht mehr, wofür die Variablen stehen. Oder eine andere Person möchte diesen Code verstehen und kann es nicht.

Landei · 22. Dezember 2013 um 05:15

Die Tradition kurzer Variablennamen kommt noch aus den Anfängen der Programmierung, wo Variablennamen wirklich beschränkt waren (Fortran, BASIC), nur die ersten paar Buchstaben berücksichtigt wurden (Pascal) oder Variablen mit längeren Namen langsamer verarbeitet wurden. Das kann heute kein Kriterium mehr sein.

Code sollte lesbar und selbsterklärend sein. Überlange Bezeichner sind schlecht lesbar, zu kurze Bezeichner sind nicht selbsterklärend, es gilt also, die “goldene Mitte” zu finden. Wie Sym schon schrub, muss man aber daran denken, dass es nicht nur darum geht, den Code **jetzt **verstehen zu können, sondern auch später, oder von anderen Leuten, also sollte man im Zweifelsfall lieber etwas großzügiger mit der Beschreibung sein.

Auch der jeweilige Kontext spielt eine wichtige Rolle. Wenn ich z.B. in mehreren Packages eine Klasse “Address” habe, ist das schlecht, auch wenn der Name zusammen mit dem jeweiligen Package “selbsterklärend” wäre. Aber schon der Import-Mechanismus von Java würde so eine Lösung zweifelhaft machen. Hat man dagegen “Address” als innere Klasse von mehreren Entities, sieht das wieder anders aus, denn ein Name wie “Bank.Address” ist genauso eindeutig wie, aber besser lesbar als z.B. “Bank.BankAddress”. Insgesamt gilt: Je “öffentlicher” ein Bezeichner ist, je größer sein Sichtbarkeitsbereich ist, um so mehr Gedanken sollte man sich um Eindeutigkeit, Lesbarkeit und Verständlichkeit machen. Das heißt, dass ein “i” als Schleifenvariable in Ordnung gehen kann, aber schon nicht mehr als Methodenargument.

Natürlich sollte man nicht in Dogmatismus verfallen, es können z.B. gewisse Konventionen existieren, die eine Abkürzung erlauben. Ein enum LengthUnit {M, CM, MM, FT, IN}; kann in einem entsprechenden Umfeld genauso aussagekräftig wie enum LengthUnit {METER, CENTIMETER, MILLIMETER, FOOT, INCH}; sein. Trotzdem sollte man im Zweifel die eindeutlige Variante bevorzugen. Dank Autovervollständigung in allen modernen IDEs ist die zusätzliche Tipparbeit jedenfalls kein Argument mehr für unverständliche Abkürzungen.