Dynamic Programming 4
Linked Answers Questions 5 and 6
The subset-sum problem is defined as follows. Given a set of n positive integers, S = {a1 , a2 , a3 , …….., an } and a positive integer W is there a subset S whose elements sum of 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.
0. Which of the following is valid for 2 < i < n and ai ≥ j ≥ W?
- Option : B
- Explanation : X [i, j] = X[i–1, j] ∨ X[i-1, j–ai] x [i, j] is true if any one is true. or x[i – 1, j – ai] is true
