Hallo,

ich suche einen Algorithmus, der sich die richtigen Summanden sucht, damit
am Ende die vorgegebene Summe rauskommt.
Ich hatte schon eine Lösung gefunden, allerdings ging die nur bis 29
Summanden und ich habe 130...
Ich dachte eigentlich an Backracking, aber leider bring ichs nicht mehr,
eine funktionierende Funktion aufzustellen.

Ich hoffe ihr könnt mir helfen

Gruß Frank

From:	Sven Guckes
Subject:	Re: Algorithmus der aus den Richtigen Summanden die Summe findet
Date:	7 Apr 2004 12:14:08 GMT

* Frank Nestler [2004-04-07]:
> ich suche einen Algorithmus, der sich die richtigen
> Summanden sucht, damit am Ende die vorgegebene Summe
> rauskommt. Ich hatte schon eine Lösung gefunden, allerdings
> ging die nur bis 29 Summanden und ich habe 130...

Summe = ( \sum_{n=1}^129 0 ) + Summe

na, das war ja einfach. der naechste, bitte!

> Ich dachte eigentlich an Backracking, aber leider bring ichs
> nicht mehr, eine funktionierende Funktion aufzustellen.

vielleicht liegt das an der fehlenden information
ueber die randbedingungen zur aufgabe? hmm...

Sven

From:	Robert Degen
Subject:	Re: Algorithmus der aus den Richtigen Summanden die Summe findet
Date:	Wed, 07 Apr 2004 14:23:58 +0200

Sven Guckes wrote:

> * Frank Nestler [2004-04-07]:
>> ich suche einen Algorithmus, der sich die richtigen
>> Summanden sucht, damit am Ende die vorgegebene Summe
>> rauskommt. Ich hatte schon eine Lösung gefunden, allerdings
>> ging die nur bis 29 Summanden und ich habe 130...
>
> Summe = ( \sum_{n=1}^129 0 ) + Summe

Hey, wenn schon denn schon.

Summe = ( \sum_{n=0}^129 0 ) + Summe
Summe = ( \sum_{n=1}^130 0 ) + Summe

tztztz ;)

>
> na, das war ja einfach. der naechste, bitte!
>
>> Ich dachte eigentlich an Backracking, aber leider bring ichs
>> nicht mehr, eine funktionierende Funktion aufzustellen.
>
> vielleicht liegt das an der fehlenden information
> ueber die randbedingungen zur aufgabe? hmm...
>
> Sven

From:	Sven Guckes
Subject:	Re: Algorithmus der aus den Richtigen Summanden die Summe findet
Date:	7 Apr 2004 13:02:24 GMT

* Frank Nestler [2004-04-07]:
> ich suche einen Algorithmus, der sich die richtigen
> Summanden sucht, damit am Ende die vorgegebene Summe
> rauskommt. Ich hatte schon eine Lösung gefunden, allerdings
> ging die nur bis 29 Summanden und ich habe 130...

* Sven Guckes wrote:
> Summe = ( \sum_{n=1}^129 0 ) + Summe

* Robert Degen [2004-04-07]:
> Hey, wenn schon denn schon.
> Summe = ( \sum_{n=0}^129 0 ) + Summe
> Summe = ( \sum_{n=1}^130 0 ) + Summe

das waeren dann aber 131 summanden -
einer zuviel. *huestel* ;-)

Sven

From:	Robert Degen
Subject:	Re: Algorithmus der aus den Richtigen Summanden die Summe findet
Date:	Wed, 07 Apr 2004 15:36:55 +0200

Sven Guckes wrote:

> * Frank Nestler [2004-04-07]:
>> ich suche einen Algorithmus, der sich die richtigen
>> Summanden sucht, damit am Ende die vorgegebene Summe
>> rauskommt. Ich hatte schon eine Lösung gefunden, allerdings
>> ging die nur bis 29 Summanden und ich habe 130...
>
> * Sven Guckes wrote:
>> Summe = ( \sum_{n=1}^129 0 ) + Summe
>
> * Robert Degen [2004-04-07]:
>> Hey, wenn schon denn schon.
>> Summe = ( \sum_{n=0}^129 0 ) + Summe
>> Summe = ( \sum_{n=1}^130 0 ) + Summe
>
> das waeren dann aber 131 summanden -
> einer zuviel. *huestel* ;-)

Ahhhhh ich trottel. Sorry. Verrafft.... tztztz

>
> Sven

