Multipart question part 1/3. anser part a) The subset-sum problem. Let S = {s1..

Question

Multipart question part 1/3. anser part a)

The subset-sum problem. Let S = {s1....sn} be a set of n
positive integers and let t be a positive integer called the target. The
subset-sum problem is to decide if S contains a subset of elements
that sum to t. For example, if S = {2,4,10,20,25}, t = 38, then
the answer is YES because 25 + 10 + 2 + 1 = 38. However, if S =
{1,2, 4, 10, 20, 25}, t = 18, then the answer is NO. Let s = s1+...sn.

(a) Let T[0..n, 0..s] be a table such that T[i, s'] = S' if there exists a
subset of elements S' in {s1...si} whose total value is s', and
T[i, s'] = * otherwise, * is a
flag indicating that no such S' exists.
Show how T[0, k] can be easily computed for k = 0,....,s.

(b) If T[i, s'] exists (T[i, s'] != * ) and element si does not belong
to T[i, s'], how can the value of T[i, s'] be expressed using table
entries in previous rows? What about when T[i, s'] exists and
element si belongs to T[i, s']? Show how entry T[i, s'] can be
computed from table entries in previous rows.

(c) Design an O(n.s) time algorithm that decides if S contains a
subset of elements A that sum to t.

Explanation / Answer

class subset_sum
{
   // Returns true if there is a subset of set[] with sun equal to given sum
   static boolean isSubsetSum(int set[], int n, int sum)
   {
       // The value of subset[i][j] will be true if there
           // is a subset of set[0..j-1] with sum equal to i
       boolean subset[][] = new boolean[sum+1][n+1];
  
       // If sum is 0, then answer is true
       for (int i = 0; i <= n; i++)
       subset[0][i] = true;
  
       // If sum is not 0 and set is empty, then answer is false
       for (int i = 1; i <= sum; i++)
       subset[i][0] = false;
  
       // Fill the subset table in botton up manner
       for (int i = 1; i <= sum; i++)
       {
       for (int j = 1; j <= n; j++)
       {
           subset[i][j] = subset[i][j-1];
           if (i >= set[j-1])
           subset[i][j] = subset[i][j] ||
                                       subset[i - set[j-1]][j-1];
       }
       }
  
       /* // uncomment this code to print table
       for (int i = 0; i <= sum; i++)
       {
       for (int j = 0; j <= n; j++)
           printf ("%4d", subset[i][j]);
       printf(" ");
       } */
  
       return subset[sum][n];
   }
   /* Driver program to test above function */
   public static void main (String args[])
   {
       int set[] = {3, 34, 4, 12, 5, 2};
       int sum = 9;
       int n = set.length;
       if (isSubsetSum(set, n, sum) == true)
           System.out.println("Found a subset with given sum");
       else
           System.out.println("No subset with given sum");
   }
}

Related Questions

Navigate

• Browse (All)
• Browse M
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.