Sunday, June 18, 2017

Sum of Subsets

Suppose we are given n distinct numbers (usually called weights) and we desire to find all combinations of these numbers whose sums are m.This is called sum of subsets problem.We consider a backtracking solution using fixed tuple size strategy.

The children of any node in fig 6.4 are easily generated.For a node at level 1 the left child corresponds to xi = 1 and the right to xi = 0.

A simple choice for bounding function is:

Bk(X1,..,Xk) = true iff  ∑ki=1 WiXi + ∑ki=k+1 Wi ≥ m

Assuming Wi's in nondecreasing order, (X1,..,Xk) cannot lead to an answer node if  
ki=1 WiXi + ∑ki=k+1 Wi > m

So, the bounding function is
 Bk(X1,..,Xk) = true iff  ∑ki=1 WiXi + ∑ki=k+1 Wi ≥ m and
ki=1 WiXi + ∑ki=k+1 Wi > m