From:	Daniel Gutekunst
Subject:	Re: Algorithmus der aus den Richtigen Summanden die Summe findet
Date:	Tue, 27 Apr 2004 19:10:21 +0200

Frank Nestler wrote:

> ich suche einen Algorithmus, der sich die richtigen Summanden sucht, damit
> am Ende die vorgegebene Summe rauskommt.
> Ich hatte schon eine Lösung gefunden, allerdings ging die nur bis 29
> Summanden und ich habe 130...
> Ich dachte eigentlich an Backracking, aber leider bring ichs nicht mehr,
> eine funktionierende Funktion aufzustellen.
>
> Ich hoffe ihr könnt mir helfen

Dies ist ein klassisches Problem der Informatik --- "Rucksack" und "Subset
Sum" genannt. Die NP-vollständigkeit wird z.B. in "Theoretische Informatik
kurzgefasst" von Uwe Schöning bewiesen.

Das heißt, es gibt höchst wahrscheinlich keinen effizienten (polynomiellen)
Algorithmus für die Aufgabe.

Du musst also mit einer Laufzeit von 2^n rechnen. Strategien das
Backtracking so effizient wie möglich zu machen, beruhen wahrscheinlich auf
der Teilbarkeit der Summe gewisser Zahlen (vorher werden alle Zahlen durch
geeignete Faktoren zu ganzen Zahlen gemacht).

MfG
Daniel Gutekunst

From:	Robert Degen
Subject:	Re: Algorithmus der aus den Richtigen Summanden die Summe findet
Date:	Wed, 07 Apr 2004 17:45:42 +0200

Frank Nestler wrote:

> Hallo,
>
> ich suche einen Algorithmus, der sich die richtigen Summanden sucht, damit
> am Ende die vorgegebene Summe rauskommt.
> Ich hatte schon eine Lösung gefunden, allerdings ging die nur bis 29
> Summanden und ich habe 130...
> Ich dachte eigentlich an Backracking, aber leider bring ichs nicht mehr,
> eine funktionierende Funktion aufzustellen.

Ich verstehe noch nichtg wirklich warum Du hier Backtracking benutzen
willst, aber egal. Diese Aufgabe erinnert mich irgendwie an den
"Traveling Salesman". Hm. Also ich habs mal überflogen. Ad hoc fällt mir nur
Bruteforce ein und das würde selbst bei 1.000.000 Tests/sek immer noch
10^25 Jahre oder so dauern. Da muss es doch was geben, ich werde mal etwas
kramen...

>
> Ich hoffe ihr könnt mir helfen
>
> Gruß Frank

From:	Chris Huebsch
Subject:	Re: Algorithmus der aus den Richtigen Summanden die Summe findet
Date:	Wed, 7 Apr 2004 18:30:57 +0000 (UTC)

Robert Degen (Wed, 07 Apr 2004 17:45:42 +0200):
> Ich verstehe noch nichtg wirklich warum Du hier Backtracking benutzen
> willst, aber egal. Diese Aufgabe erinnert mich irgendwie an den
> "Traveling Salesman". Hm. Also ich habs mal überflogen. Ad hoc fällt mir nur
> Bruteforce ein und das würde selbst bei 1.000.000 Tests/sek immer noch
> 10^25 Jahre oder so dauern. Da muss es doch was geben, ich werde mal etwas
> kramen...

Klar muss dich das an das TSP erinnern, denn es ist wohl das
Rucksack-Problem, was der OP hier zu loesen sucht. Beide sind in
polynomieller Zeit aufeinander abbildbar.

Was ich nicht verstehe: Wie kann es einen Algorithmus geben, der das
Problem fuer 29, aber nicht fuer 130 Summanden loesen kann?

Achja - falls jemand eine polynomielle Loesung des TSP hat, bitte
melden. *g*

Chris
--
Chris Huebsch www.hübsch-gemacht.de | TU Chemmnitz, Informatik, RNVS
GPG-Encrypted mail welcome! ID:7F2B4DBA | Str. d. Nationen 62, B204
Chemnitzer Linux-Tage 2005, 5.-6.März | D-09107 Chemnitz
http://www.tu-chemnitz.de/linux/tag/ | +49 371 531-1377, Fax -1803

From:	Frank Nestler
Subject:	Re: Algorithmus der aus den Richtigen Summanden die Summe findet
Date:	Thu, 8 Apr 2004 08:30:32 +0200

> Was ich nicht verstehe: Wie kann es einen Algorithmus geben, der das
> Problem fuer 29, aber nicht fuer 130 Summanden loesen kann?

Hallo Chris,

