Seite 3 von 4 ErsteErste 1234 LetzteLetzte
Ergebnis 31 bis 45 von 55

Thema: [PDW 9] Geldwechsel

  1. #31
    Mastermind in Training
    Registriert seit
    Mar 2001
    Beiträge
    1.552
    Renommee
    727

    Re: [PDW 9] Geldwechsel

    So, hier der Code. Wie gesagt, es ist irgendwo ein Fehler und leider noch nicht Kommentiert. Kamm nicht dazu.

    neon
    Angehängte Dateien Angehängte Dateien
    Eine Zeitung wirbt mit "Bild dir deine Meinung". Mir wäre es lieber, wenn die Menschen weniger Meinung und dafür mehr Ahnung hätten.

  2. #32
    Registered User
    NewYearsChallenge Sieger 2010

    Registriert seit
    Oct 2002
    Beiträge
    730
    Renommee
    444

    Re: [PDW 9] Geldwechsel

    @destructor
    Hmm, bei Münzen 1, 9, 10 und Wert 28 gibt der aber nicht drei aus, oder? ...
    Verdammt - daran habe ich überhaupt nicht gedacht...
    Ich habe ansich denselben Code wie Neon ihn beschrieben hat, nur dass ich genau AnzahlDerMünzen-1 mal alles durchprüfe und eben nicht versuche ob's mit einer geringeren Anzahl der höchsten auch geht...

    Ganz schön trickreich dieses Problem ...
    destructor

  3. #33
    Moderator
    Registriert seit
    Jan 2001
    Beiträge
    419
    Renommee
    55

    Re: [PDW 9] Geldwechsel

    Hallo PDWler,

    Gut mein erster Vorschlag war hässlich und falsch und schlecht erklärt. Da war ich auch im Stress.

    Im Anhang mein neuer Vorschlag, schöner und besser. Ich bitte um Beispiele wo der nicht funktioniert. mir fallen keine mehr ein.

    Also wei gesagt konstruiere ich, wie schon andere das versuchen alle Möglichkeiten und bewerte die beste. Da ich ein kleiner Fan von Rekursionen bin, hab ich das eben im Kern mit einer for Schleifen die alle Möglichkeiten für den aktuellen Münzentyp durchläuft und einem Rekursiven Aufruf zum nächst niedrigeren Typ implementiert.

    mfg
    Angehängte Dateien Angehängte Dateien
    • Dateityp: zip PDW.zip (743 Bytes, 54x aufgerufen)
    Work smarter, not longer

  4. #34
    Registered User
    Registriert seit
    Feb 2008
    Beiträge
    1
    Renommee
    33

    Re: [PDW 9] Geldwechsel

    Ich hoffe, es ist in Ordnung, wenn ich den Thread aus seiner Versenkung hochhole. Da ich das Thema sehr interessant fand, habe ich mich auch mal an einer Lösung versucht inkl. einigen Erläuterungen.
    Ich habe auch mal die Lösung von Bunny ausprobiert (da ich mein Programm auch in Ruby geschrieben habe) und glaube, dass da noch ein Fehler steckt.
    Beispiel: Münzen: 1,4,5 Wert: 18
    Die Ausgabe des Programms:
    Anzahl Münzen:6
    Zerlegung:2*1, 4*4, 0*5,
    Die optimale Zerstückelung wäre dagegen: 0x1 2x4 2x5

    Jetzt zu meinem Programm:
    Ich habe das Problem versucht auf ein paar unterschiedliche Weisen zu lösen, der Lösung liegt jeweils ein Graph zu Grunde.

    1. Variante
    Der 1. Graph schaut folgendermaßen aus (a, b, und c stehen für Münzwerte)

    Nun wird der Baum traversiert (mit einer Tiefen- oder Breitensuche) und nach den Elementen durchsucht, deren Summe dem Betrag entspricht. Hier ein Überblick über die Implementierung:

    Tiefensuche (http://en.wikipedia.org/wiki/Depth-first_search)
    Hierbei füge ich alle gefundenen Knoten in eine Liste ein. Diese Liste wird nach dem Suchvorgang (und einigen Umformungen) sortiert, sodass die Ergebnisse mit der geringsten Münzanzahl vorne stehen.

    Breitensuche (http://en.wikipedia.org/wiki/Breadth-first_search)
    Bei der Breitensuche wird nur der erste Fund verwendet. Da die Ebenen nacheinander abgesucht werden (und die Tiefe im Baum gleichbedeutend mit der Anzahl der Münzen ist), ist der erste Fund auch der optimale (auch wenn es nicht ausgeschlossen ist, dass es noch weitere Knoten gibt, die genausogut sind)

    Die Codeabschnitte sind nur Teile aus dem Quellcode und alleine nicht lauffähig:
    Code:
    # Depth-first search
    def dfs(matches, node = Array.new, sum = 0)
        if sum == @amount
            matches.push(node)
            return
        elsif sum > @amount
            return
        else
            @coins.each do |coin|
                dfs(matches, node.dup.push(coin), sum + coin)
            end
        end
    end
    
    # Breadth-first search
    def bfs
        queue = [[]]
        while true
            node = queue.shift
            return [] if node == nil  # nothing found
            
            if( node.sum == @amount )
                return node
            elsif (node.sum < @amount )
                @coins.each do |coin|
                    queue.push( node.dup.push(coin) )
                end
            end
        end
    end
    2. Variante


    Die Knoten des Baums stellen jetzt nicht mehr die Münzen selber dar, sondern die Anzahl einer bestimmten Sorte Münze.
    Einer der dargestellten Pfade (root--0--2--2) würde also bedeuten: 0xa,2xb,2xc. Um die zum Betrag passenden Kombinationen auszuwählen wird auch hier wieder eine Tiefensuche eingesetzt. Entspricht die Summe (im Beispiel: 0xa + 2xb + 2xc) dem Betrag, wird diese Kombination wieder in einer Liste abgespeichert.

    Code:
    # Depth-first search
    # Finds all possible distributions that yield the specified amount 
    def dfs(matches, depth = 0, sum = 0, path = Array.new )
        if sum == @amount and depth == @coins.size
            matches.push(path)
            return
        end
        
        coin = @coins[depth]
        return if coin == nil
        
        i = 0
        sum.step(@amount, coin) do |sum|
            dfs(matches, depth + 1, sum, path.dup.push(i))
            i += 1	
        end
    end
    Hier mal ein Beispielergebnis aus meinem Programm:
    Code:
    Please enter the values of the coins (in the form a,b,c)
    1,4,5
    Please enter the amount
    18
      0x1   2x4   2x5   4
      1x1   3x4   1x5   5
      2x1   4x4   0x5   6
      3x1   0x4   3x5   6
      4x1   1x4   2x5   7
      5x1   2x4   1x5   8
      6x1   3x4   0x5   9
      8x1   0x4   2x5   10
      9x1   1x4   1x5   11
     10x1   2x4   0x5   12
     ... (3 more results)
    Angehängte Dateien Angehängte Dateien

  5. #35
    Registered User
    Registriert seit
    Jan 2006
    Beiträge
    492
    Renommee
    760

    Re: [PDW 9] Geldwechsel

    Ich kann leider nicht so gut Programmieren, von daher setze ich für sowas auf das Excel AddIn Solver

    Zitat:

    Microsoft Excel 2000 Solver verwendet den Generalized Reduced Gradient (GRG2) Algorithmus für das Optimieren nicht linearer Probleme.

    http://support.microsoft.com/kb/214115

    Keine Ahnung ob jemand soetwas wie den GRG2 in Ruby oder Perl umsetzen kann bei mir sind es zwei Tabellenblätter als Beispiel.

    Bildausschnitte:







    Zum kontrollieren ob mit einem selbst erstellten Programm das optimale Ergebnis gefunden wurde, könnte Excel aber hilfreich sein.

    FG
    GRip

  6. #36
    Moderator
    Registriert seit
    Jul 2000
    Beiträge
    3.763
    Renommee
    1214

    Re: [PDW 9] Geldwechsel

    du Bescheisser xD

  7. #37
    Registered User
    Registriert seit
    Jan 2006
    Beiträge
    492
    Renommee
    760

    Re: [PDW 9] Geldwechsel

    wenn der thread schon aus der versenkung geholt wurde, fände ich es viel interessanter die aufgabe so umzustellen das nicht die münzwerte sondern die münzgewichte betrachtet werden.

    also gewicht x soll mit so wenig wie möglich münzen realisiert werden!

    66,62 g kann ich zum beispiel mit 10 münzen realisieren.

    wer weniger als 10 münzen braucht vor dem mache ich den virtuellen kniefall !

    wer dasselbe ergebnis mit einem selbst erstellten programm findet
    geniesst selbstverständlich meinen allergrössten respekt!!!


    die münzgewichte sind genormt die werte stimmen so wie in der tabelle zu sehen sind.



    FG
    GRip

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

    Re: [PDW 9] Geldwechsel

    Ich find's gut, dass das Thema mal wiederbelebt wird.

    Es scheint auch so, als wäre die optimale Lösung noch nicht gefunden, wobei ich da nochmal die exisiterenden durchgucken müsste. Die neue von JimmyX ist jedenfalls letztlich nur eine Brute-Force-Variante, aber sehr schön präsentiert.

    @grip:
    Ob du es Betrag oder Gewicht nennst, ändert nichts an dem Problem.
    Aktuelle Probleme der Doppelwoche:
    [29 Logik] Fahnenjagd

  9. #39
    Registered User
    Registriert seit
    Jan 2006
    Beiträge
    492
    Renommee
    760

    Re: [PDW 9] Geldwechsel

    ich habe festgestellt das es nur lösungen gibt für schrittweiten von 0,02 g
    oder anders ausgedrückt eine lösung für 66,63 g scheint es nicht zu geben bei meinem beispiel.
    von daher ist es zwar im grundprinzip aber im detail nicht egal ob man die tatsächlichen münzgewichte oder beliebige münzwerte zugrundelegt...

  10. #40
    Registered User
    Registriert seit
    Apr 2001
    Beiträge
    449
    Renommee
    95

    Re: [PDW 9] Geldwechsel

    ist das nicht auf den ersten blick ersichtlich? es gibt ja nur zwei münzen die irgendetwas mit hundertstel gramm wiegen und beide haben geradzahlige hundertstel. dass man daraus keine 3/100 g basteln kann ist logisch.

  11. #41
    Registered User
    Registriert seit
    Jan 2006
    Beiträge
    492
    Renommee
    760

    Re: [PDW 9] Geldwechsel

    jo, sag ich doch ;-) es sind allerdings 3 münzen mit hunderstel gramm im gewicht ändert aber nichts daran das du recht hast.
    als differenzgewicht auf einer balkenwaage lassen sich also beliebige werte ab 0,02 g aufwärts
    und einer schrittweite von 0,02 g mit minimaler münzzahl darstellen.

    aber gut, insgesamt bleibt es natürlich dasselbe optimierungsproblem unabhängig davon wie die aufgabenstellung nun konkret formuliert ist.


  12. #42
    Registered User
    Registriert seit
    Jan 2006
    Beiträge
    492
    Renommee
    760

    Re: [PDW 9] Geldwechsel

    Die nichtlinearen Optimierungscodes GRG2 und VF13AD kommen unter anderem zur Lösung der Aufgabe in Frage.

    -> User's Guide for GRG2 Optimization Library

    -> Download GRG2VB Project (291KB self-extracting zip file, Grg2ezvb.EXE).

    kann leider nicht so gut Programmieren sorry, deswegen hier nur der Hinweis auf Quellen...

  13. #43
    Registered User
    Registriert seit
    Jan 2006
    Beiträge
    492
    Renommee
    760

    Re: [PDW 9] Geldwechsel

    verschiedene solver für das lösen des Problems incl. Quellcode in C findet man hier...

    http://www.ampl.com/solvers.html

  14. #44
    Moderator
    Registriert seit
    May 2002
    Beiträge
    653
    Renommee
    1014

    Re: [PDW 9] Geldwechsel

    Vornweg: beide Lösungen sind reines BF:

    SWI-Prolog[1], primitiv
    Spoiler:

    Code:
    combo(_,Max,Acc,Acc):- sumlist(Acc,Max).
    combo(Type,Max,Acc,Res):- sumlist(Acc,Sum),Sum=<Max,
              member(Coin,Type),
              combo(Type,Max,[Coin|Acc],Res).
    
    solve(Cointypes,Sum):-
              findall(solution(Len,Sol),(combo(Cointypes,Sum,[],Sol),
                      length(Sol,Len)),Solutions),
              sort(Solutions,[solution(Len,Result)|_]),
              format('Loesung: Anzahl ~k, Muenzen: ~q',[Len,Result]).
    Kommentar:
    "combo" generiert aus gegebenen Münztypen erstmal alle möglichen Lösungen:
    liest sich auch als:
    Lösung: wenn Summe der Kombination=Zielwert
    ansonsten: sofern die Summe der jetztigen Kombination kleiner ist, kann
    eine Münze aus den gegebenen Typen zur Kombination dazugehören,

    solve sucht erstmal alle Lösungen für die gegebenen Münztypen zusammen,
    ermittelt deren Länge, sortiert nach der Länge und gibt dann die erste (kürzeste) Lösung aus.

    Schön kurz und relativ gut lesbar - allerdings liefert hier 'combo' alle Permutationen einer Lösung und eignet sich daher eher nur als Gegencheck für andere Lösungen

    Das ist die optimierte Variante (allerdings nicht mehr auf Anhieb lesbar):
    Spoiler:
    Code:
    single_combo(_,Max,[],Max):- Max>=0.
    single_combo(Coin,Max,[Coin|Res],Remains):- Max>=0,New is Max-Coin,
             single_combo(Coin,New,Res,Remains).
    
    combo([],Max,_,Acc,Acc):- sumlist(Acc,Max).
    combo([Coin|Type],Max_all,Max_tail,Acc,Res):- 
             single_combo(Coin,Max_tail,List,Rest),
             append(Acc,List,New),
             combo(Type,Max_all,Rest,New,Res).
    
    solve(Cointypes,Sum):-
             findall(result(Len,Res),(combo(Cointypes,Sum,Sum,[],Res),
                     length(Res,Len)),Results),
             sort(Results,[result(Len,Res)|_]),
             format('Loesung: Anzahl ~k, Muenzen: ~q',[Len,Res]).
    Kommentar:
    "Single_combo" liefert zu einem Wert die möglichen Kombinationen, also z.B
    1,1,1,1,1
    1,1,1,1
    1,1,1
    1,1
    1
    und den verbleibenden "Freibetrag".
    Das eigentliche "combo" hat eine Endrekursion (daher wird ein Accumulator verwendet)
    Liest sich als:
    Sofern keine Münztypen mehr verfügbar sind und die Summe der Kombination=Ziel -> eine Lösung.
    Sonst: nehme eine Kombination für einen Münztyp (und zwar mit dem Zielwert="Freibetrag"="Max_tail") - diese kann zusammen mit der schon vorhandenen Teilliste eine Lösung ergeben (->rekursiver Aufruf zur Prüfung).

    Der "solve" Teil ist identisch mit dem ersten.

    beide Varianten starbar mit:
    solve([Münztyp,Münztyp],Zielbetrag).
    Bps:
    16 ?- solve([1,9,10],18).
    Loesung: Anzahl 2, Muenzen: [9, 9]
    Hier wird nur eine Kombination geprüft, ohne die Permutationen überhaupt zu generieren.
    Die zweite Variante ist also _wesentlich_ perfomanter. Ich weiß zwar nicht, wie es im Vergleich zu den anderen Lösungen steht, aber z.B grips Münzenbeispiel (in diesem Fall sind Gewichte die Münztypen):
    Welcome to SWI-Prolog (Multi-threaded, 32 bits, Version 5.6.55)

    60 ?- time(solve([850,750,780,574,410,392,306,230],6662)).
    Loesung: Anzahl 10, Muenzen: [750, 750, 750, 750, 750, 780, 574, 574, 574, 410]

    % 12,737,543 inferences, 5.66 CPU in 5.88 seconds (96% CPU, 2251941 Lips)
    true.
    6 Sek auf einem mit 980Mhz Core2Duo - und das mit SWI-Prolog (SICStus sollte noch deutlich besser laufen).


    [1]SICStus wird über das fehlende "sumlist" meckern (ist ein SWI-Built-In) - der Dreizeiler sollte aber kein Problem darstellen .
    Geändert von CDW (16.08.2008 um 02:18 Uhr)
    Selig, wer nichts zu sagen hat und trotzdem schweigt!

  15. #45
    Registered User
    Registriert seit
    Aug 2008
    Beiträge
    2
    Renommee
    27

    Re: [PDW 9] Geldwechsel

    Hallo,

    also ich bin neu hier und habe mir mal den Thread durchgelesen. Da ich dachte das das Problem rel. einfach zu lösen ist hab ich mich mal rangesetzt. mein ansatz war folgender:

    Ges.: n aus P wobei n die minimale Münzenanzahl ist und P die Menge aller Lösungen.

    Das ganze hab ich dann Iterativ gelöst zwecks laufzeit und kam auf folgende Lösung zu der ich gerne mal wüsste ob die so stimmt. Quellcod in Java:

    Code:
    public class muenzen
    
    	{
                    //Münz Stücke erstellen
    		int w[] = {1,2,5,9,10,20,50};
                    //ergebniss Array das die Anzahl der jeweiligen Münzstücke enthält
    		int erg[] = {0,0,0,0,0,0,0};
                    //ergebniss gesammt anzahl der Münzen
    		int Anzahl = 32000;
    		private int i=0;
    		public int[] berechne(int uebbetrag)
    		{
                            // Schleife die alle münzen von der höchstwertigsten beginnend durchläuft
    			for (i=w.length - 1 ; i>=0 ; i--)
    			{
                                    //Temporäres ergeniss Array
    				int tmparray[]={0,0,0,0,0,0,0};
                                    //Temporäre Münzenanzahl
    				int tmpanzahl = 0;
                                    //aktueller Restbetrag
    				int betrag = uebbetrag;
                                    //hier geht das gerechne los
    				for (int j=i ; j>=0 ; j--)
    				{
                                            //wie oft kann ich das Münzstück maximal verwenden
    					int tmp = betrag / w[j];
    					if (tmp > 0)
    					{
    						tmparray[j] = tmp;
    						betrag -= tmp * w[j];
    						tmpanzahl += tmp;
    					}
                                            //wenn ich die kleinste münze abgearbeitet habe
    					if (j==0)
    					{
                                                   //wenn ich eine lösung gefunden habe die besser ist dann....
    						if (tmpanzahl <= Anzahl && tmpanzahl >0 && betrag == 0)
    						{
    							Anzahl = tmpanzahl;
    							erg = tmparray;
                                                     //jetzt wird nicht abgebrochen weil es eine Lösung mit kleineren Münzen geben kann die besser ist
    						}
                                             
    					}
    				}
    			}
    			return erg;
    		}
    	
    		public static void main(String[] args)
    		{
    			muenzen hwnd= new muenzen();
    			hwnd.berechne(33);
                            //das ganze ist ohne ausgabe da ich keine Zeit dafür hatte 
    		}
    	}
    Was meint Ihr dazu?

    Wenn ich Zeit habe schau ich mir auch mal das Andere Problem an...

    Mfg

    OkeanosTom

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
  •