McqMate

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

Answer» C. greedy algorithm | |

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

1.7k

0

Do you find this helpful?

18

View all MCQs in

Design and Analysis of AlgorithmsNo comments yet

- Which of the following statement about 0/1 knapsack and fractional knapsack problem is correct?
- Fractional knapsack problem can be solved in time O(n).
- The result of the fractional knapsack is greater than or equal to 0/1 knapsack.
- The 0-1 Knapsack problem can be solved using Greedy algorithm.
- Fractional knapsack problem is also known as
- Time complexity of fractional knapsack problem is
- The main time taking step in fractional knapsack problem is
- The longest increasing subsequence problem is a problem to find the length of a subsequence from a sequence of array elements such that the subsequence is sorted in increasing order and it’s length is maximum. This problem can be solved using
- Which of the following algorithm can be used to solve the Hamiltonian path problem efficiently?
- Which of the following problems is equivalent to the 0-1 Knapsack problem?