PDA

Archiv verlassen und diese Seite im Standarddesign anzeigen : Kombinations-Algorithmus gesucht!


WarSlash
2009-11-22, 02:40:16
Ich habe 8 Münzen (unsere Euro-Münzen).

Eine Bildungssumme x gebe ich an und möchte nun die Anzahl der verschiedenen Kombinationsmöglichkeiten finden, die alle diese Summe bilden.

Beispiel: 5 Cent, gibt es 4 Möglichkeiten:
(5 mal 1 Cent; 1 mal 2 Cent und 3 mal 1 Cent; 2 mal 2 Cent und 1 mal 1 Cent; 1 mal5 Cent).

Ich habe bereits einen Algorithmus für dieses Problem gefunden, dieser beruht aber leider auf Bruteforce und das dauert bekanntlich lange. (Rechner rechnet gerade für 2 €, habe bereits 75 Lösungen und es dauert....)

Daher die Frage an euch: Ist für diese Problemstellung auch ein Algorithmus auf Basis des Backtrackings möglich?!

Kann mir da einer auf die Sprünge helfen?

Gast
2009-11-22, 06:20:03
Summe hernehmen und solange die höchste Münze abziehen bis du einen negativen Wert erhältst. Dann die letzte Münze (kann auch die erste sein, wenn schon beim ersten Schritt negativ herauskommt) durch nächstkleinere ersetzen, solange bis ein gerade noch positiver Wert entsteht, sozusagen der "Rest". Dann die höchste Münze nehmen, die gerade noch kleiner als dieser Rest ist- usw usf. Irgendwann kommt dann genau 0 heraus. Die Kombination, die du jetzt hast, ist die mit den höchsten Münzen, größer geht nicht.
Und jetzt ersetzt du nach und nach, angefangen mit den allergrößten Münzen, jede Münze durch eine Kombination der nächstkleineren Münzen. Da nur ersetzt wird muß man das Ergebnis nicht mehr überprüfen. Die Ersetzungsmatrix kannst du ja speichern (zb aus 2€ wird als höchstmögliche Verkleinerung 2x 1€ usw).
Am Ende kommst du dann auf X mal 1Cent als kleinste Kombination.
Es findet also ein "Verdrängungswettbewerb" statt. Zuerst findet man die größe Kombi, dann drängen nach und nach immer kleinere Münzen nach.
Diese Methode sollte alle möglichen Kombinationen finden :)

Gast
2009-11-22, 06:43:36
Dein Beispiel mit 5 Cent wäre also:

5C minus 2€ = negative -> auf 1€ reduzieren
5C minus 1€ = negativ -> auf 50C reduzieren
.
.
.
5C minus 10C = negativ -> auf 5C reduzieren
5C minus 5C = 0 -> Bingo, höchste Kombination (1. gültige Kombi.)

-> Ersetzungalgo. starten!

(Ersetzungstabelle:
5C = 2C + 2C + 1C
2C = 1C + 1C)

5C -> 2C + 2C + 1C (2. gültige Kombi.)
2C +2C +1C -> 2C + 1C + 1C +1C (3. gültige Kombi.)
2C + 1C + 1C +1C -> 1C + 1C + 1C + 1C + 1C (4. gültige Kombi.)

-> Minimum erreicht, da nur mehr 1C -> Endergebnis: 4. Kombinationen

universaL
2009-11-22, 10:08:12
willst du eine oder alle mögliche lösungen?

Neomi
2009-11-22, 13:11:53
Die Variante mit jeweils der Ersetzung der größten Münze durch kleinere ausgehend von der einen höchsten Kombination kann nicht immer alle Kombinationen finden. Beispiel:

6 ct
-> 5 ct + 1 ct (höchste Kombination)
-> 2 ct + 2 ct + 1 ct + 1 ct (Ersetzung von 5 ct)
-> 2 ct + 1 ct + 1 ct + 1 ct + 1 ct (Ersetzung von 2 ct)
-> 1 ct + 1 ct + 1 ct + 1 ct + 1 ct + 1 ct (Ersetzung von 2 ct)

Die Möglichkeit 2 ct + 2 ct + 2 ct fehlt komplett bei der Methode.

