## Help authour, Buy PDF Ebook
>>>**Click Here**<<<

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

Greedy algorithm | |

2D dynamic programming | |

1D dynamic programming | |

Divide and conquer |

**Data interpretation (DI) Questions answers**

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?

Brute force algorithm | |

Recursion | |

Dynamic programming | |

All of the mentioned |

**Home science Questions answers**

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?

160 | |

200 | |

170 | |

90 |

**Aptitude test Questions answers**

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?

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

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

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

None of the mentioned |

**History Questions answers**

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?

O(n) | |

O(n!) | |

O(2 ^{n}) | |

O(n ^{3}) |

**Computer science Questions answers**

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(2

^{n}).

There are 5 questions to complete.