Bissoy.com
Doctors Medicines MCQs Q&A

Which of the following is a correct time complexity to solve the 0/1 knapsack problem where n and w represents the number of items and capacity of knapsack respectively?

Which of the following is a correct time complexity to solve the 0/1 knapsack problem where n and w represents the number of items and capacity of knapsack respectively? Correct Answer O(nw)

Knapsack problem has the following two variants-

  1. Fractional Knapsack Problem
  2. 0/1 Knapsack Problem

Time Complexity- 

  • Each entry of the table requires constant time θ(1) for its computation.
  • It takes θ(nw) time to fill (n+1)(w+1) entries. Therefore, O(nw + n + w +1) =  O(nw )
  • It takes θ(n) time for tracing the solution since the tracing process traces the n rows.
  • Thus, overall θ(nw) time is taken to solve 0/1 knapsack problem using dynamic programming.

Related Questions

A 0-1 knapsack problem has four items and knapsack capacity 11. The weight and profit of each item is given in below table. Pi (Rs.) 50 30 32 27    W = 11  Wi (Kg) 5 6 4 3 Which of the following greedy strategy gives the maximum profit?
A superincreasing knapsack problem is ____ to solve than a jumbled knapsack.
What is the time complexity of the brute force algorithm used to solve the Knapsack problem?
The probability that Mohan can solve a mathematical problem is 2/3 and Sohan can solve the same problem is 3/4. If both Mohan and Sohan work on this problem, then what is the probability that the problem gets solved.
Which of the following statement about 0/1 knapsack and fractional knapsack problem is correct?
In the following figure, rectangle represents the number of persons who like Snacks, hexagon represents the number of persons who like Tea, triangle represents the number of persons who like Toasts and half capsule shaped polygon represents the number of persons who like Coffee. Which number represents Coffee which is Tea but not Toasts?  
In the following question, two statements are numbered as A and B. On solving these statements we get quantities A and B respectively. Solve for the both quantities and choose the correct option. Quantity A: A positive number is such that adding its square root to itself gives another number equal to twice the first number. Find number? Quantity B: A number which is greater than 2 is such that adding square of that number to itself gives another number equal to 3 less than 5 times of the given number. Find number?
The question below is followed by three statements I, II and III. You have to determine whether the data given is sufficient for answering the question. You should use the data and your knowledge of mathematics to choose the best possible answer. In a garments shop, there are 2 items shirts and jeans. Find which of these two items is greater in quantity? Statement I∶ The price of a shirt and a jeans is Rs. 150 and Rs. 250 respectively. Statement II∶ The total price of all the items together is Rs. 4200. Statement III∶ The average of price of all the items in the shop is Rs. 210.
A factory produces certain number of items out of which ratio of sold to unsold items is 7 : 3. If difference between sold to unsold items is 100, then what is the total number of items produced by the factory?
You are given infinite coins of N denominations v1, v2, v3,…..,vn and a sum S. The coin change problem is to find the minimum number of coins required to get the sum S. What is the time complexity of a dynamic programming implementation used to solve the coin change problem?