Gast
2009-11-22, 15:18:09
Hmm, der Fehler entsteht offenbar bei ungeradem Ersetzen. Die 1 aus 2+2+1 aus der 5 entstand nicht aus einer 2, sondern direkt aus der 5- da findet ein Sprung statt. Diese 1 steht dann einer möglichen anderen 1 nicht mehr zur Verfügung, dh, diesen beiden 1 kamen nicht aus einer 2 , sondern beide aus anderen 5ern.
Man müßte also alle Kombinationen von unten aus nochmal durchgehen und überprüfen ob aus allen niederen Münzen auch die entsprechenden höheren existieren. Falls diese fehlen, fügt man diese dann hinzu.

Beim 6C Beispiel würde man also mit dem "Kamm" durchgehen und feststellen, daß es zu 2+2+1+1 kein 2+2+2 gibt.
Aufpassen müßte man eigentlich nur bei der 5. Alle anderen sind nur durch eine Art niederen Wertes zu ersetzen, nur die 5 braucht 2 Arten (2 und 1).
Aus 2€ reicht 2x 1€.
Aus 1€ reicht 2x 50C.
Aus 20C reicht 2x 10C.
AUs 10C reicht 2x 5C.
Aus 2C reicht 2x 1C.

Nur bei 50C und 5C gibts Probleme. Die brauchen 2(0) und 1(0).
Dh, man müßte eigentlich alle Kombinationen mit einem flag versehen, wo eine 5C bzw 50C ersetzt wurde. Die müssen dann nochmal "gekämmt" werden.

Gast
2009-11-22, 15:24:57
Beispiel 11C

5 5 1
5 2 2 1 1 (flag 1)
2 2 1 2 2 1 1 (flag 2)
2 2 1 2 1 1 1 1
2 2 1 1 1 1 1 1 1
2 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1

flag 1: 5 2 2 2
flag 2: 2 2 2 2 2 1

Insg.: 9 Kombinationen

Gast
2009-11-22, 15:49:23
Ups, 10 Kombis. 10-1 geht ja auch ^^

Neomi
2009-11-22, 16:17:48
Jede Art von Betrachtung schon vorhandener Lösungen außer der aktuellen (die weiter aufgesplittet wird) ist unnötig, es gibt da eine recht einfache Methode der Aufsplittung mit Sonderfällen.

Die regulären Fälle:
2 € -> 2x 1 €
1 € -> 2x 50 ct
20 ct -> 2x 10 ct
10 ct -> 2x 5 ct
2 ct -> 2x 1 ct

Jetzt die Sonderfälle:
50 ct -> 10 ct min 1x vorhanden ? 3x 20 ct, -1x 10 ct : 2x 20 ct, 1x 10 ct
5 ct -> 1 ct min 1x vorhanden ? 3x 2 ct, -1x 1 ct : 2x 2 ct, 1x 1 ct

Der trinäre Operator ist so zu lesen:
<Bedingung> ? <Aufsplittung falls erfüllt> : <Aufsplittung sonst>

Die alternative Aufsplittung ergibt sich später automatisch aus der bedingten Aufsplittung, es geht also trotz fehlendem Backtracking keine Lösung verloren.

Edit: nein, stimmt doch nicht, wenn man wirklich alle Kombinationen will. In dem Fall fehlen in #7 allerdings auch einige, wie z.B. 5 1 1 1 1 1 1.

Pinoccio
2009-11-22, 16:29:02
[...]
Diese Methode sollte alle möglichen Kombinationen finden :)Und ist sie schneller als Brute force? (I. S. d. Komplexitätstheorie)

willst du eine oder alle mögliche lösungen?Solange wir das nicht wissen ...

