Sunday, June 18, 2017

SumOfSub(s,k,r)

Algorithm:SumOfSub(s,k,r)

//Finfd all subset of W[1:n] that sum to m.The values
//of x[j]; 1<=j<k, have already been determined.

* s = ∑k-1j=1>W[j] * x[j] and r = ∑nj=k>W[j]
// The w[j]'s are in non decreasing order.
//It is assumed that W[1] <= m and  ∑ni=1>W[i] ≥ m

{

// Generate left child .Note that s+w[k] <= m
//because Bk-1 is true. 
x[k] = 1;

if(s+w[k] == m) then write (x[1:k]) // Subset found

//There is no recursive call here as w[j] > 0, 1<=j <=n.

else if(s+w[k] + w[k+1] <=m)
then SumOfSub(s+w[k], k+1, r-w[k]);
//Generate right child and evaluate Bk-1

if((s+r-w[k] >=m) && (s+w[k+1] <=m)) then {
x[k] = 0;
SumOfSub(s, k+1, r-w[k]);