GATE2008-81

3.6k 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]$

edited

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

edited
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
1
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;
}
1

Here is nice explaination.

0
Question description itself gives the answer :)
0

@srestha Ma'am, Consider the following set $S = \{ 1, 2, 3, 4, 5 \} \space and \space W = 1$

What would be then stored at $X[1,1] \space ( i.e \space X[1,W] ) \space and \space X[5,1] \space (i.e \space X[n,W])$

Wouldn't both of them be $= True$ as we have $S_1 = \{1\}$ for $i=1$ and when $i=5 \space i.e$ $S_2 = \{1,2,3,4,5\}$ the subset would be one containing the first element i.e 1 in this case.

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.

Related questions

1
3.7k 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 ... $X[i, j] = X[i-1, j] \wedge X[i, j-a_i]$ $X[i, j] = X[i-1, j] \wedge X[i-1, j-a_i]$
Consider the following C program that attempts to locate an element $x$ in an array $Y[ \ ]$ using binary search. The program is erroneous. f (int Y[10] , int x) { int u, j, k; i= 0; j = 9; do { k = (i+ j) / 2; if( Y[k] < x) i = k;else j = k; } while (Y[k] != x) && (i < j)) ; if( ... $(Y[k] < x) i = k$; else $j = k$; Change line 7 to: } while $((Y[k] == x) \&\& (i < j))$ ;
Consider the following C functions: int f1 (int n) { if(n == 0 || n == 1) return n; else return (2 * f1(n-1) + 3 * f1(n-2)); } int f2(int n) { int i; int X[N], Y[N], Z[N]; X[0] = Y[0] = Z[0] = 0; X[1] = 1; Y[1] = 2; Z[1] = 3; for(i = 2; i <= n; i++){ ... X[i]; Z[i] = 3 * X[i]; } return X[n]; } $f1(8)$ and $f2(8)$ return the values $1661$ and $1640$ $59$ and $59$ $1640$ and $1640$ $1640$ and $1661$
Let $x_n$ denote the number of binary strings of length $n$ that contain no consecutive 0s. The value of $x_5$ is $5$ $7$ $8$ $16$