- Computer Science Engineering (CSE)
- Design and Analysis of Algorithms
- Which of the following problems is equiv...

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. |

View all MCQs in:
Design and Analysis of Algorithms

- Which of the following statement about 0/1 knapsack and fractional knapsack problem is correct?
- The result of the fractional knapsack is greater than or equal to 0/1 knapsack.
- Fractional knapsack problem is solved most efficiently by which of the following algorithm?
- The Knapsack problem is an example of
- The 0-1 Knapsack problem can be solved using Greedy algorithm.
- Fractional knapsack problem is also known as
- What is the objective of the knapsack problem?
- Time complexity of fractional knapsack problem is
- Fractional knapsack problem can be solved in time O(n).
- The main time taking step in fractional knapsack problem is

Login to Continue

It will take less than 2 minutes

Report MCQ