Lösung des Truhenproblems

31/01/2008 - 15:58 von Robert Meissner | Report spam
Hallo!

Ich bin auf der Suche nach der Lösung des sogenannten Truhen-
problems. Vielleicht gibt es auch einen àhnlichen Namen für
dieses Problem. Über Google finde ich keine Informationen be-
züglich "Truhenproblem".

Das Problem gestaltet sich folgendermaßen:

- Truhe mit z.B. 20 Münzen (die Anzahl der Münzen ist für
die Aufgabenstellung immer bekannt)
- Münzen besitzen eine ganzzahlige Wertigkeit

Beispiel: n=6 Münzen:

Münzen in der Truhe: 1 6 3 5 3 8

Das Problem besteht darin zu prüfen, ob sich der Gesamt-
münzenwert der Truhe (im Beispiel 26) mit den gegebenen
Münzen hàlftig aufteilen làsst.

Die 1. Hàlfte: 1 6 3 3 (Summe: 13)
Die 2. Hàlfte: 5 8 (Summe: 13)

Ich habe die Werte der Münzen in einem Array mit vorgegebener
Lànge gegeben. Nun soll ein Algorithmus geschrieben werden,
welcher _rekursiv_ überprüft ob sich die Wertmenge der in der
Truhe befindlichen Münzen teilen làsst. Die Funktion soll dann
entsprechend 'true' oder 'false' zurückliefern.

Hat jemand eine Idee für einen rekursiven Lösungsansatz?

Danke!

Mit freundlichen Grüßen
Robert Meissner
 

Lesen sie die antworten

#1 Josef Chmel
31/01/2008 - 16:09 | Warnen spam
On 31 Jan., 15:58, Robert Meissner
chemnitz.de> wrote:
Hallo!

Ich bin auf der Suche nach der Lösung des sogenannten Truhen-
problems. Vielleicht gibt es auch einen àhnlichen Namen für
dieses Problem. Über Google finde ich keine Informationen be-
züglich "Truhenproblem".

Das Problem gestaltet sich folgendermaßen:

   - Truhe mit z.B. 20 Münzen (die Anzahl der Münzen ist für
     die Aufgabenstellung immer bekannt)
   - Münzen besitzen eine ganzzahlige Wertigkeit

   Beispiel: n=6 Münzen:

   Münzen in der Truhe: 1 6 3 5 3 8

   Das Problem besteht darin zu prüfen, ob sich der Gesamt-
   münzenwert der Truhe (im Beispiel 26) mit den gegebenen
   Münzen hàlftig aufteilen làsst.

   Die 1. Hàlfte: 1 6 3 3 (Summe: 13)
   Die 2. Hàlfte: 5 8 (Summe: 13)

Ich habe die Werte der Münzen in einem Array mit vorgegebener
Lànge gegeben. Nun soll ein Algorithmus geschrieben werden,
welcher _rekursiv_ überprüft ob sich die Wertmenge der in der
Truhe befindlichen Münzen teilen làsst. Die Funktion soll dann
entsprechend 'true' oder 'false' zurückliefern.

Hat jemand eine Idee für einen rekursiven Lösungsansatz?

Danke!

Mit freundlichen Grüßen
Robert Meissner



Hallo,

das ist wohl das partition problem (http://en.wikipedia.org/wiki/
Partition_problem).
Als Loesungsweg die ueblichen Verdaechtigen fuer NP-harte Probleme
(Branch&Bound,
Dynamic programming, ...). Infos sollten sich darueber genug im Netz
finden.

Gruss
Josef Chmel

Ähnliche fragen