The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

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

- $X[i, j] = X[i-1, j] \vee X[i, j-a_i]$
- $X[i, j] = X[i-1, j] \vee X[i-1, j-a_i]$
- $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]$

+2 votes

Best answer

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 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][j-a_{i}]

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

**A[j-a _{i}]** means we have considered element a

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

Hence **answer is option B.**

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 .

+7 votes

I think answers are

(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]; }

- All categories
- General Aptitude 1.1k
- Engineering Mathematics 4.5k
- Digital Logic 1.9k
- Programming & DS 3.3k
- Algorithms 2.9k
- Theory of Computation 3.6k
- Compiler Design 1.4k
- Databases 2.7k
- CO & Architecture 2.4k
- Computer Networks 2.7k
- Non GATE 901
- Others 1.2k
- Admissions 246
- Exam Queries 433
- Tier 1 Placement Questions 17
- Job Queries 42
- Projects 4

32,330 questions

39,146 answers

108,246 comments

36,501 users