2.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 | 2.6k views

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

by (331 points)
edited
0
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[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 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 , a , ....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,a,...............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[ ]  = 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,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 :)