# 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

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

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

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

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)