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 of the following is valid for 2 ≤ i ≤ n and ai ≤ j ≤ W ?
-
- X [i, j] = X [i – 1, j] ∨ X[i, j – ai]
- X [i, j] = X [i – 1, j] ∨ X[i – 1, j – ai]
- X [i, j] = X [i – 1, j] ∧ X[i, j – ai]
- X [i, j] = X [i – 1, j] ∧ X[i – 1, j – ai]
- X [i, j] = X [i – 1, j] ∨ X[i, j – ai]
Correct Option: B
Dynamic programming can be successfully used, i.e n rows for n elements &w + 1 columns.
Each row is filled on the basis of its previous rows & the (j – ai) – th column.
If any of them is 0 then X[i, j] should be zero. This require X[i, j] = X[i – 1, j] ∨ × [i – 1, j – ai]
Hence (b) is correct option.
