01 Knapsack Problem : Data Structure And Algorithm MCQ Practice Questions & Answers (English)

Data Structure And AlgorithmMediumDynamic Programming01 Knapsack Problem

1.

Which of the following lines completes the above code?

A

find_max(ans[itm - 1][w - wt[itm - 1]] + val[itm - 1], ans[itm - 1][w])

B

find_max(ans[itm - 1][w - wt[itm - 1]], ans[itm - 1][w])

C

ans[itm][w] = ans[itm - 1][w];

D

ans[itm+1][w] = ans[itm - 1][w];

Data Structure And AlgorithmMediumDynamic Programming01 Knapsack Problem

2.

The 0-1 Knapsack problem can be solved using Greedy algorithm.

A

True

B

False

Data Structure And AlgorithmMediumDynamic Programming01 Knapsack Problem

3.

What is the time complexity of the brute force algorithm used to solve the Knapsack problem?

A

O(n)

B

O(n!)

C

O(2^{n})

D

O(n^{3})

Data Structure And AlgorithmMediumDynamic Programming01 Knapsack Problem

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

You are given a suitcase that can carry a maximum weight of 15kg. You are given 4 items which have a weight of {10, 20, 15,40} and a value of {1, 2, 3,4}. You can break the items into smaller pieces. Choose the items in such a way that you get the maximum value

Correct Answer:

(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

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.

Data Structure And AlgorithmMediumDynamic Programming01 Knapsack Problem

5.

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

Data Structure And AlgorithmMediumDynamic Programming01 Knapsack Problem

6.

Which of the following methods can be used to solve the Knapsack problem?

A

Brute force algorithm

B

Recursion

C

Dynamic programming

D

Brute force, Recursion and Dynamic Programming

Data Structure And AlgorithmMediumDynamic Programming01 Knapsack Problem

7.

The Knapsack problem is an example of ____________

A

Greedy algorithm

B

2D dynamic programming

C

1D dynamic programming

D

Divide and conquer

01 Knapsack Problem in Data Structure And Algorithm : Practice MCQ Questions & Answers with Explanations