CO2412 Computational Thinking Lecture 7 Notes

CO2412: Computational Thinking
Lecture 7

The Greedy Algorithm
1. Introduction
o A greedy algorithm follows the problem-solving heuristic of making
the locally optimal choice at each stage with the hope of finding the
global optimum.
o Greedy algorithms are typically used for optimization problems.

2. Characteristics of Greedy Algorithms
o Local Optimization: The algorithm selects the best option
available at each step without considering the broader context.
o Greedy Choice Property: It assumes that by choosing the optimal
local solution, the global solution will also be optimal.
o Optimal Substructure: The problem can be broken down into
smaller subproblems, which can be solved optimally.
Fractional Knapsack Problem
1. Problem Statement
o The Fractional Knapsack problem involves a thief who can carry a
maximum weight in their knapsack. The goal is to maximize the
value of the knapsack by taking fractions of items.
2. Greedy Approach to Fractional Knapsack
o Items are selected based on the highest value-to-weight ratio.

o The item with the highest ratio is taken first, followed by the next,
and so on, until the knapsack is full.
Example: