1.5k 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 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 | 1.5k views
second part analysis anyone?
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.

Hope it will help to understand the problem

This will help

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

Consider the Capacity of the knapsack W 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 Ai)  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][j-ai]

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

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

Case (2) Or we do not consider the item(in this case the element ai) 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 part of 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, ai, we consider two possibilites

(1) EIther we can ignore it and still get our possible sum

Which is X[i-1][j]

OR

(2) We could include element ai and then get our required sum.

Which is X[i-1][j-ai]

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

This might help along with 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

Ans. B

Thumbs up for posting video here.