Project ForgeThe subset-sum problem is defined as follows: given a set of n positive integers S={a1,...,an} and a positive integer W, is there a subset of S whose elements sum to W? A dynamic program uses a 2D Boolean array X with n rows and W+1 columns, where X[i,j] (1≤i≤n, 0≤j≤W) is TRUE iff some subset of {a1,...,ai} sums to j. Which of the following is valid for 2≤i≤n and aᵢ≤j≤W?
- AX[i,j] = X[i-1,j] ∨ X[i,j-aᵢ]
- X[i,j] = X[i-1,j] ∨ X[i-1,j-aᵢ]
- CX[i,j] = X[i-1,j] ∧ X[i,j-aᵢ]
- DX[i,j] = X[i-1,j] ∧ X[i-1,j-aᵢ]
Explanation
X[i,j] is true if a subset of the first i elements sums to j — either aᵢ is EXCLUDED (some subset of the first i-1 sums to j: X[i-1,j]) OR aᵢ is INCLUDED (some subset of the first i-1 sums to j-aᵢ: X[i-1,j-aᵢ]). These are combined with OR since either possibility suffices.
Source: GATE CS 2008 (2008)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.