in Algorithms edited by
740 views
0 votes
0 votes

Read the following statements about 0/1 Knapsack problem.

(i) Time complexity of Knapsack is O(n* W) where W is the weight of the Knapsack and there are n items.
(ii) Time complexity of Knapsack is min( O(n*W) , O(2^n) ) where W is the weight of the Knapsack and there are n items.
(iii) Knapsack can be implemented in O(n*W) space .
(iv) Knapsack can be implemented in O(W) space.

where n is the number of items and W is the weight of the Knapsack .

Mark the correct option

  1.   (i) and (iii) is true
  2.   (ii) and (iii) is true
  3.   (i) ( iii) (iv) is true
  4.  (ii) (iii) (iv) is true.
in Algorithms edited by
740 views

1 comment

Option 2.  is the correct answer.

Statement 2 says, time complexity of knapsack is O(n*W) since we need to compare each element weight to 0-W.

but sometimes W will be far bigger hence 2^n exahustive search will be better.

Statement 3 is also correct.

0
0

Please log in or register to answer this question.