Dynamische Programmierung Partition Problem

[Xzeer]

Hallo zusammen,

es geht um folgendes Problem: Partition problem

Eingabe: Eine Liste mit Integerwerten
Gesucht: Der Wahrheitswert, ob die Liste in zwei Unterlisten mit gleicher Summe zerlegt werden kann

Im oben verlinkten Wikipediaartikel ist ja ein dynamischer Algorithmus angegeben. Doch entweder habe ich den nicht richtig verstanden oder der ist irgendwie falsch. :stupid: Wenn ich den so übernehme, bekomme ich immer eine ArrayOutOfBounds-Exception in Zeile 8. Ist ja eigentlich auch logisch, weil im ersten Schleifendurchlauf ist i = 1 und j = 1. Wenn jetzt in der Liste an Indexposition 1 ein Wert größer als 1 steht, wird der Wert i-S[j] doch zwangsweise negativ und liegt dann außerhalb von P.

Habe ich da jetzt einen Denkfehler oder ist der wirklich nicht ganz korrekt? :gruebel:

[spaxxn]

Mit deinem bisher erstellten Quelltext, könnte man dir mit Sicherheit weiterhelfen...

[Iwo Asnet]

Zitat:

Zitat von Wikipedia

INPUT: A list of integers S
OUTPUT: True if S can be partitioned into two subsets that have equal sum

Code:

1 function find_partition( S ):
2     N = sum(S)
3     P = empty boolean table of size (N/2 +  1) by (n + 1)
4     initialize top row (P(0,x)) of P to True
5     initialize leftmost column (P(x, 0)) of P, except for P(0, 0) to False
6     for i from 1 to N/2
7          for j from 1 to n
8          P(i, j) ← P(i, j-1) or P(i-S[j], j-1)
9     return P(N/2 , n)

Sehe ich auch so, das für jedes S[j]>i ein Problem auftritt.
Die For-J-Schleife über alle Elemente von S geht zudem bis zur Summe aller Elemente von S und dann knallt es auch. Beispiel:

Code:

S = (1,2,3) (also Elemente 0,1,2.
N = 1+2+3 = 6
For j:=1 to 6 S[j] <--- puff

[DeddyH]

Arrayindizes fangen bei Low(Array) an, was bei dynamischen immer 0 ist, bei statischen aber frei definiert werden kann.

[spaxxn]

Bei mir steht gerade eher die Frage im Raum, ob die Länge des Arrays gesetzt wurde :D

[DeddyH]

Mit Code wäre das leichter zu klären :roll: