Question:
Which of the following problems can be solved optimally using a Greedy approach?
Which of the following problems can be solved optimally using a Greedy approach?
Show Hint
Which one lets you take a fraction of an item so that always grabbing the highest value-per-weight fills the bag optimally?
Updated On: Jul 2, 2026
- Fractional Knapsack Problem
- Traveling Salesman Problem
- Matrix Chain Multiplication
- 0/1 Knapsack Problem
Show Solution
Verified By Collegedunia
The Correct Option is A
Solution and Explanation
Step 1: A greedy method gives an optimal answer only when picking the best local choice at each step leads to a globally best solution.
Step 2: In the Fractional Knapsack Problem you may take fractions of an item. Sort items by value per unit weight \( \tfrac{v_i}{w_i} \), then keep adding the highest ratio item, taking a fraction of the last one to fill the bag. This greedy rule is proven optimal.
Step 3: The other three fail. The Traveling Salesman Problem is NP-hard and greedy nearest-neighbour is not optimal. Matrix Chain Multiplication needs dynamic programming to find the best parenthesization. The 0/1 Knapsack forbids fractions, so greedy by ratio can miss the best set.
Step 4: The correct answer is the Fractional Knapsack Problem, option A.
Step 2: In the Fractional Knapsack Problem you may take fractions of an item. Sort items by value per unit weight \( \tfrac{v_i}{w_i} \), then keep adding the highest ratio item, taking a fraction of the last one to fill the bag. This greedy rule is proven optimal.
Step 3: The other three fail. The Traveling Salesman Problem is NP-hard and greedy nearest-neighbour is not optimal. Matrix Chain Multiplication needs dynamic programming to find the best parenthesization. The 0/1 Knapsack forbids fractions, so greedy by ratio can miss the best set.
Step 4: The correct answer is the Fractional Knapsack Problem, option A.
Was this answer helpful?
0
0
Top CPET Computer Science Questions
- Which of the following is a key reason for choosing DRAM over SRAM for main memory?
- Which of the following components in an FPGA is responsible for implementing combinational and sequential logic?
- What is the main purpose of declaring a base class as virtual in multiple inheritance?
- What happens if a class contains at least one pure virtual function?
- What happens if a derived class defines a function with the same name as a base class function, but with a different parameter list?
View More Questions
Top CPET Questions
- Which of the following is a key reason for choosing DRAM over SRAM for main memory?
- Which of the following components in an FPGA is responsible for implementing combinational and sequential logic?
- What is the main purpose of declaring a base class as virtual in multiple inheritance?
- What happens if a class contains at least one pure virtual function?
- What happens if a derived class defines a function with the same name as a base class function, but with a different parameter list?
View More Questions