Q.

# 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
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.
1.5k
0