Suma de submultimi

Fie n numere pozitive    S w_i> w_i w_j    i j    si M>

Sa se determine toate multimile S` S cu =M

Folosim notatia solutiei sub forma X= x_i=0 sau 1

w_i=M

Arborele spatiului starilor va fi de forma:

Consideram w₁,w₂.w_n in ordine crescatoare (fara a fi o restrictie generala)

Functia de marginire

B_k(x₁,x₂,.x_k) = true if ( + M    and w_i + w_k+1 M)

w_i-cresc.

= false - altfel

SumSubset(s,k,r);

//(x₁,x_2,.x_n) - vectorul solutie . Psp. x₁,.,x_k-1 calculati

s =w_i r =

//Psp. w₁ M si M [ deci initial (k=1) B_k-1 = true ]

}

return

Observatie:

Functia intra in executie ,avind asigurate conditiile B_k-1=true : s+w_k M si s+r M.

Initial w₁ M si 0+ M corespunzind apelului SumSubset (0,1,)

Aceste conditii sint asigurate la apelul recursiv.

Nu se verifica explicit k>n deoarece initial s = 0     < M si s+r M. Rezulta r 0 deci k nu poate depasi n. De asemenea in linia (*) deoarece s+w_k < M si s+r M rezulta r w_k, deci k+1 n.