Data Structure Questions and Answers-0/1 Knapsack Problem

 

 Help authour, Buy PDF Ebook   >>>Click Here<<<

Data Structure Questions and Answers-0/1 Knapsack Problem

Click on any option to know the CORRECT ANSWERS

Question 1
The Knapsack problem is an example of .....
A
Greedy algorithm
B
2D dynamic programming
C
1D dynamic programming
D
Divide and conquer
Data interpretation (DI) Questions answers

Question 1 Explanation: 
Knapsack problem is an example of 2D dynamic programming.

Question 2
Which of the following methods can be used to solve the Knapsack problem?
A
Brute force algorithm
B
Recursion
C
Dynamic programming
D
All of the mentioned
Home science Questions answers

Question 2 Explanation: 
All of the mentioned techniques can be used to solve the Knapsack problem.

Question 3
You are given a knapsack that can carry a maximum weight of 60. There are 4 items with weights {20, 30, 40, 70} and values {70, 80, 90, 200}. What is the maximum value of the items you can carry using the knapsack?
A
160
B
200
C
170
D
90
Aptitude test Questions answers

Question 3 Explanation: 
The maximum value you can get is 160. This can be achieved by choosing the items 1 and 3 that have a total weight of 60.

Question 4
Which of the following problems is equivalent to the 0-1 Knapsack problem?
A
You are given a bag that can carry a maximum weight of W. You are given N items which have a weight of {w1, w2, w3, ...., wn} and a value of {v1, v2, v3, ...., vn}. You can break the items into smaller pieces. Choose the items in such a way that you get the maximum value
B
You are studying for an exam and you have to study N questions. The questions take {t1, t2, t3, ...., tn} time(in hours) and carry {m1, m2, m3, ...., mn} marks. You can study for a maximum of T hours. You can either study a question or leave it. Choose the questions in such a way that your score is maximized
C
You are given infinite coins of denominations {v1, v2, v3, ....., vn} and a sum S. You have to find the minimum number of coins required to get the sum S
D
None of the mentioned
History Questions answers

Question 4 Explanation: 
In this case, questions are used instead of items. Each question has a score which is same as each item having a value. Also, each question takes a time t which is same as each item having a weight w. You have to maximize the score in time T which is same as maximizing the value using a bag of weight W.

Question 5
What is the time complexity of the brute force algorithm used to solve the Knapsack problem?
A
O(n)
B
O(n!)
C
O(2n)
D
O(n3)
Computer science Questions answers

Question 5 Explanation: 
In the brute force algorithm all the subsets of the items are found and the value of each subset is calculated. The subset of items with the maximum value and a weight less than equal to the maximum allowed weight gives the answer. The time taken to calculate all the subsets is O(2n).

There are 5 questions to complete.

 

 Download all FREE PDF Ebook >>>CLICK HERE<<<