Sum of subset problem.pptx

Subset sum problem is to find subset of elements that are selected from a given set whose sum adds up to a given number K. We are considering the set contains non-negative values. It is assumed that the input set is unique (no duplicates are presented).

1. Sum of subset Problem Mrs.G.Chandraprabha ., M.Sc.,M.Phil ., Assistant Professor, Department of Information Technology, V.V.V.anniaperumal College for Women, Virudhunagar .

2. Sum of subset Problem Subset sum problem is to find subset of elements that are selected from a given set whose sum adds up to a given number K. We are considering the set contains non-negative values. It is assumed that the input set is unique (no duplicates are presented). In the sum of subsets problem, there are n positive integers(weights) Wi and a positive integer W. The goal is to find all subsets of the integers that sum to W.

3. Sum of subset Problem Backtracking Algorithm is used for Sum of subset problem.Using exhaustive search we consider all subsets irrespective of whether they satisfy given constraints or not. Backtracking can be used to make a systematic consideration of the elements to be selected. Assume given set of 4 elements, say  w[1] … w[4] . Tree diagrams can be used to design backtracking algorithms. The following tree diagram depicts approach of generating variable sized tuple .

4. State space tree of sum of subset State Space Tree

5. Problem: Input: The problem of determining such sets is called the sum of subset problem. In the sum of subsets problem there are n positive integers(weights) wi and a positive integer w. The goal is to find all subsets of the integers that sum to W. Problem: n=5, w=21 and W1=5 w2=6 w3=10 w4=11 w5=16 Because w1+w2+w3=5+6+10=21, w1+w5=5+16=21, w3+w4=10+11=21 The solutions are {w1,w2,w3},{w1,w5} and {w3,w4}

6. Example: Problem: Shows the pruned state space tree when backtracking is used with n=4, w=13 W1=3 , w2=4, w=5,w4=6 The solution is {w1,w2,w4}

7. Pruned state space tree

8. Explanation: The non promising nodes are marked with crosses. The nodes containing 12, 8, 9 are non promising because the adding the next weight (6) would make the value of weight exceed W. The nodes containing 7,3,4 and 0 are non-promising because there is not enough total weight remaining to bring the value of weight up to W. Notice that a leaf in the state space tree that does not containing solution automatically non promising because there are no weights remaining that could bring up to W. The leaf containing 7 illustrates this. There are only 15 nodes in the pruned state space tree , whereas the entire state space tree contains 31 nodes.

9. Algorithm: The backtracking algorithm for the sum of subsets problem Problem: Given n positive integers (weights) and a positive integer w, determine all combinations of the integers that sum to W. Input: positive integer n, sorted ( non decreasing order) array of positive integer u indexed from 1 to n, and a positive w. Problem: Void sum of subsets(index i , int weight , int total) { If (promising( i )) If (weight==w) Cout <<include[1] through include[ i ]; Else { Include[i+1]=“yes”; Sum_of_subsets (i+1, weight + w[i+1].total- w[i+1]);

10. . Include[i+1]= “no” ; Sum_of_subsets (i+1, weight, total- w[i+1]); } } bool promising(index i ); { Return( weight+total >=w)&&(weight==w||weight +w[i+1] }

11. Thank you