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

ADD COMMENTlink
modified 2.7 years ago  • written 2.7 years ago by gravatar for Barkha Barkha750
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:

  1. Start with an empty set.

  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:

enter image description here

The state space tree is shown as below in figure. {5, 10, 12, 13, 15, 18}

enter image description here

ADD COMMENTlink
written 2.7 years ago by gravatar for Barkha Barkha750
Please log in to add an answer.