4.1 Definition of Greedy Algorithms.
Greedy Algorithms are a class of algorithms that build a solution by making locally optimal decisions at each step. These decisions are made based on the current state and are not reconsidered later.
Greedy algorithms are often used for solving optimization problems where the goal is to maximize or minimize a certain value.
Main principles of greedy algorithms
- Greedy choice: At each step, the algorithm picks the best local option which it believes will lead to a globally optimal solution.
- Optimal substructure: The problem must have the property that locally optimal solutions can be combined to form a global optimal solution.
- Monotonicity: After choosing the next locally optimal step, the solution should not be worsened by subsequent choices.
Advantages and disadvantages of greedy algorithms
Advantages:
- Simplicity of implementation: Greedy algorithms are often easy to understand and implement.
- Efficiency: They usually run faster than more complex algorithms like dynamic programming.
Disadvantages:
- Lack of global optimality: Greedy algorithms don't always lead to a globally optimal solution.
- Not all problems are suitable: Only certain problems can be solved using greedy algorithms.
There's a whole class of problems where the best solution is achieved by a greedy algorithm. You'll find it useful to learn about these.
4.2 Coin Change Problem.
Problem:
We have coins of different denominations. We need to find the minimum number of coins to make a given amount.
Solution:
Always take the coin of the highest denomination not exceeding the remaining amount.
Time complexity: O(n), where n is the number of coin types.
Example code in Python:
def min_coins(coins, amount):
coins.sort(reverse=True)
count = 0
for coin in coins:
while amount >= coin:
amount -= coin
count += 1
return count
4.3 Knapsack Problem
Problem:
We have items with known value and weight. We want to put things into a fixed-size backpack to get the maximum total value.
In this variant of the problem, items can be divided into parts. For example, we want to buy different grains, and it can be 1000 grams or 512.
Solution:
Sort items by unit value (value/weight) and choose the largest unit values until the backpack is filled.
Time complexity: O(n log n), where n is the number of items.
Example code in Python:
class Item:
def __init__(self, value, weight):
self.value = value
self.weight = weight
self.ratio = value / weight
def fractional_knapsack(items, capacity):
items.sort(key=lambda x: x.ratio, reverse=True)
total_value = 0.0
for item in items:
if capacity >= item.weight:
total_value += item.value
capacity -= item.weight
else:
total_value += item.ratio * capacity
break
return total_value
4.4 Problem of Covering with Segments
Problem:
We have segments on a straight line, given by their endpoints (x1, x2), and one target segment. We need to find the minimum number of segments covering all points of the target segment.
Solution:
Sort segments by right endpoint and choose the smallest segment covering the current point.
Time complexity: O(n log n), where n is the number of segments.
Example code in Python:
def min_segments(segments):
segments.sort(key=lambda x: x[1])
count = 0
end = -float('inf')
for seg in segments:
if seg[0] > end:
end = seg[1]
count += 1
return count
GO TO FULL VERSION