Skip to content
GATETECH
Official PYQ · 2008Q81Algorithm Design: Dynamic ProgrammingMCQ1 mark

GATE CS 2008 Q81 — Algorithm Design: Dynamic Programming

Explain with AI

The subset-sum problem is defined as follows. Given a set of nn positive integers, S={a1,a2,a3,…,an}S = \{ a_1, a_2, a_3, \dots , a_n \}, and positive integer WW, is there a subset of SS whose elements sum to WW? A dynamic program for solving this problem uses a 2-dimensional\text{2-dimensional} Boolean array, XX, with nn rows and W+1W+1 columns. X[i,j],1≤i≤n,0≤j≤WX[i, j], 1 \leq i \leq n, 0 \leq j \leq W, is TRUE, if and only if there is a subset of {a1,a2,…,ai}\{a_1, a_2, \dots, a_i\} whose elements sum to jj.

Which entry of the array XX, if TRUE, implies that there is a subset whose elements sum to WW?

Choose one option
View worked solution

Answer: C

According to the problem definition, the entry X[i,j]X[i, j] is defined as:

  • ii (Row index): Represents the subset of the first ii elements, i.e., {a1,a2,…,ai}\{a_1, a_2, \dots, a_i\}.
  • jj (Column index): Represents the target sum.

We want to determine if there is a subset of the entire set S={a1,a2,…,an}S = \{a_1, a_2, \dots, a_n\} (which contains all nn elements) that sums to the target value WW.

  • To consider the entire set of nn elements, we must set i=ni = n.
  • To check for the target sum WW, we must set j=Wj = W.

Thus, the entry X[n,W]X[n, W] being TRUE indicates that there exists a subset of the entire set SS whose elements sum to WW.

Therefore, the correct option is C.

Free practice · Your answers on this page are not saved.

Published
Report a correction
Keep exploringMore Algorithm Design: Dynamic Programming questions