Question

1. A problem that can be solved by the Backtracking technique is the 'Sum-of-Subsets' problem. Given n distinct positive numbers (usually called weights), we want to find all possible subsets of these numbers whose sum (or weight) is W. A “binary” state space tree (like in the 0/1 Knapsack problem) can be constructed for this problem, where each level represents one of the n numbers. A left branch indicates that the number is included in the subset, and a right branch indicates that it is not. Each node stores the partial sum accumulated so far. The backtracking algorithm could be written as:

algorithm SOS (i, weight, total) {

// i is the number considered,

// weight the accumulated weight,

// total the leftover weight

// the n numbers are stored in the array w

// the array 'include' contains a solution

   if promising (i) then

      if weight = W then

         write (include)             //we found a solution     

      else

         include[i+1] := 'yes'

         SOS (i+1, weight + w[i+1], total - w[i+1]

         include[i+1] := 'no'

         SOS (i+1, weight , total - w[i+1]     

}

function promising(i){

// A node is not promising (and therefore will not be expanded) if

// adding any remaining number will make weight exceed W, or

// adding all remaining numbers will not bring weight up to W

// to facilitate the detection of the first case, it is best to order

// the numbers in a nondecreasing order

   promising = (weight+total >=W) && (weight =W || weight+w[i+1] <=W)

}

The algorithm is called with   SOS (0, 0, total), where total is the sum of all w's.

Assume n = 5, W = 21, and w = [5, 16, 11, 10, 6]

Draw the state space tree resulting from the above algorithm, and indicate the solution.

Answer 1

We represent each node as:

( current index , accumulated weight )

The state space tree can be represented as follows:

( Note that pruned nodes are further not expanded since they do not constitute the solution)

( Also, some nodes in the right subtree are shown as dots since they would get pruned and are avoided to reduce the comlpexity of the state space tree )

Solution: ( 5, 6, 10 ) and ( 5, 16 )