Suchalgorithmus gesucht

[ff]

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]

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]

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]

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]

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]

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]

@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]

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]

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]

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]

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

Eine moderne Variante des guten alten Fermat? :shock:

Ich habe hierfür einen wahrhaft wunderbaren Beweis gefunden, doch ist der Rand hier zu schmal, um ihn zu fassen

 

[Redfrettchen]

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}

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

 

[ff]

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]

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

 

[Anmeldeboykottierer]

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]

merci, anmeldeboykottierer,
da werden wir mal munter googeln