edited by
10,082 views
32 votes
32 votes

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

Which entry of the array $X$, if TRUE, implies that there is a subset whose elements sum to $W$?

  1. $X[1, W]$
  2. $X[n, 0]$
  3. $X[n, W]$
  4. $X[n-1, n]$
edited by

2 Answers

Best answer
22 votes
22 votes

ANSWER is C.

If LAST ROW and LAST COLUMN entry is $1$, then there exists a subset whose elements sum to $W$.

edited by
Answer:

Related questions

24 votes
24 votes
6 answers
4
go_editor asked Apr 23, 2016
5,187 views
Let $x_n$ denote the number of binary strings of length $n$ that contain no consecutive $0$s.The value of $x_5$ is $5$$7$$8$$16$