Direction: The subset - sum problem is defined as follows : 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? 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 ≤ i ≤ n,0 ≤ j ≤ W, is true if and only if there is a subset of {a1, a2, ....ai} 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]
- X[1, W]
Correct Option: C
The algorithm of dynamic programming has n rows & w columns.These would be filled dynamically depending upon previous rows &columns. So X[n,w] will be filled in the last & this would give the result. If X[n,w] = 1 i.e. TRUE, then we know that there is subset present whose sum = integer w. Otherwise subset not present.
Hence (c) is correct option.
