0
6.8kviews
Write and explain sum of subset algorithm
written 7.7 years ago by | • modified 2.2 years ago |
Write and explain sum of subset algorithm for W = {2, 7, 8, 9, 15} M = 17
ADD COMMENT
EDIT
1 Answer
written 7.7 years ago by | • modified 2.2 years ago |
Write and explain sum of subset algorithm for W = {2, 7, 8, 9, 15} M = 17
written 7.7 years ago by |
The solution may also be expressed as fixed size tuple (x_1,x_(2,),x_3,…….,x_n) such that
x_i =0 if w_i is not selected
x_i =1 if w_i is selected
Algorithm:
Method
SumOfSubset(s, k, r)
{
x[k] =1; //Generating left child
if(s+w[k]==m)
Display x[1….k] //and remaining zeros
else if(s+w[k]+w[k+1]<=m)
SumOfSubset(s+w[k], k+1, r-w[k])
if((s+r-w[k]>=m) && (s+w[k+1]<=m))
{
x[k]=0;
SumOfSubset(s, k+1, r-w[k]);
}
}
S → existing sum
Problem:
n = 5, W = {2, 7, 8, 9, 15} M = 17
Hence, there are three subset with given sum m=17
A(111)
B(10001)
C(0010)