Hallo Jungs, das ist ´ne harte Nuß!

Wissenschaft Physik
1

Ich habe eine Geldbörse G mit n Münzen M1…Mn.
Der Prägewert W einer Münze bewegt sich zwischen Wmin und Wmax.
W ist immer eine positive Ganzzahl.

Beispiel (n=23; Wmin=1; Wmax=200):

Anzahl W (Wert) Summe Geldeinheiten GE

4…3…4 * 3 = 12
3…4…3 * 4 = 12
3…5…3 * 5 = 15
3…6…3 * 6 = 18
2…7…2 * 7 = 14
3…9…3 * 9 = 27
2…12…2 * 12 = 24
1…14…1 * 14 = 14
1…17…1 * 17 = 17
1…20…1 * 20 = 20

Summe S aller Geldeinheiten in meiner G: 173 GE

In meiner Geldbörse sind also 23 Münzen. Die kleinste Münze ist
ein 3er, die größte ein 20er. Ich habe insgesamt S=173 GE.

Jetzt kommt ein anderer Marktteilnehmer auf mich zu und bittet mich,
seine Münze mit dem Prägewert W1 zu wechseln („kleinmachen“).
Ich schaue in meine G und prüfe zunächst:
1.) Ist W1 „kleinste“ Münze (kann ich überhaupt „kleinmachen“)?

Wenn ich mindestens eine der beiden Fragen mit „Nein“ beantworte, sage
ich: „Tut mir leid, ich kann nicht wechseln“.
Wenn aber beide Male die Antwort „Ja“ heißt, wird´s komplizierter.
Es kann nämlich viele Möglichkeiten geben, wie ich wechsle.

Beispiel (G wie oben; W1=34):
Möglichkeit Stückelung des Wechselns

1…(1 * 20) + (1 * 14) = 34
2…(2 * 12) + (2 * 5) = 34
3…(1 * 9) + (1 * 7) + (3 * 6) = 34
4…(1 * 17) + (1 * 5) + (4 * 3) = 34
usw…usw.

Es kann aber auch sein, daß ich gar nicht wechseln kann, obwohl Frage
1 und 2 bejaht wurden.

So, und jetzt meine Frage/Bitte:

  • Gibts eine Möglichkeit, die Lösung bei gegebenem G und W1 zu berech-
    nen (Formel)?
  • Kann mir jemand in Grundzügen (BASIC/Pascal) einen entsprechenden
    Algorithmus formulieren (ohne programmtechnische Details)?
  • Wie schauts aus, wenn der andere Marktteilnehmer z. B. sagt: „Ich bräuchte
    zwei 3er und einen 5er“?

Vielen Dank für Eure Lösungen!

Grüße,
Gustav Kollmeier, München

2

Das beschriebene Problem ist NP-vollständig (z.B. Reduktion von Partition), es gibt also i.a. keinen besseren Algorithmus als alles durchzuprobieren. Das schoene bei Dir ist, dass Du eine
(hoffentlich kleine) Obergrenze für Münzwerte hast. Es gibt nämlich einen sog. pseudopolynomiellen ASlgorithmus (in diesem Fall mittels dynamischer Programmierung). Man stellt damit alle
Werte fest, die man potentiell herausgeben koennte.

Das ganze geht (in Pseudo-Basic, nbischen eingerostet) wie folgt:
Seien in M[i] die Werte deiner n Münzen gespeichert und in A[i] die
jeweiligen Anzahlen, sei dim P$[Mmax] ein Array von (noch leeren) Strings und ToString(a) eine Funktion, die aus der Zahl a einen String macht, der diese Nummer enthaelt. Fuer zwei Strings A$,B$
sei A$+B$ ihre konkatenierung (ich weiss nicht, ob Dein Basic das kann).

10 P$[0]=„Lösung: "
20 for i=1 to n
30 for j=Mmax to 0 step -1
40 if len(P$[j])=0 goto 200
50 for e=1 to A[i]
60 if len(P$[j+M[i]*e])>0 then goto 190
70 P$[j+M[i]*e]=P$[j]+“+"+tostring(e)+"*"+tostring(M[i])
190 next e
200 next j
210 next i
220 input „was wollen sie zerlegen ?“;a
230 print P$[a]

Das ganze hat dann Laufzeit approximativ Mmax*zahl der Münzen
was das ganze „theoretisch“ hart macht, ist dass du zm Speichern
von Mmax nur log Mmax Bits brauchst, die Laufzeit also exponentiell in dieser Bitzahl ist.

MfG
Martin Loehnertz

3

Hallo Gustav,

  • Gibts eine Möglichkeit, die Lösung bei gegebenem G und W1 zu
    berech-
    nen (Formel)?

mir ist nicht klar, ob Du unter „Formel“ und „Algorithmus“ dasselbe verstehst. Die Frage, ob es einen Lösungsalgorithmus gibt, kann sofort mit „ja“ beantwortet werden. Schließlich kannst Du einfach einen Generator programmieren, der Dir zu gegebenem G-Inhalt alle Münzkombinationen, die es überhaupt gibt, ausrechnet, z. B. zu 4 Münzen {A, B, C, D}:

A, B, C, D, AB, AC, AD, BC, BD, CD, ABC, ABD, ACD, BCD, ABCD

sowie eine Testroutine, die überprüft, ob der aktuelle „Generatoroutput“ die Bedingung „Summe über die Münzwerte des Generatoroutputs = W1“ erfüllt.

Dieser Algorithmus funktioniert, hat allerdings einen Schönheitsfehler: Er ist nicht effizient. Du kannst Dir leicht überlegen, daß die Anzahl der Generatoroutputs gleich 2^n–1 ist, bzw. gleich 2^n, wenn die Möglichkeit, daß der Wechselpartner gar nichts gewechselt haben möchte, mitberücksichtigt werden soll (einziges passendes Wechsel-Münzset dann leere Menge). Die Rechenzeit steigt daher exponentiell mit n an. Bei Deinem n=23 wären schon über 8 Millionen (genau: 8388607 bzw. 8388608) Möglichkeiten durchzutesten.

Die eigentlich interessante Frage ist daher, ob es einen effizienten Algorithmus gibt, d. h. einen, dessen Rechenzeit nicht stärker als polynomiell ansteigt. Die Antwort darauf kenne ich nicht.

Mit freundlichem Gruß
Martin

4

Ergänzung

10 P$[0]="Lösung: "
20 for i=1 to n
30 for j=Mmax to 0 step -1
40 if len(P$[j])=0 goto 200
50 for e=1 to A[i]

55 if j+M[i]*e > Mmax then goto 200

60 if len(P$[j+M[i]*e])>0 then goto 190
70 P$[j+M[i]*e]=P$[j]+"+"+tostring(e)+"*"+tostring(M[i])
190 next e
200 next j
210 next i
220 input „was wollen sie zerlegen ?“;a
230 print P$[a]

5

Danke!
Danke Martin,
ich werde das Programm so bald wie möglich ausprobieren.

Grüße,
Gustav Kollmeier,
München