Greedy Algorithm
Basicsβ
A greedy algorithm is a problemsolving technique that builds up a solution piece by piece, always choosing the next piece that offers the most immediate benefit or the largest local gain. In simpler terms, a greedy algorithm makes a series of choices, each of which looks the best at the moment, without reconsidering those choices later on.
Key Characteristics:

Local Optimization: At each step, the algorithm selects the option that seems the best right now (the local optimum) without worrying about whether it leads to the best global solution.

Greedy Choice Property: The choice made by the algorithm at each step is the one that appears best according to some criterion. This decision is made without considering the future consequences.

Optimal Substructure: A problem has an optimal substructure if an optimal solution to the problem contains optimal solutions to its subproblems.
Demonstrationβ
Hereβs a demonstration of the Greedy Algorithm applied to the fractional knapsack problem.
You have to maximize the total value of items that can be placed in a knapsack with a given weight capacity. You are given a list of items, each with a specific value and weight, and you can take fractions of items if necessary. The goal is to determine the optimal combination of items (or portions of items) to include in the knapsack so that the total value is as high as possible without exceeding the knapsack's weight limit.
Python Codeβ
def fractional_knapsack(items, capacity):
# Calculate valuetoweight ratio for each item and sort them in descending order
items = sorted(items, key=lambda x: x[0]/x[1], reverse=True)
total_value = 0.0 # Total value accumulated in the knapsack
for value, weight in items:
if capacity >= weight:
# If the item can be fully added
capacity = weight
total_value += value
else:
# Take the fraction of the remaining capacity
total_value += value * (capacity / weight)
break
return total_value
# Example usage:
items = [(60, 10), (100, 20), (120, 30)] # Each tuple is (value, weight)
capacity = 50
max_value = fractional_knapsack(items, capacity)
print(f"Maximum value in knapsack: {max_value}")
Output : Maximum value in knapsack: 240.0