This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Fractional Knapsack Problem”.
1. Fractional knapsack problem is also known as __________
a) 0/1 knapsack problem
b) Continuous knapsack problem
c) Divisible knapsack problem
d) Non continuous knapsack problem
View Answer
Explanation: Fractional knapsack problem is also called continuous knapsack problem. Fractional knapsack is solved using dynamic programming.
2. Fractional knapsack problem is solved most efficiently by which of the following algorithm?
a) Divide and conquer
b) Dynamic programming
c) Greedy algorithm
d) Backtracking
View Answer
Explanation: Greedy algorithm is used to solve this problem. We first sort items according to their value/weight ratio and then add item with highest ratio until we cannot add the next item as a whole. At the end, we add the next item as much as we can.
3. What is the objective of the knapsack problem?
a) To get maximum total value in the knapsack
b) To get minimum total value in the knapsack
c) To get maximum weight in the knapsack
d) To get minimum weight in the knapsack
View Answer
Explanation: The objective is to fill the knapsack of some given volume with different materials such that the value of selected items is maximized.
4. Which of the following statement about 0/1 knapsack and fractional knapsack problem is correct?
a) In 0/1 knapsack problem items are divisible and in fractional knapsack items are indivisible
b) Both are the same
c) 0/1 knapsack is solved using a greedy algorithm and fractional knapsack is solved using dynamic programming
d) In 0/1 knapsack problem items are indivisible and in fractional knapsack items are divisible
View Answer
Explanation: In fractional knapsack problem we can partially include an item into the knapsack whereas in 0/1 knapsack we have to either include or exclude the item wholly.
5. Time complexity of fractional knapsack problem is ____________
a) O(n log n)
b) O(n)
c) O(n2)
d) O(nW)
View Answer
Explanation: As the main time taking a step is of sorting so it defines the time complexity of our code. So the time complexity will be O(n log n) if we use quick sort for sorting.
6. Fractional knapsack problem can be solved in time O(n).
a) True
b) False
View Answer
Explanation: It is possible to solve the problem in O(n) time by adapting the algorithm for finding weighted medians.
7. Given items as {value,weight} pairs {{40,20},{30,10},{20,5}}. The capacity of knapsack=20. Find the maximum value output assuming items to be divisible.
a) 60
b) 80
c) 100
d) 40
View Answer
Explanation: The value/weight ratio are-{2,3,4}. So we include the second and third items wholly into the knapsack. This leaves only 5 units of volume for the first item. So we include the first item partially.
Final value = 20+30+(40/4)=60.
8. The result of the fractional knapsack is greater than or equal to 0/1 knapsack.
a) True
b) False
View Answer
Explanation: As fractional knapsack gives extra liberty to include the object partially which is not possible with 0/1 knapsack, thus we get better results with a fractional knapsack.
9. The main time taking step in fractional knapsack problem is ___________
a) Breaking items into fraction
b) Adding items into knapsack
c) Sorting
d) Looping through sorted items
View Answer
Explanation: The main time taking step is to sort the items according to their value/weight ratio. It defines the time complexity of the code.
10. Given items as {value,weight} pairs {{60,20},{50,25},{20,5}}. The capacity of knapsack=40. Find the maximum value output assuming items to be divisible and nondivisible respectively.
a) 100, 80
b) 110, 70
c) 130, 110
d) 110, 80
View Answer
Explanation: Assuming items to be divisible-
The value/weight ratio are {3, 2, 4}.So we include third and first items wholly. So, now only 15 units of volume are left for second item. So we include it partially.
Final volume = 20+60+50x(15/25)=80+30=110
Assuming items to be indivisible- In this case we will have to leave one item due to insufficient capacity.
Final volume = 60 + 20 = 80.
Sanfoundry Global Education & Learning Series – Data Structures & Algorithms.
To practice all areas of Data Structures & Algorithms, here is complete set of 1000+ Multiple Choice Questions and Answers.
If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]
- Check Programming Books
- Practice Data Structure MCQ
- Check Computer Science Books
- Practice Programming MCQs
- Apply for Computer Science Internship