Lesetip: Matheplanet (http://www.matheplanet.com/default3.html?call=article.php?sid=269), "Lösungen" (http://www.matheplanet.com/matheplanet/nuke/html/matroid/muenzz.php)

mittels der verlinkten Lösungen:
(Rechner rechnet gerade für 2 €, habe bereits 75 Lösungen und es dauert....)Es gibt 73682 mögliche Lösungen.

mfg

WarSlash
2009-11-22, 17:45:24
Dann hätte ich noch ewig weiter rechnen können (paar Jahre?! Jahrzehnete?!).
In den Morgenstunden war er bereits bei Lösung 178.

Wie hast du die Lösung so fix heraufgefunden?!

Ich will natürlich alle Kombinationsmöglichkeiten finden!

Neomi
2009-11-22, 17:50:51
Jep, auf die Zahl an Lösungen komme ich auch. Hab mal kurz ein Lua-Script zusammengehämmert (E statt € wegen der Konsolendarstellung). Die Ausgabe ist der Flaschenhals, ohne Ausgabe läuft das bei mir in weniger als einer Sekunde:

value = 200

-- helpers (do not change without checking the following code)

coins = { 200, 100, 50, 20, 10, 5, 2, 1 }
names = { "2E", "1E", "50ct", "20ct", "10ct", "5ct", "2ct", "1ct" }
count = 0

function dumpSplit(split)
local text = false
for i = 1, #coins do
if split[i] > 0 then
text = text and (text..", ") or ""
text = text..split[i].."x "..names[i]
end
end
if text then
count = count + 1
print("#"..count..": "..text)
end
end

function findInitialSplit(value)
local split, rest = {}, value
for i = 1, #coins do
split[i] = math.floor(rest / coins[i])
rest = rest - split[i] * coins[i]
end
dumpSplit(split)
return split
end

function splitRecursive(split, limit)
for i = #coins - 1, limit, -1 do
if split[i] > 0 then
local split2 = {}
for j = 1, #coins do
split2[j] = split[j]
end
split2[i] = split[i] - 1
if coins[i] ~= 2 * coins[i + 1] then -- special for 50ct and 5ct
if split[i + 2] > 0 then
split2[i + 1] = split[i + 1] + 3
split2[i + 2] = split[i + 2] - 1
else
split2[i + 1] = split[i + 1] + 2
split2[i + 2] = split[i + 2] + 1
end
else
split2[i + 1] = split[i + 1] + 2
end
dumpSplit(split2)
splitRecursive(split2, i)
end
end
end

print(string.format("Value: %.2fE\n", value / 100))
splitRecursive(findInitialSplit(value), 1)

Pinoccio
2009-11-22, 18:04:44
Dann hätte ich noch ewig weiter rechnen können (paar Jahre?! Jahrzehnete?!).
In den Morgenstunden war er bereits bei Lösung 178.

Wie hast du die Lösung so fix heraufgefunden?!Folge meinen Links ....

Ich will natürlich alle Kombinationsmöglichkeiten finden!Das Problem ist NP. Viel Spaß. :-)


mfg

pest
2009-11-22, 18:07:33
erinnert mich ans Bin-Packing-Problem, da gibt es ein paar nette Heuristiken, das Problem ist aber eh NP

Pinoccio
2009-11-22, 18:13:24
erinnert mich ans Bin-Packing-Problem, da gibt es ein paar nette Heuristiken, das Problem ist aber eh NPEs ist so wie ich das sehe eher verallgemeinertes PARTITION (http://en.wikipedia.org/wiki/Karp%27s_21_NP-complete_problems). Aber die sind ja eh alle gleich - von einem gewissen Standpunkt aus. ><

Und Heuristiken sind toll, wenn man eine Lösung benötigt. Aber für alle ist das eher ungünstig.

mfg

pest
2009-11-22, 18:18:44
Für mich ist das eher ein Set packing problem...aber nunja..


Und Heuristiken sind toll, wenn man eine Lösung benötigt. Aber für alle ist das eher ungünstig.


darüber können wir jetzt streiten...aber Simpsons sind spannender

WarSlash
2009-11-22, 18:33:22
Folge meinen Links ....

Das Problem ist NP. Viel Spaß. :-)


mfg


Sowas habe mir langsam auch gedacht. Na toll :(

Exhaustive Search (Bruteforce FTW)

pest
2009-11-22, 18:38:46
nur weil etwas NP ist, heißt das nicht, das man alle Möglichkeiten durchprobieren muss

Neomi
2009-11-22, 20:00:35
Exhaustive Search (Bruteforce FTW)

Wenn Bruteforce nötig wäre, dann würde das Script, was ich vorhin gepostet habe (und das ohne Bruteforce auskommt), nicht alle Möglichkeiten finden.

Gast
2009-12-17, 20:28:55
Hallo,
super, dass Ihr gerade über Kombinationsmöglichkeiten sprecht! Mit der angegeben Rechnung komme ich nicht klar. Wir suchen die Kombimöglichkeiten für 10€ in die Münzen 5€, 2€, 1€, 50c, 20c, 10c, 5c, 2c und 1c. Kann jemand mir möglichst bis morgen früh mir die Anzahl der Möglichkeiten durchgeben. 1000 Dank. Gruß ibberlin