# Suchalgorithmus gesucht



## ff (22. Sep 2006)

hallo welt

mein problem tönt sehr einfach, scheint es aber gar nicht zu sein (oder ich steh aufm schlauch):
ich habe einen betrag, der sich aus n teilbeträgen zusammensetzt (n ist nicht bekannt). nun möchte ich einen suchalgorithmus basteln, der so lange alle teilbeträge miteinander addiert, bis er den betrag gefunden hat (falls eine kombination existiert).

hat jemand eine idee, wie man das bewerkstelligen könnte?

so als beispiel:

betrag = 10
verfügbare subbeträge = {4, 9, 12, 1.5, 5.7, 3.8, 2.9, 1}


----------



## SnooP (22. Sep 2006)

Hmm... Kombinatorik? - Du musst jeden mit jedem addieren zumindest so lange die summe unter dem betrag ist. Also beim ersten Durchlauf: 4 + 9, 4+12, 4+1.5+5.7, 4+3.8+2.9, 4+1... danach mit dem zweiten Element weitermachen: 9+12, 9+1.5, usw. bis bei diesem Fall sogar 9+1 rauskommt und alles abbrechen kann.

Das ganze würde ich allerdings nicht wirklich als Suchalgorithmus bezeichnen


----------



## ff (22. Sep 2006)

naja, irgendwie ja schon oder? wir suchen teilbeträge. hab mir mal überlegt, ob ich das irgendwie in einen graphen bringe, aber da fällt mir auch nichts gescheites dazu ein...

aber jetzt merk ich, weshalb mir das ganze stinkt: weils vielleicht doch kombinatorik ist


----------



## ff (22. Sep 2006)

eigentlich kommts ja im wesentlich auf die "suchtiefe" an, oder? wenn sich ein betrag aus zwei teilbeträgen zusammensetzt, habe ich zwei verschachtelte for-schleifen, bei drei teilbeträgen drei, ...

hat jemand eine idee, wie man das rekursiv lösen könnte? war schon immer schlecht mit rekursionen...


----------



## Wildcard (22. Sep 2006)

Hier ein binärer Lösungsweg:
Angenommen du hast 4 Werte zur Auswahl. Erzeug dir eine binärzahl der Länge 4.
Zähl von 0000 bis 1111. Für jede Kombination dieser zahl errechnest du die Summe:
Wenn an Stelle n eine 1 steht, addiere den Wert von Stelle n.
Wenn eine 0 an der Stelle steht ignoriere den Wert.


----------



## SnooP (22. Sep 2006)

Kombinatorik fand ich immer noch schöner als Wahrscheinlichkeitstheorie... - die Wahrscheinlichkeit, dass bei mir eine Wahrscheinlichkeitsrechnung korrekt war, war doch immer recht gering 

Edit: du denkst glaub ich zu kompliziert...


----------



## ff (22. Sep 2006)

@wildcard: die idee gefällt mir, doch wirklich performant scheint mir das nicht zu sein. ich hab mal gedacht, ich sortiere erstmal alle zahlen (damit muss ich summen, die eh zu hoch werden gar nicht erst bilden).

und anschliessend möchte ich das ganze eben rekursiv über n vorgegebene schritte durchsuchen. aber eben, die ***-rekursion krieg ich nicht hin...


----------



## Wildcard (22. Sep 2006)

Das ist nur die Grundidee die noch optimiert werden muss. Du kannst beispielsweise schon von anfang an alle Zahlen aus der Liste werfen die größer als der Zielwert sind.
Rekursion ist zwar immer ganz schön, aber in diesem Fall sehe ich 2 Probleme:
1. Durch die hohe Anzahl an möglichen Kombinationen erzeugst du sehr viel overhead für die Stackverwaltung.
2. Mir fällt keine einfache Rekursion ein bei der du nicht ständig Array-Kopien machen musst. Da dürftest du mit meinem Ansatz deutlich schneller sein.


----------



## SnooP (22. Sep 2006)

Warum denn erst alle Kombinationen raussuchen? Ich würde das direkt machen - da kommt man mit zwei Schleifen aus und man spart sich die Kombinationen die schon vorher abbrechen, weil man über 10 ist... - ne Rekursion ist imho überflüssig.

hab grad eigentlich was zu tun - sonst hätt ichs schnell hingecoded


----------



## ff (22. Sep 2006)

snoop, falls du nächstens dazu kämest würd ichs äusserst schätzen, wenn du mir sowas mal entwurfsmässig zusammenschustern könntest. einfach, dass ich die idee darin sehen könnte...

cool wäre einfach, wenn man irgendwie trotzdem die max. anzahl "sub-summen" definieren könnte.


----------



## Leroy42 (22. Sep 2006)

SnooP hat gesagt.:
			
		

> hab grad eigentlich was zu tun - sonst hätt ichs schnell hingecoded



Eine moderne Variante des guten alten Fermat?  :shock: 


			
				Fermat hat gesagt.:
			
		

> _Ich habe hierfür einen wahrhaft wunderbaren Beweis gefunden, doch ist der Rand hier zu schmal, um ihn zu fassen_


----------



## Redfrettchen (22. Sep 2006)

ff hat gesagt.:
			
		

> hallo welt
> 
> mein problem tönt sehr einfach, scheint es aber gar nicht zu sein (oder ich steh aufm schlauch):
> ich habe einen betrag, der sich aus n teilbeträgen zusammensetzt (n ist nicht bekannt). nun möchte ich einen suchalgorithmus basteln, der so lange alle teilbeträge miteinander addiert, bis er den betrag gefunden hat (falls eine kombination existiert).
> ...


Na, das hört sich aber stark nach BW-Inf an...


----------



## ff (22. Sep 2006)

nicht ausfällig werden, redfrettchen! ich kann nichts dafür, dass ich (resp. das büro) das grad praktisch brauche. code sonst auch lieber anderes...


----------



## Wildcard (22. Sep 2006)

Warum versuchst du's nicht erstmal selbst statt auf die Lösung anderer zu warten. 
Ich hab dir doch schon einen Algorithmus gegeben...


----------



## Anmeldeboykottierer (23. Sep 2006)

HI,
so ganz allgemein würde mir hier sofort Rucksackproblem einfallen. Da gibt es etliche Varianten von, so ganz grob ist die Idee, dass du einen Rucksack der Größe A hast und Gegenstände mit einem Wert W und einem Gewicht G. Es geht dann darum, dass du so gut wie möglich den Rucksack füllst (A = max. Gewicht), so dass der Wert W möglichst groß ist. 

Im einfachsten Fall ist der Wert = dem Gewicht, es geht also darum möglichst gut an die Summe der einzelnen Werte ranzukommen (natürlich gibt es auch das exakte erreichen).
Das ist damit exakt dein Problem. Leider liegt aber meine Kenntnis der besten Lösungen etwas zurück, aber da es auch heute noch in jedem theor. Informatik Kurs auftauchen sollte, such einfach mal nach dem Rucksack Problem.

Gruß Der Anmeldeboykottierer


----------



## Gast (24. Sep 2006)

merci, anmeldeboykottierer,
da werden wir mal munter googeln


----------

