Multiple choice

The subset-sum problem is defined as follows. Given a set of n positive integers, S = {a1, a2, a3, …, an}, and positive integer W, is there a subset of S whose elements sum to 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$\le$i $\ge$ n,0 $\le$j $\le$ W, is TRUE if and only if there is a subset of {a1, a2, …, a} whose elements sum to j.

Which of the following is valid for 2 $\le$ i $\le$ n and ai $\le$ j $\le$ W?

  1. X[i, j] = X[i - 1, j] vX [i, j - ai]

  2. X[i, j] = X[i - 1, j] vX [i, 1, j - ai]
  3. X[i, j] = X[i - 1, j] $\land$X [i, j - ai]
  4. X[i, j] = X[i - 1, j] $\land$X [i-1, j - ai]
Reveal answer Fill a bubble to check yourself
B Correct answer
Explanation

Keep practicing — related questions