Question: Write and explain sum of subset algorithm

0

0

- Given positive numbers (weight) w_i where (1<=i<=n) and m.
- This problem calls for finding all subsets of w_i whose sum is m.
- For e.g. if n=4, m=31, (w_1,w_2,w_3,w_4) = (11, 13, 24, 7).
- Then the desired subset are (11, 13, 7) and (2, 4, 7).
- In this method of giving the solution, the solution vector is given as variable-sized tuple (tuple is collection of element).
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

- Using this strategy the solution would be (1,1,0,1) and (0,0,1,1)

**Algorithm**:

- Let n be the number of elements and let m be the required sum.
- Let w[1…..n] be an array of weights in ascending order and Let x[1….n] be the solution vector.
**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

- w[k] → weight of current element
- w[k+1] → weight of next element
- s+w[k]+w[k+1]<=m → sum of existing element+weight of current element+weight of next element is less tham m.
- Thus the next element can be selected for time being.
- s+r-w[k]>=m → Even if u discard the current element, you may still get the required sum later on.
- s+w[k+1]<=m → The sum of selected element + weight of next element is less than m . This is even if u take the next element the sum will not exit the required sum(m)
- Thus next element can be selected.

**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)

Please log in to add an answer.