The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+20 votes
2.4k views

The subset-sum problem is defined as follows. Given a set of $n$ positive integers, $S = \{ a_1, a_2, a_3, \dots , a_n \}$, and positive integer $W$, is there a subset of $S$ whose elements sum to $W$? A dynamic program for solving this problem uses a $\text{2-dimensional}$ Boolean array, $X$, with $n$ rows and $W+1$ columns. $X[i, j], 1 \leq i \leq n, 0 \leq j \leq W$, is TRUE, if and only if there is a subset of $\{a_1, a_2, \dots, a_i\}$ whose elements sum to $j$.

Which entry of the array $X$, if TRUE, implies that there is a subset whose elements sum to $W$?

  1. $X[1, W]$
  2. $X[n, 0]$
  3. $X[n, W]$
  4. $X[n-1, n]$
in Algorithms by Veteran (98.3k points)
edited by | 2.4k views

2 Answers

+15 votes
Best answer

ANSWER is C.

If LAST ROW and LAST COLUMN entry is $1$, then there exists a subset whose elements sum to $W$.

by (305 points)
edited by
0
shouldnot answer be A)?
0

here question told " 2-dimensional Boolean array "

and array has n rows and W+1 column

So, from here we  can say each row contain W+1 elements

and it is a boolean array,

So, array only contain 0 or 1

So, sum of 1 row can be maximum W+1

And question asking for " there is a subset " whose sum is W

So, isnot 1 row and W column will be possible answer?

Which is option A)

Where am I going wrong?

+2

^ read the following two lines of the given question carefully.

1.Given a set of n positive integers, S={a1,a2,a3,…,an}, and positive integer W, is there a subset of S whose elements sum to W.

2.X[i,j], 1≤in,0≤jW, is TRUE, if and only if there is a subset of {a1,a2,…,ai} whose elements sum to j.


Option A says if only first number is = W. that is X[1][W] = 1.

0

right @vijay (y)

Here 2 D array definition changed

According to point 1)there a subset of S whose elements sum to W. i.e. ok.

but in point 2) .X[i,j], 1≤in,0≤jW, is TRUE, if and only if there is a subset of {a1,a2,…,ai} whose elements sum to j.

So, sum of elements is j, so sum could be less than W too.

How do u predict it will be W?

+1

* So, sum of elements is j, so sum could be less than W too. - Yes.

* X[i,j], 1≤in,0≤jW.

here we are supposed to take array elements from a1 to ai only ..and among these numbers, we have to check if subset sum = j or not ..

but In the definition of W we can use elements from a1 to an .... so here no of array elements to be used in the calculation of subset sum differs ..

0

then what is meaning of

2-dimensional Boolean array, X, with n rows and W+1 columns

Say an array X[3,2]={1,2,3}

i should be always less than j

but is it has W+1 columns?

+1

here in 2-D array, row tells ( say X[p][q]) the domain that we are supposed to use in the given array in the calculation of subset sum.. here we will be using elements from a[1] to a[p] only not a[p+1] or a[p+2] ... if total elements in given array = n ..so we can use maximum n elements ..that's why row (max) = n = no of elements of given array.


X[p][q] -> subset sum = q or not ..where elements used in calculation of subset sum = a[1] , a[2] , ....a[p] ..

now coming to the the column -

here column says what is the value of desired subset sum ..min = 0 and max = W ( so total column = W+1) .. 



 your example- Say an array X[3,2]={1,2,3}.

here given array = a = {1, 2, 3}

X[3,2] = > can we have subset sum =2 in array = { 1, 2, 3} ...[ see here p = 3 ..so using all elements ]

X[3,2] = should be 1 , since subset sum = 2 is there [ take only 2nd element of array ]

0

@vijaycs

1)  X[p][q] ={a[1],a[2],...............a[p]}

Only upto a[p] elements are possible,not more than that.

Say in worst case W=5

then is there 6 column possible?

2)" Which entry of the array X, if TRUE, implies that there is a subset whose elements sum to W? "

but if there is more than one subset sum=5, will it be accepted?

0

1.

Say in worst case W=5

then is there 6 column possible?

----> yes total 6 column ..but no need of 7th column in the calculation of subset-sum =5. 


  1st column will be for subset-sum =0
 2nd column will be for subset-sum =1

.
. 6th -------------------------------------- = 5.
 


2 . but if there is more than one subset sum=5, will it be accepted?

----> yes .. any one possible subset will make X[ ] [5] = 1.
 

0
how 6 column possible?

S contains only 3 elements

S={1,2,3}

And W=5 possible here.

But column W+1 not possible
0
W+1 columns are there to accommodate col with W=0. Suppose there are 3 elements {1,2,3} and required sum=5(W).

So, n rows( 3 rows) and 6 columns(W+1) in a way like below:

                         0 1 2 3 4 5

                     1                

                     2                 

                    3                 (nW)

For here, we can see that the value of nW will give us the subset sum.
0

See this will be the algo for it

#include<stdio.h>
#include<stdlib.h>
int main()
{
    int i,j,m,n,W,sum,s[10][10],flag;
    printf("Number of elements in array:");
    scanf("%d%d",&n,&W);
    printf("Enter values in array either 0 or 1:");
    for(i=0;i<n;i++)
    {
        for(j=0;j<W;j++)
        {
             printf("Enter the a[%d][%d]element:",i,j);
             scanf("%d",&s[i][j]);
        }
    }
    for(i=0;i<=n;i++)
    {
         sum=0;
         for(j=0;j<W;j++)
         {   
             if(s[i][j]==1)
             {
                 if(sum!=W)
                 {
                 sum=sum+1;
                 if(sum==W)
                 {
                     flag=1;
                     break;
                 //printf("The sequence is S[%d][%d]",i,j);
                 }
                 }
             }
             else
             {
                 if(s[i][j]==0)
                 continue;
                 else
                 break;
             }
         }
     }
     if(flag==1)
     {
        printf("Such a sequence exists");
     }
     else
     {
         printf("Such a sequence not exists");
     }
        
   system("pause");
   return 0;
}            
0

Here is nice explaination.

0
Question description itself gives the answer :)
0 votes
The answer is C.  Because of entry X[n,w] is true only when there is a subset of N integer whose sum is W.
by (43 points)
Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,807 questions
54,729 answers
189,317 comments
79,913 users