The subset-sum problem is defined as follows. Given a set of n positive…
GATE · 2008 · CS
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?
- A.
X[i, j] = X[i − 1, j] V X[i, j − ai]
- B.
X[i, j] = X[i − 1, j] V X[i − 1, j − ai]
- C.
X[i, j] = X[i − 1, j] ∧ X[i, j − ai]
- D.
X[i, j] = X[i − 1, j] ∧ X[i − 1, j − ai]
Attempted by 256 students.
Sign up free to check your answer
Sign up freeLoading lesson…