Seite 4 von 4 ErsteErste 1234
Ergebnis 46 bis 55 von 55

Thema: [PDW 9] Geldwechsel

  1. #46
    Moderator
    Registriert seit
    May 2002
    Beiträge
    653
    Renommee
    1014

    Re: [PDW 9] Geldwechsel

    Nochmal etwas Cheaten (Constraint - Anfrage bei SWI/SICStus, Beispiel von DarkTom https://www.buha.info/board/showpost...&postcount=2):
    Zur Veranschaulichung noch ein Beispiel:

    Eingabe:
    Münzwerte: 1, 5, 10, 20
    Betrag: 108

    Ausgabe:
    Anzahl Münzen: 9
    Zerlegung: 3, 1, 0, 5

    denn 108 = 3*1 + 1*5 + 0*10 + 5*20 und diese Stückelung ist optimal.
    Code:
    ?- use_module(library(clpfd)).                                                
    yes                                                                             
    | ?- _L=[_V,_X,_Y,_Z],domain(_L,0,108),
    _V*1+_X*5+_Y*10+_Z*20#=108,
    findall(sum(Sum,_V,_X,_Y,_Z),(labeling([ff],_L),Sum is _X+_Y+_Z+_V),_Sums),
    sort(_Sums,[sum(Anz,Eins,Fuenf,Zehn,Zwanzig)|_]).
    Ausgabe:

    Anz = 9,
    Eins = 3,
    Zehn = 0,
    Fuenf = 1,
    Zwanzig = 5,
    _V in 3..108,
    _X in 0..21,
    _Y in 0..10,
    _Z in 0..5 ?
    Edit: SWI möchte statt domain(_L,0,108) lieber _L ins 0..108 haben.
    Geändert von CDW (22.08.2008 um 10:37 Uhr) Grund: SWI Lib
    Selig, wer nichts zu sagen hat und trotzdem schweigt!

  2. #47
    Moderator
    Registriert seit
    Jun 2001
    Beiträge
    1.327
    Renommee
    846

    Re: [PDW 9] Geldwechsel

    Willkommen OkeanosTom!
    Zitat Zitat von OkeanosTom Beitrag anzeigen
    kam auf folgende Lösung zu der ich gerne mal wüsste ob die so stimmt.
    Leider nein. Im Wesentlichen verfolgst du den Greedy-Ansatz, den z.B. mdk in Post 5 widerlegt. Zwar erweiterst du ihn leicht, indem du eine Greedylösung für mehrere Münzkombinationen berechnest und davon die beste auswählst, aber das hilft auch nicht weiter. Man muss das Beispiel von mdk nur leicht variieren und schon sollte dein Algorithmus scheitern:

    Münzen: 1, 9, 10, 50
    Betrag: 68


    Übrigens hätte ich mir an deiner Stelle die 1 Minute mehr Zeit für die Ausgabe schon genommen, damit du wenigstens die berechneten Ergebnisse siehst. Das einfachste wäre wohl ein
    Code:
    import java.util.Arrays
    
    class Muenzen {
    ...
            int[] erg = hwnd.berechne(33);
            System.out.println(Arrays.toString(erg));
    ...
    Aktuelle Probleme der Doppelwoche:
    [29 Logik] Fahnenjagd

  3. #48
    Registered User
    Registriert seit
    Aug 2008
    Beiträge
    2
    Renommee
    27

    Re: [PDW 9] Geldwechsel

    ersteinmal Danke für Deine Antwort.

    Ich habe das Programm mal mit Deinen Werten durchlaufen lassen und kam auf folgende stuckelung:
    8x1
    0x9
    1x10
    1x50

    Das ist doch auch die optimal Lösung denk ich mal.
    Welcher Lösungs Ansatz wäre denn deiner Meinung nach für dieses Problem der richtige?

    MfG

    OkeanosTom

  4. #49
    Moderator
    Registriert seit
    Jun 2001
    Beiträge
    1.327
    Renommee
    846

    Re: [PDW 9] Geldwechsel

    Optimal wäre 1x50, 2x9.

    Lösungen, die das Problem - wenn auch ineffizient - lösen, findest du ja hier im Thread. Ich bin immer noch gespannt, ob jemand die Lösung findet, die keinen exponentiellen sondern einen pseudopolynomiellen Aufwand hat.
    Aktuelle Probleme der Doppelwoche:
    [29 Logik] Fahnenjagd

  5. #50
    Registered User
    Registriert seit
    Apr 2007
    Beiträge
    28
    Renommee
    84

    Re: [PDW 9] Geldwechsel

    Ich sitz schon eine ganze Weile an dem Problem aber erst jetzt bin ich zu einer, meiner Meinung nach, guten Lösung gekommen.
    Der Algorithmus läuft in etwa so ab:
    1. Die beste Münzverteilung für den Betrag m=0 (ist klar, 0)
    2. Prüfe die beste Möglichkeit für m=m+1, aus den vorher berechneten Möglichkeiten und einer weiteren Münze
    3. Wiederhole 2. solange bis m=Gewünschter Betrag


    Bei mir sieht die Ausgabe dann so aus:
    Code:
    $ time for i in "108 1 5 10 20" "18 1 9 10" "28 1 9 10" "18 1 4 5" "6662 230 306 392 410 574 750 780 850" "68 1 9 10 50" ; do ./wechselgeld $i ; done
    3x1 + 1x5 + 0x10 + 5x20 = 108 (9 Muenzen)
    0x1 + 2x9 + 0x10 = 18 (2 Muenzen)
    0x1 + 2x9 + 1x10 = 28 (3 Muenzen)
    0x1 + 2x4 + 2x5 = 18 (4 Muenzen)
    2x230 + 0x306 + 1x392 + 0x410 + 0x574 + 0x750 + 2x780 + 5x850 = 6662 (10 Muenzen)
    0x1 + 2x9 + 0x10 + 1x50 = 68 (3 Muenzen)
    
    real    0m0.042s
    user    0m0.028s
    sys     0m0.006s
    Code:
    #include <iostream>
    #include <vector>
    #include <cstdlib>
    
    using namespace std;
    
    int change(vector<int> &l, int v)
    {
    	vector<vector<int> > best(v + 1, vector<int>(l.size() + 1, 0));
    
    	for (int i = 1; i <= v; ++i) {
    		best[i][0] = v + 1; // over maximum value
    		for (int k = 0; k < l.size(); ++k) {
    			if (i >= l[k]) {
    				if (best[i - l[k]][0] + 1 < best[i][0]) {
    					best[i] = best[i - l[k]];
    					best[i][0]++; // total number of coins
    					best[i][k + 1]++; // number of coins with value
    				}
    			}
    		}
    	}
    	if (best[v][0] > v)
    		cout << "Keine Loesung" << endl;
    	else {
    		for (int t = 0; t < l.size() + 1; ++t)
    			cout << best[v][t + 1] << "x" << l[t] <<  " + ";
    	
    		cout << "\b\b= " << v << " (" << best[v][0] << " Muenzen)" << endl;
    	}
    }
    
    int main(int argc, char *argv[])
    {
    	int value;
    	vector<int> coins;
    
    	value = atoi(argv[1]);
    
    	for (int i = 2 ; i < argc; ++i)
    		coins.push_back(atoi(argv[i]));
    
    	change(coins, atoi(argv[1]));
    
    	return 0;
    }
    Bin mir nicht ganz sicher, wegen der Laufzeit. Aber ich denke er hängt linear vom Betrag und quadratisch von der Anzahl an Münzarten ab.
    Speichermäßig von beiden linear.

  6. #51
    Registered User
    Registriert seit
    Jan 2006
    Beiträge
    492
    Renommee
    760

    Re: [PDW 9] Geldwechsel

    Zitat Zitat von lagalopex Beitrag anzeigen
    Code:
    2x230 + 0x306 + 1x392 + 0x410 + 0x574 + 0x750 + 2x780 + 5x850 = 6662 (10 Muenzen)
    2x230 + 0x306 + 1x392 + 0x410 + 0x574 + 0x750 + 2x780 + 5x850 = 6662 (10 Muenzen)
    0x230 + 0x306 + 2x392 + 0x410 + 2x574 + 3x750 + 1x780 + 2x850 = 6662 (10 Muenzen)

    prima Sache!

    Kann man eigentlich vorab abschätzen wie viele richtige Lösungen in etwa zu erwarten sind?

    FG
    GRip

  7. #52
    Registered User
    Registriert seit
    Apr 2007
    Beiträge
    28
    Renommee
    84

    Re: [PDW 9] Geldwechsel

    Man könnte im Test immer gucken, ob es noch andere Münzkombinationen mit der gleichen minimalen Anzahl gibt und die jeweils mit speichern.

    Das ist dann aber (verhältnismäßig) langsam... aber möglich
    (Mit dem regelmäßigen sortieren und löschen von Dublikaten wird folgende Ausgabe in weit unter einer Sekunde generiert.)

    Code:
    0x230 + 0x306 + 0x392 + 1x410 + 3x574 + 5x750 + 1x780 + 0x850 = 6662 (10 Muenzen)
    0x230 + 0x306 + 1x392 + 0x410 + 5x574 + 0x750 + 0x780 + 4x850 = 6662 (10 Muenzen)
    0x230 + 0x306 + 1x392 + 2x410 + 0x574 + 5x750 + 0x780 + 2x850 = 6662 (10 Muenzen)
    0x230 + 0x306 + 2x392 + 0x410 + 2x574 + 3x750 + 1x780 + 2x850 = 6662 (10 Muenzen)
    0x230 + 2x306 + 0x392 + 1x410 + 0x574 + 1x750 + 3x780 + 3x850 = 6662 (10 Muenzen)
    2x230 + 0x306 + 1x392 + 0x410 + 0x574 + 0x750 + 2x780 + 5x850 = 6662 (10 Muenzen)

  8. #53
    Moderator
    Registriert seit
    Jun 2001
    Beiträge
    1.327
    Renommee
    846

    Re: [PDW 9] Geldwechsel

    Damit hat sich auch die optimale Lösung gefunden. Die Laufzeit beträgt O(n*B) bei n Münzarten und gesuchten Betrag B und ist somit pseudopolynomiell.

    Der Lösungsansatz fällt übrigens unter das Konzept der sogenannten dynamischen Programmierung.

    Man kann darauf verzichten, die Münzanzahlen der Zwischenergebnisse mitzuspeichern. Um die für das finale Ergebnis zu berechnen, müsste man nur nochmal die erstellte Tabelle durchgehen, bei einem Laufzeitaufwand von O(n * Wert der Lösung).
    Aktuelle Probleme der Doppelwoche:
    [29 Logik] Fahnenjagd

  9. #54
    Registered User
    Registriert seit
    Apr 2001
    Beiträge
    449
    Renommee
    95

    Re: [PDW 9] Geldwechsel

    Ich habe nicht viel Ahnung von Informatik, aber wie kommt man darauf, dass das die optimale Lösung ist, dass es also keine bessere geben kann?

  10. #55
    Moderator
    Registriert seit
    Jun 2001
    Beiträge
    1.327
    Renommee
    846

    Re: [PDW 9] Geldwechsel

    Zitat Zitat von lulu Beitrag anzeigen
    Ich habe nicht viel Ahnung von Informatik, aber wie kommt man darauf, dass das die optimale Lösung ist, dass es also keine bessere geben kann?
    Ach Mist, die Frage hatte ich ganz vergessen. Ich hätte doch direkt antworten sollen, aber damals war ich gerade unterwegs...


    Grundsätzlich lassen sich so Sachen beweisen, häufig indem man das Problem auf ein anderes zurückführt, von dem man weiss, dass es nicht schneller zu lösen ist. Informationen dazu findest du unter dem Stichwort Komplexitätstheorie.

    In diesem konkreten Fall ist mir allerdings kein Beweis bekannt. Ich habe da etwas unvorsichtig formuliert. Die "beste der informatischen Welt bekannte Lösung" wäre eine bessere Wahl gewesen.
    Aktuelle Probleme der Doppelwoche:
    [29 Logik] Fahnenjagd

Aktive Benutzer

Aktive Benutzer

Aktive Benutzer in diesem Thema: 1 (Registrierte Benutzer: 0, Gäste: 1)

Ähnliche Themen

  1. Antworten: 4
    Letzter Beitrag: 31.05.2013, 23:00

Berechtigungen

  • Neue Themen erstellen: Nein
  • Themen beantworten: Nein
  • Anhänge hochladen: Nein
  • Beiträge bearbeiten: Nein
  •