Data Structure Questions and Answers-0/1 Knapsack Problem

DOWNLOAD FREE PDF <<CLICK HERE>>

Data Structure Questions and Answers-0/1 Knapsack Problem

Congratulations - you have completed Data Structure Questions and Answers-0/1 Knapsack Problem.

You scored %%SCORE%% out of %%TOTAL%%.

Your performance has been rated as %%RATING%%


Your answers are highlighted below.
Question 1 [CLICK ON ANY CHOICE TO KNOW MCQ multiple objective type questions RIGHT ANSWER]
The Knapsack problem is an example of .....
A
Greedy algorithm
B
2D dynamic programming
C
1D dynamic programming
D
Divide and conquer
Question 1 Explanation: 
Knapsack problem is an example of 2D dynamic programming.

Question 2 [CLICK ON ANY CHOICE TO KNOW MCQ multiple objective type questions RIGHT ANSWER]
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
Question 2 Explanation: 
All of the mentioned techniques can be used to solve the Knapsack problem.

Question 3 [CLICK ON ANY CHOICE TO KNOW MCQ multiple objective type questions RIGHT ANSWER]
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
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 [CLICK ON ANY CHOICE TO KNOW MCQ multiple objective type questions RIGHT ANSWER]
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
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 [CLICK ON ANY CHOICE TO KNOW MCQ multiple objective type questions RIGHT ANSWER]
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)
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).

Once you are finished, click the button below. Any items you have not completed will be marked incorrect. Get Results
There are 5 questions to complete.

DOWNLOAD FREE PDF <<CLICK HERE>>