Question: Write an algorithm for sum of subsets. Solve the following problem. M=30 W={5, 10, 12, 13, 15, 18}
2

Mumbai University > Computer Engineering > Sem 4 > Analysis of Algorithm

Marks: 10M

Year: May 2016

 modified 2.7 years ago  • written 2.7 years ago by Barkha • 750
2

Problem statement:

Let, S = {S1 …. Sn} be a set of n positive integers, then we have to find a subset whose sum is equal to given positive integer d.It is always convenient to sort the set’s elements in ascending order. That is, S1 ≤ S2 ≤…. ≤ Sn

Algorithm:

Let, S is a set of elements and m is the expected sum of subsets. Then:

2. Add to the subset, the next element from the list.

3. If the subset is having sum m then stop with that subset as solution.

4. If the subset is not feasible or if we have reached the end of the set then backtrack through the subset until we find the most suitable value.

5. If the subset is feasible then repeat step 2.

6. If we have visited all the elements without finding a suitable subset and if no backtracking is possible then stop without solution.

Example: Solve following problem and draw portion of state space tree M=30,W ={5, 10, 12, 13, 15, 18}

Solution: The state space tree is shown as below in figure. {5, 10, 12, 13, 15, 18} written 2.7 years ago by Barkha • 750