The subset-sum problem is defined as follows. Given a set of n positive…
2008
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? Which entry of the array X, if TRUE, implies that there is a subset whose elements sum to W?
- A.
X[1, W]
- B.
X[n, 0]
- C.
X[n, W]
- D.
X[n-1, n]
Attempted by 73 students.
Show answer & explanation
Correct answer: C
Answer: X[n, W] is the entry to check. If X[n, W] is TRUE, there exists a subset of {a1,...,an} whose elements sum to W.
Recurrence: For 2 <= i <= n and ai <= j <= W, the table satisfies the relation X[i, j] = X[i-1, j] OR X[i-1, j - ai].
Base cases: For all i, X[i, 0] = TRUE (empty subset). For i = 1, X[1, a1] = TRUE if a1 <= W; otherwise X[1, j] is TRUE only if j = 0.
Meaning: X[i, j] is TRUE exactly when some subset of the first i items sums to j. Using the recurrence fills the table for increasing i and j.
Decision rule: After filling the table for i = 1..n and j = 0..W, check X[n, W]. If it is TRUE, a subset summing to W exists; otherwise no such subset exists.
A video solution is available for this question — log in and enroll to watch it.