24 votes

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$?

- $X[1, W]$
- $X[n, 0]$
- $X[n, W]$
- $X[n-1, n]$

19 votes

Best answer

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*={*a*1,*a*2,*a*3,…,** an**}, and positive integer

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

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≤*i*≤*n*,0≤*j*≤*W*, is TRUE, if and only if there is a subset of {*a*1,*a*2,…,** ai**} whose elements sum to

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≤*i*≤*n*,0≤*j*≤*W.*

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 a_{n }.... 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

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.

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

@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.