The GATE Grind

GATE 2008 CS – Question 80

Algorithms · Dynamic Programming · 2 marks · Multiple choice

Given positive integers $S=\{a_1,\ldots,a_n\}$ and positive W, subset sum asks whether some subset sums to W. Boolean X[i, j], with n rows and W+1 columns (1≤i≤n, 0≤j≤W), is true iff a subset of the first i elements sums to j. For $2\le i\le n$ and $a_i\le j\le W$, which is valid?

  1. $X[i,j]=X[i-1,j]\lor X[i,j-a_i]$
  2. $X[i,j]=X[i-1,j]\lor X[i-1,j-a_i]$
  3. $X[i,j]=X[i-1,j]\land X[i,j-a_i]$
  4. $X[i,j]=X[i-1,j]\land X[i-1,j-a_i]$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) $X[i,j]=X[i-1,j]\lor X[i-1,j-a_i]$

Explanation

We are sorry we couldn't write detailed soluition for this, we are working on it!, please consider asking your own AI, its just 2-3 clicks with very minimum effort

More Dynamic Programming questions

All Dynamic Programming questions →