Fractional knapsack problem is solved most efficiently by which of the following algorithm?

M

Mr. Dubey

🎓 Coach ⭐ 104.48K Points

📊 Design and Analysis of Algorithms

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

💬 Discuss

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

Explanation by: Mr. Dubey

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.

💬 Discussion

📊 Question Analytics

👁️

154

Total Visits

📽️

3 y ago

Published

🎖️

Mr. Dubey

Publisher

📈

86%

Success Rate