Sum of subset problem.pptx

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.

 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.

 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.

STATE SPACE TREE OF SUM OF SUBSET
State Space Tree

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}

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}

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.

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]);

.
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]
}

Sum of subset problem.pptx

Recommended

Recommended

More Related Content

What's hot

What's hot (20)

Similar to Sum of subset problem.pptx

Similar to Sum of subset problem.pptx (20)

More from V.V.Vanniaperumal College for Women

More from V.V.Vanniaperumal College for Women (20)

Recently uploaded

Recently uploaded (20)

Sum of subset problem.pptx