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