das problem schon mal jemand anderes beschrieben und der hat mir das hier
gesendet:

ai enthällt alles summanden und
textbox enthällt die gesuchte summe

und dieser algorithmus ist auf max 29 summanden begrenzt

Private Sub CommandButton1_Click()
Dim ai&(), v:

ReDim ai(Range("A1").CurrentRegion.Count)

While Range("a1").Offset(i, 0) <> ""
ai(i) = Range("a1").Offset(i, 0)
i = i + 1
Wend

For Each v In Summen(ai(), TextBox1)
Debug.Print "30 = " & v
Next v

End Sub

Function Summen(aSummanten&(), ByVal Gesamtsumme&) As Collection
Dim af&, uf&, c&, d&, m&, pow2&(29), s$

Set Summen = New Collection: m = 1
For c = 0 To 29: pow2(c) = m: m = m * 2: Next c

uf = UBound(aSummanten())
If uf > 29 Then Err.Raise 6

For c = 1 To 2 ^ (uf + 1) - 1
m = 0
For d = 0 To uf
If (c And pow2(d)) <> 0 Then
m = m + aSummanten(d)
End If
Next d
If m = Gesamtsumme Then
s = vbNullString
For d = 0 To uf
If (c And pow2(d)) <> 0 Then
s = s & aSummanten(d) & " + "
End If
Next d
Summen.Add Left$(s, Len(s) - 3)
End If
Next c
End Function

From:	Chris Huebsch
Subject:	Re: Algorithmus der aus den Richtigen Summanden die Summe findet
Date:	Thu, 8 Apr 2004 07:16:03 +0000 (UTC)

Frank Nestler (Thu, 8 Apr 2004 08:30:32 +0200):
> ai enthällt alles summanden und
> textbox enthällt die gesuchte summe
>
> und dieser algorithmus ist auf max 29 summanden begrenzt

Es ist nicht der Algorithmus, der begrenzt ist, sondern dessen
Implementierung in BASIC.

> Private Sub CommandButton1_Click()
> Dim ai&(), v:
>
> ReDim ai(Range("A1").CurrentRegion.Count)
>
> While Range("a1").Offset(i, 0) <> ""
> ai(i) = Range("a1").Offset(i, 0)
> i = i + 1
> Wend
>
> For Each v In Summen(ai(), TextBox1)
> Debug.Print "30 = " & v
> Next v
>
> End Sub
>
> Function Summen(aSummanten&(), ByVal Gesamtsumme&) As Collection
> Dim af&, uf&, c&, d&, m&, pow2&(29), s$
^^ Hier
>
> Set Summen = New Collection: m = 1
> For c = 0 To 29: pow2(c) = m: m = m * 2: Next c
^^ Hier
>
> uf = UBound(aSummanten())
> If uf > 29 Then Err.Raise 6
^^ Hier
> For c = 1 To 2 ^ (uf + 1) - 1
> m = 0
> For d = 0 To uf
> If (c And pow2(d)) <> 0 Then
> m = m + aSummanten(d)
> End If
> Next d
> If m = Gesamtsumme Then
> s = vbNullString
> For d = 0 To uf
> If (c And pow2(d)) <> 0 Then
> s = s & aSummanten(d) & " + "
> End If
> Next d
> Summen.Add Left$(s, Len(s) - 3)
> End If
> Next c
> End Function

Mir scheint, dass das Feld pow2 mit der Produktfolge p(i+1)=p(i)*2
gefuellt wird. Bei 32-Bit-Laufzeitumgebungen ist da bei 2^32-1
Feierabend. (Wenn sogar vorzeichenbehaftet sogar bei 2^31-1).

Ich habe den Eindruck, dass das Feld verwendet wird, um die Verwendung
der Summanden in der Summe zu markieren. Das kann man wahrscheinlich
auch anders loesen, indem man da ein Datentyp nimmt, der keine
Laengenbegrenzung kennt. Mit derartig grossen Zahlen umher zu werfen,
macht auch nicht wirklich Sinn.

Gruesse

Chris
PS: Summand schreibt man mit dem weichen T ;-p
--
Chris Huebsch www.hübsch-gemacht.de | TU Chemmnitz, Informatik, RNVS
GPG-Encrypted mail welcome! ID:7F2B4DBA | Str. d. Nationen 62, B204
Chemnitzer Linux-Tage 2005, 5.-6.März | D-09107 Chemnitz
http://www.tu-chemnitz.de/linux/tag/ | +49 371 531-1377, Fax -1803

From:	Robert Degen
Subject:	Re: Algorithmus der aus den Richtigen Summanden die Summe findet
Date:	Wed, 07 Apr 2004 12:13:00 +0200

Frank Nestler wrote:

> Hallo,
>
> ich suche einen Algorithmus, der sich die richtigen Summanden sucht, damit
> am Ende die vorgegebene Summe rauskommt.

Geht das eventuell etwas genauer? Wie müssen die Summanden beschaffen sein?
Nur ganze Zahlen?!? Beispiel? Also nach dem was ich jetzt hier gelesen
habe, brauch man für sowas keinen Algorithmus.

Könntest Du vielleicht ein Beispiel posten. Aus der kurzen Beschreibung
werde ich nicht schlau...

> Ich hatte schon eine Lösung gefunden, allerdings ging die nur bis 29
> Summanden und ich habe 130...
> Ich dachte eigentlich an Backracking, aber leider bring ichs nicht mehr,
> eine funktionierende Funktion aufzustellen.
>
> Ich hoffe ihr könnt mir helfen
>
> Gruß Frank

Gruß
Rob

From:	Frank Nestler
Subject:	Re: Algorithmus der aus den Richtigen Summanden die Summe findet
Date:	Wed, 7 Apr 2004 16:43:53 +0200

Ok hier das Beispiel:

Die Summanden sind zum Beispiel:
1,3
3
54
12
0,4
2

Und die summe die ich raus haben möchte ist:
13,7

Das heißt, der Algorithmus soll herausfinden, dass 13,7 die summe von
1,3+0,4+12 ist.
Und jeder summand soll aber nur einmal verwendet werden!

Hoffe jetzt kannst du was damit anfangen.

Gruß Frank

From:	Robert Degen
Subject:	Re: Algorithmus der aus den Richtigen Summanden die Summe findet
Date:	Wed, 07 Apr 2004 17:28:24 +0200

können die Summanden negativ sein?

From:	Sven Guckes
Subject:	Re: Algorithmus der aus den Richtigen Summanden die Summe findet
Date:	7 Apr 2004 22:25:54 GMT

* Frank Nestler [2004-04-07]:
> Ok hier das Beispiel:
> Die Summanden sind zum Beispiel:
> 0,4 1,3 2 3 12 54
>
> Und die summe die ich
> raus haben möchte ist: 13,7
>
> Das heißt, der Algorithmus soll herausfinden,
> dass 13,7 die summe von 1,3+0,4+12 ist. Und
> jeder summand soll aber nur einmal verwendet werden!

sollen alle summanden *genau* einmal oder
*hoechstens* einmal verwendet werden?
duerfen die summanden auch negativ verwendet werden?

wird vorausgesetzt, dass es eine loesung gibt?
oder kann es auch mehrere loesungen geben?
oder vielleicht ueberhaupt keine loesung?

sollen alle loesungen gefunden werden - oder nur eine?
soll der algorithmus nach einer vorgegebenen zeit
oder eine anzahl von operationen abbrechen?

in welcher sprache soll der algorithmus gegeben
werden - imperativ oder funktional? pseudo code?

fuer jede kombination von antworten kann
die loesung eine wenig anders aussehen..

Sven

From:	Frank Nestler
Subject:	Re: Algorithmus der aus den Richtigen Summanden die Summe findet
Date:	Thu, 8 Apr 2004 08:25:24 +0200

> sollen alle summanden *genau* einmal oder
> *hoechstens* einmal verwendet werden?
> duerfen die summanden auch negativ verwendet werden?

die summanden sind nur positiv
und jeder wird nur einmal verwendet

>
> wird vorausgesetzt, dass es eine loesung gibt?
> oder kann es auch mehrere loesungen geben?
> oder vielleicht ueberhaupt keine loesung?

es kann mehrere lösungen geben,
aber auch keine

>
> sollen alle loesungen gefunden werden - oder nur eine?
> soll der algorithmus nach einer vorgegebenen zeit
> oder eine anzahl von operationen abbrechen?

es sollen alle lösungen gefunden werden
der algorithmus soll enden wenn er alle möglichkeiten durchprobiert hat

>
> in welcher sprache soll der algorithmus gegeben
> werden - imperativ oder funktional? pseudo code?

ich wollte das problem im excel lösen -also vba

>
> fuer jede kombination von antworten kann
> die loesung eine wenig anders aussehen..
>
> Sven

Hoffe die antworten reichen erstmal

Danke für deine/eure Bemühungen.
Frohe Ostern

Gruß Frank