Kombinationsbildung per Rekursion

Hallo!

Ich habe folgenden Code fabriziert, der jedoch nicht so richtig will wie ich... läuft wie eine Endlosschleife ;)

Es gibt unterschiedliche Tiere, 1 Hund (15 Euro), 1 Katze (1 Euro) und 4 Mäuse (1 Euro)...
Es sollen nun Kombinationen gebildet werden, bei denen ich folgende Kriterien erfülle:
- Jedes Tier muss mindestens einmal gekauft werden
- Es müssen 100 Tiere gekauft werden
- Es muss 100 Euro ausgegeben werden

Code:
def doIt(pets, count, cash):
	if count == 100 and cash == 100:
		animals.append(pets)
		return
	elif count > 100 or cash > 100:
		return
	
	for pet, cost in dic.items():
		pets.append(pet)
		doIt(pets[:], count+int(pet[0]), cash+cost) 

if __name__ == '__main__':
	animals = []
	dic = { "1 Dog":15, "1 Cat":1, "4 Mice":1 }
	doIt([], 0, 0)
	for petComb in animals:
		print petComb
	print len(petComb)

Vielleicht könnt Ihr mir weiterhelfen, ich sehe meinen Fehler momentan nicht.

Gruß
Felix
 
Es könnte daran liegen, dass deine drei Regeln in deinem Programm nicht gleichzeitig erfüllt werden können. Du müsstest die Werte vervierfachen (Maus=1, Katze=4, Hund=60, 100?=400) oder den Mäusen 0.25 als Wert zuweisen.
 
Ergibt Sinn...
Leider funktioniert es trotzdem noch nicht, läuft immer noch wie eine Endlosschleife!

Code:
def doIt(pets, count, cash):
	if count == 100 and cash == 400:
		animals.append(pets)
		return
	elif count > 100 or cash > 400:
		return
	
	for pet, cost in dic.items():
		pets.append(pet)
		doIt(pets[:], count+int(pet[0]), cash+cost) 

if __name__ == '__main__':
	animals = []
	dic = { "1 Dog":60, "1 Cat":4, "4 Mice":4 }
	doIt([], 0, 0)
	for petComb in animals:
		print petComb
	print len(petComb)

Oder wie hast du das gemeint? Es ist nicht möglich 1 Maus für 0.25 Euro zu kaufen.

Gruß
Felix
 
Ich denke, mit ein wenig Mathematik wirst du bei diesem Problem sehr viel schneller am Ziel sein.

In der Aufgabenstellung angegeben:
(a: Hund, b: Katze, c: Maus)
Code:
a + b + c = 100
15a + b + 0.25c = 100
c = x * 4
a, b, c, x : Ganze Zahlen größer Null
Die beiden Gleichungen nach b umstellen und gleichsetzen:
Code:
100 - a - c = 100 - 15a - 0.25c
a + c = 15a + 0.25c
14a = 0.75c
c = a * 14 / 0.75
Mit ein wenig ausprobieren findet man heraus, dass a nur 3 sein kann, da c sonst entweder ungerade oder größer als 100 ist. Also:
Code:
a = 3
c = 3 * 14 / 0.75 = 56
b = 100 - 3 - 56 = 41

Kontrolle:
3 + 41 + 56 = 100
15*3 + 41 + 0.25 * 56 = 100
56 = 14 * 4
Es gibt also nur eine Lösung. (btw, kann mir vielleicht eines der Mathe-Genies hier im Board sagen, wie man den Abschnitt mit dem Ausprobieren mathematischer ausdrücken kann? ;))

@Ook: Ich habe mir jetzt deinen Code nicht mehr genauer angeschaut, aber kann es sein, dass dein Programm nicht in einer Endlosschleife hängt, sondern einfach nur Ewigkeiten zum "Berechnen" (Brute Force) der Lösung braucht?

Mfg, Eydeet
 
Original von Ook!
Hallo!

Vielleicht könnt Ihr mir weiterhelfen, ich sehe meinen Fehler momentan nicht.

Gruß
Felix
Sehe ich es richtig, dass Du versucht, tatsächlich eine Kombination aus 100 Tieren zu bilden? Das könnte dauern (3^100~5*10^47 ;)

Wenn man zu faul zum Rechnen ist:
Frage:
Code:
Hund in 1..100,Katze in 1..100,Maus in 1..100,
     Hund*15+Katze+Maus/4#=100,    %Eurosumme = 100
     Hund+Katze+Maus#=100,                %Anzahl der Tiere=100         
     Maus mod 4 #=0,                               %Mäuse gibts nur in 4er Päckchen
     labeling([ff],[Hund,Katze,Maus]).
Antwort:
Code:
Hund = 3,
Maus = 56,
Katze = 41 ? ;   %weitere Antworten?
no
 
Danke für eure Hilfe...

Das Problem mit ein wenig Mathe anzugehen, habe ich nicht versucht ;)

Ich habe bisher nicht über die Dauer nachgedacht, ich bin davon ausgegangen, dass solch eine aufgabe doch recht schnell gelöst werden könnte mit einer einfachen Rekursion.

Bezüglich der Dauer, stimmt...
Das wirds dann wohl sein... Ich hatte offensichtlich nicht genug Geduld oder war zu faul einmal mehr zu überlegen ;)

Gruß
Felix
 
Zurück
Oben