3.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 of the following is valid for $2 \leq i \leq n$, and $a_i \leq j \leq W$?

1. $X[i, j] = X[i-1, j] \vee X[i, j-a_i]$
2. $X[i, j] = X[i-1, j] \vee X[i-1, j-a_i]$
3. $X[i, j] = X[i-1, j] \wedge X[i, j-a_i]$
4. $X[i, j] = X[i-1, j] \wedge X[i-1, j-a_i]$

edited | 3.4k views
0
second part analysis anyone?
0
Its simple. When you draw 2 D array then on row side you have n values and on column side you have 0 to W values = W+1 values. Now array[n][W] wil give the truth value.

This is analogous to the dynamic programming solution to $0/1$ knapsack problem.

Consider the capacity of the knapsack, i.e., $W$ to be analogous to $J$(the total sum here).

The solution exploits the optimal substructure of the problem.

At each stage we can have $2$ options:

Case $(1)$: Either we take an item(in this question either we consider the element $A_i$)  along with the total solution to previous sub-problem(total solution here means the total sum obtained  till previous sub-problem)

in which case we choose $A[i-1]$$\left [ j-a_{i} \right ]$

$A[i-1]$ indicates we are considering solution to previous subproblem and

$A[j-a_i]$ means we have considered element $a_i$ and now remaining sum is $J-a_i$ which has to be further considered.

Case $(2)$: Or we do not consider the item(in this case the element $a_{i}$) in which case we only consider the solution to previous subproblem, which is, $A[i-1][J]$

Since the whole solution to this subset-sum problem is Logical OR(+) of cases 1 and 2, we eliminate options $C$ and $D$ because both are considering the Logical AND of the two parts of the solution.

Now, since here in the given question we are given a boolean array $X[n][W+1]$

So, an entry $X[i][j]$ is true only if sum $j$ is possible with array elements from $0$ to $i$.

So, for Each element of array, $a_{i}$, we consider two possibilities:

(1) Either we can ignore it and still get our possible sum, which is, $X[i-1][j]$

OR

(2) We could include element $a_i$ and then get our required sum, which is, $X[i-1][j-a_i]$

And finally, to get $X[i][j]$, we take logical or of the above two cases.

Reference :

By using the analogy of the problem and solution between subset-sum problem and $0/1$ knapsack problem, the above video clearly explains the how the solution to the problem is structured .

edited
0
Here condition given is 2 ≤i ≤ n, and ai ≤ j ≤W. If for X[i,j] ,  j is greater than ai then X[i-1,j] will always be blank. so whats the use of the condition x[i-1,j]?
0

Nice solution. It is an application of 0/1 Knapsack while I thought it is LCS by seeing the Ans options. Thanks for ans :)

But from problem given, how do u come to know, it will be 0/1 Knapsack and it will not be only a subset sum problem?

0

@srestha-Thank you. It is an application of subset sum problem only but you see the recurrence is somewhat similar to the recurrence of 0/1 knapsack where we either take the item or don't take the item.

0

@Ayush Upadhyaya @Arjun Please explain the the part where 2<=i<=n. Does it will not effect the solution.

(B)

$X[i][j] = X[i-1][j] \cup X[i-1][j-a_i]$

$\text{ We calculate the value of } X[i][j] \text{ as if we include the value }$

$a_i \text{ in the subset } X[i-1][j-a_i] \text{ or we do not include the value in the subset} X[i-1][j].$

(C)

// Returns true if there is a subset of set[] with sun equal to given sum
bool 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
bool subset[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("\n");
} */

return subset[sum][n];
}

edited by

Similar to $0|1$ knapsack

if $W(n)>m\rightarrow01KS(m,n-1)$

else

$\underbrace{a=01KS(m-W(n),n-1)+P(n)}$

We are not sure whether this object will give maximum profit or not. So one time we are taking it and calculating rest.

$\underbrace{b=01KS(m,n-1)}$

One time we are not taking that element and calculating rest.

$c=max(a,b)$

$Ans:B$